代码

#include "router.h"
struct Trienode{
	unsigned nexthop;
	unsigned ls,rs;
	bool end;
}T[30100000];
int t;
void init(int n, int q, const RoutingTableEntry *a) {
	for(register RoutingTableEntry *i=a,*e=a+n;i!=e;++i){
		unsigned cur=0,val=i->addr;
		for(register int b=31,r=31-i->len;l>r;--l){
			if(val>>b&1){
				if(!T[cur].ls)T[cur].ls=++t;
				cur=T[cur].ls;
			}
			else{
				if(!T[cur].rs)T[cur].rs=++t;
				cur=T[cur].rs;
			}
		}
		T[cur].end=true;
		T[cur].nexthop=i->nexthop;
	}
}
unsigned query(unsigned addr) {
	unsigned cur=0,ans=0;
	for(register int i=31;~i;--i){
		if(addr>>i&1)cur=T[cur].rs;
		else cur=T[cur].ls;
		if(!cur)return ans;
		else if(T[cur].end)ans=T[cur].nexthop;
	}
	return ans;
}

评测结果