代码

#include "router.h"

/*
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) {
	Node* c = _root;
	int solo;
	for (int i = 1; i <= a.len; i++) {
		solo = a.addr>>(32-i)&1;
		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;
}

void init(int n, int q, const RoutingTableEntry *a) {
	for (int i = 1; i <= n; i++) {
		Insert(a[i]);
	}
}

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

评测结果