代码

//#define Debug 
#ifndef Debug
#include "router.h"
#endif
#ifdef Debug
typedef struct {
    unsigned addr;
    unsigned char len;
    char pad[3];  // Padding for memory alignment
    unsigned nexthop;
} __attribute__((packed)) RoutingTableEntry;
#endif

#include <netinet/in.h> 
#include <cstdlib>
unsigned ones_prefix[33];
unsigned mask_addr[33];
int maxlen=-1;
int n;
int q;
RoutingTableEntry *a;

struct trie_node
{
	unsigned nexthop;
	unsigned isvalid;
	trie_node* son[2];
};
trie_node* root=new trie_node;
void insert_node(unsigned addr,unsigned len,unsigned nexthop){
	trie_node* tmp_node=root;
	for (unsigned i=0;i<len;i++){
		int dir=((addr&(1<<(31-i)))>0);
		if (tmp_node->son[dir]==NULL){
			tmp_node->son[dir]=new trie_node;
			tmp_node=tmp_node->son[dir];
			tmp_node->son[0]=tmp_node->son[1]=NULL;
			tmp_node->nexthop=tmp_node->isvalid=0;
		}
		else{
			tmp_node=tmp_node->son[dir];
		}
	}
	tmp_node->nexthop=nexthop;
	tmp_node->isvalid=1;
}



void init(int _n, int _q, const RoutingTableEntry *_a) {
	n=_n;
	q=_q;
	a=(RoutingTableEntry*)_a;
	for (int i=1;i<=32;i++){
		ones_prefix[i]=ones_prefix[i-1]|(1<<(32-i));
	}

	root->son[0]=root->son[1]=NULL;
	root->nexthop=root->isvalid=0;
	for (int i=0;i<n;i++){
		insert_node(htonl(a[i].addr),a[i].len,a[i].nexthop);
	}
}


unsigned query(unsigned addr) {
	addr=htonl(addr);
	trie_node* tmp_node=root;
	unsigned ans=root->nexthop;
	for (int i=0;i<32;i++){
		int dir=((addr&(1<<(31-i)))>0);
		if (tmp_node->son[dir]==NULL){
			break;
		}
		tmp_node=tmp_node->son[dir];
		if (tmp_node->isvalid==1){
			ans=tmp_node->nexthop;
		}
	}


	return ans;
}

评测结果