代码

#include "router.h"
#include <arpa/inet.h>

int reusei=0, reusej=0;
struct pp {pp* left, *right; unsigned refer;} pool[9999999]; int ppcnt=0; pp* reusep;
pp* insert(pp*& pos) {if(!pos){if(reusej<=reusei){pos=reusep+reusej++; pos->left=pos->right=0;pos->refer=0;}else pos=pool+ ++ppcnt; }return pos;}
pp& insert(int depth, unsigned pos) {pp* p=pool; for(int i=0; i<depth;++i) {
p=insert(pos&0x80000000?p->right:p->left), pos<<=1;
}
return *p;
}
void init(int n, int q, const RoutingTableEntry *a) { reusep=(pp*)a;
	for(reusei=0; reusei<n; ++reusei) {unsigned t=a[reusei].nexthop; insert(a[reusei].len,htonl(a[reusei].addr)).refer=t;}
}

unsigned query(unsigned addr) {addr=htonl(addr);
	unsigned res=0;pp* p=pool;
	do {
		if(p->refer)res=p->refer;p=addr&0x80000000?p->right:p->left;
addr<<=1;
}
	while(p);return res;
}

评测结果