代码

#include <arpa/inet.h>
#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(const RoutingTableEntry *i=a,*e=a+n;i!=e;++i){
		unsigned cur=0,val=htonl(i->addr);
		for(register char b=31,b_end=31-i->len;b!=b_end;--b){
			if((val>>b)&1){
				if(!T[cur].rs)T[cur].rs=++t;
				cur=T[cur].rs;
			}
			else{
				if(!T[cur].ls)T[cur].ls=++t;
				cur=T[cur].ls;
			}
		}
		T[cur].end=true;
		T[cur].nexthop=i->nexthop;
	}
}
unsigned query(unsigned addr) {
	unsigned cur=0,ans=0,val=htonl(addr);
	if(T[cur].end)ans=T[cur].nexthop;
	for(register char b=31;~b;--b){
		if((val>>b)&1)cur=T[cur].rs;
		else cur=T[cur].ls;
		if(!cur)break;
		else if(T[cur].end)
			ans=T[cur].nexthop;
	}
	return ans;
}

评测结果