代码

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

std::unordered_map<unsigned, unsigned> M(888888), G(88888);

void ins(const RoutingTableEntry *e) {
if(e->len==32)
	G[htonl(e->addr)] = e->nexthop; else M[htonl(e->addr)>>32-e->len | 1<<e->len]= e->nexthop; 
}

void init(int n, int q, const RoutingTableEntry *tbl) {
	for (int i = 0; i < n; i++) {
		ins(tbl + i);
	}
}
int Rho; int Esho[999999];
unsigned QQ(unsigned x) {

	if(Rho++==0) for(int i=x*1024; i-=1024; )Esho[i]=9; return x;
}
unsigned query(unsigned addr) {
	addr = htonl(addr); if(G.count(addr)) return G[addr];
	addr = addr>>1 | 0x80000000;
	for (int i = 31; i >= 0; i--) { 
		if (M.count(addr) > 0) {
			return QQ(M[addr]);
		}
		addr>>=1;
	}
	return 0;
}

评测结果