代码

#include "router.h"
struct TrieNode{
	unsigned nexthop;
	unsigned padding1;
	unsigned padding2;
	unsigned padding3;
	TrieNode *c0;
	TrieNode *c1;
}T[26466817];
void init(int n, int q, const RoutingTableEntry *a) {
	TrieNode *t=T;
	for(const RoutingTableEntry *i=a,*e=a+n;i!=e;++i){
		TrieNode *v=T;
		for(char l=31,r=31-i->len;l!=r;--l){
			unsigned char c=(i->addr)>>l;
			if(c){
				if(v->c1)v=v->c1;
				else v=v->c1=++t;
			}else{
				if(v->c0)v=v->c0;
				else v=v->c0=++t;
			}
		}
		v->nexthop=i->nexthop;
	}
}
unsigned query(unsigned addr) {
	unsigned cur=0;
	TrieNode *v=T;
	for(char l=31;~l;--l){
		unsigned char c=addr>>l;
		if(c)v=v->c1;else v=v->c0;
		if(v){if(v->nexthop)cur=v->nexthop;}
		else return cur;
	}
	return cur;
}

评测结果