代码

#include "router.h"
#include <iostream>

/*
typedef struct {
    unsigned addr;
    unsigned char len;
    char pad[3];  // Padding for memory alignment
    unsigned nexthop;
} __attribute__((packed)) RoutingTableEntry;
*/

using namespace std;

struct Node {
	bool end;
	int hop;
	Node* next[2];
};

Node* _root = new Node;

void Insert(RoutingTableEntry a) {
//	cout << "Insert " << a.addr << endl;
	Node* c = _root;
	int solo;
	for (int i = 1; i <= a.len; i++) {
		solo = a.addr>>(32-i)&1;
//		cout << i << ',' << solo << endl;
		if (!c->next[solo]) {
			c->next[solo] = new Node;
			c->next[solo]->end = false;
			c->next[solo]->next[0] = 0;
			c->next[solo]->next[1] = 0;
		}
		c = c->next[solo];
	}
	c->end = true;
	c->hop = a.nexthop;
//	cout << "Insertion end" << endl;
}

//RoutingTableEntry Input() {
//	RoutingTableEntry a;
//	unsigned x, y, z;
//	cin >> hex >> x >> dec >> y >> z;
//	a.addr = x;
//	a.len = y;
//	a.nexthop = z;
//	return a;
//}

void init(int n, int q, const RoutingTableEntry *a) {
	_root->end = false;
	_root->next[0] = 0;
	_root->next[1] = 0;
	for (int i = 0; i < n; i++) {
		Insert(a[i]);
	}
//	cout << "init end" << endl;
}

unsigned query(unsigned addr) {
//	cout << "Query " << addr << endl;
	unsigned res = 0;
	Node* c = _root;
	int solo;
	if (c->end) {
		res = c->hop;
	}
	for (int i = 1; i <= 32; i++) {
		solo = addr>>(32-i)&1;
//		cout << i << ',' << solo << endl;
		c = c->next[solo];
		if (!c) return res;
		if (c->end) {
			res = c->hop;
		}
	}
	return res;
}

评测结果