代码

#include "router.h"

#include <cassert>

const int maxn = 827090 << 5;

int nodes = 1;
int next[maxn][2];
bool isEntry[maxn];
unsigned nexthop[maxn];

unsigned toLittleEndian(unsigned bigEndian) {
	return ((bigEndian & 0xffu) << 24) | ((bigEndian & 0xff00u) << 8) | ((bigEndian & 0xff0000u) >> 8) | ((bigEndian & 0xff000000u) >> 24);
}

void insert(const RoutingTableEntry &entry) {
	const unsigned addr = toLittleEndian(entry.addr), len = entry.len;
	int o = 0;
	for (unsigned i = 0; i < len; ++i) {
		const int digit = !!(addr & (1u << (31 - i)));
		assert(digit == 0 || digit == 1);
		if (!next[o][digit]) {
			next[o][digit] = nodes;
			isEntry[nodes] = false;
			++nodes;
		}
		o = next[o][digit];
	}
	isEntry[o] = true;
	nexthop[o] = entry.nexthop;
}

void init(int n, int q, const RoutingTableEntry *a) {
	for (int i = 0; i < n; ++i) {
		insert(a[i]);
	}
}

unsigned query(unsigned addr) {
	addr = toLittleEndian(addr);
	int o = 0;
	unsigned ans = isEntry[o] ? nexthop[o] : 0;
	for (int i = 0; i < 32; ++i) {
		const int digit = !!(addr & (1u << (31 - i)));
		if (!next[o][digit]) {
			return ans;
		} else {
			o = next[o][digit];
			if (isEntry[o]) {
				ans = nexthop[o];
			}
		}
	}
	return ans;
}

评测结果