代码

#include "router.h"
struct TrieNode{
	unsigned nexthop;
	unsigned is;
	unsigned padding1;
	unsigned padding2;
	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){
			if((i->addr)>>l&1){
				if(v->c1)v=v->c1;
				else v=v->c1=++t;
			}else{
				if(v->c0)v=v->c0;
				else v=v->c0=++t;
			}
		}
		v->is=1;
		v->nexthop=i->nexthop;
	}
	//for(TrieNode *v=T;v<=t;++v){
		//std::cout<<v<<" c0="<<(v->c0)<<" c1="<<(v->c1)<<" nexthop="<<(v->nexthop)<<std::endl;
		//printf("%llx c0=%llx c1=%llx nexthop=%u\n",v,v->c0,v->c1,v->nexthop);
	//}
}
unsigned query(unsigned addr) {
	unsigned cur=0;
	TrieNode *v=T;
	for(char l=31;~l;--l){
		if(addr>>l&1)v=v->c1;else v=v->c0;
		if(v){if(v->is)cur=v->nexthop;}
		else return cur;
	}
	return cur;
}

评测结果