代码

#include <arpa/inet.h>
#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;
		unsigned int ad=htonl(i->addr);
		for(char l=31,r=31-i->len;l!=r;--l){
			if(ad>>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;
	}
}
unsigned query(unsigned addr) {
	unsigned cur=0,ad=htonl(addr);
	TrieNode *v=T;
	if(v->is)cur=v->nexthop;
	for(char l=31;~l;--l){
		if(ad>>l&1)v=v->c1;else v=v->c0;
		if(v){if(v->is)cur=v->nexthop;}
		else return cur;
	}
	return cur;
}

评测结果