代码

#include "router.h"

struct node{
	node *ch[2];
	unsigned nexthop;
	bool is_end;
	node () {
		ch[0]=ch[1]=0;
		is_end=false;
		nexthop=0u;
	}
}*rt;

inline unsigned _bit(unsigned a,unsigned k)//k in 0-31
{
	k=31-k;
	return a&(1<<k)>>(k);
}
inline void insert(char *bp,unsigned char len,unsigned nexthop,node *cur=rt)
{
	while(1){
		if(len==0)
		{
			cur->nexthop=nexthop;
			cur->is_end=true;
			break ;
		}
		++bp;
		--len;
		if(cur->ch[*bp]==0) cur->ch[*bp]=new node(); 
		cur=cur->ch[*bp];
	}
//	insert(bp+1,len-1,nexthop,((cur->ch[*bp]==0)?cur->ch[*bp]=new node:cur->ch[*bp]));
}
void init(int n, int q, const RoutingTableEntry *a) {
	rt=new node ();
	char bp[32];
	for(int i=0;i<n;++i)
	{
		for(unsigned char j=0;j<a[i].len;++j)
		{
			bp[j]=_bit(a[i].addr,1u*j);
		}
		insert(bp,a[i].len,a[i].nexthop);
	}
}
unsigned query(char *bp,unsigned char len,node *cur=rt)
{
	unsigned res=0;
	while(1)
	{
		if(rt->is_end)
		{
			res=rt->nexthop;
		}
		if(len==0)
		{
			break;
		}
		++bp;
		--len;
		if(cur->ch[*bp]==0) break;
		cur=cur->ch[*bp];
	}
	return res;
}
unsigned query(unsigned addr) {
	static char bp[32];
	for(unsigned char j=0;j<32;++j)
	{
		bp[j]=_bit(addr,1u*j);
	}
	return query(bp,32);
}

void del__(node *rt)
{
	if(rt==0) return;
	del__(rt->ch[0]);
	del__(rt->ch[1]);
	delete(rt);
	return ;
}
void del()
{
	del__(rt);
}

评测结果