代码

#include "router.h"

#include <stdint.h>
#include <arpa/inet.h>

#include <unordered_map>

static std::unordered_map<uint32_t, uint32_t> M[33];

// Assume sorted
static void insert(uint32_t addr, int len, uint32_t nexthop) {
	uint32_t last_nexthop = M[0][0];
	for (int i = 1; i < len; i++) {
		uint32_t &t = M[i][addr >> (32 - i) << (32 - i)];
		if (t) {
			last_nexthop = t;  // get deepest nexthop
		} else {
			t = last_nexthop;  // push-down
		}
	}
	
	M[len][addr] = nexthop;
}

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

unsigned query(unsigned addr) {
	addr = htonl(addr);
	int bits = 0;
	if (M[16].count(addr >> 16 << 16)) bits = 16;
	if (M[bits + 8].count(addr >> (32 - bits - 8) << (32 - bits - 8))) bits += 8;
	if (M[bits + 4].count(addr >> (32 - bits - 4) << (32 - bits - 4))) bits += 4;
	if (M[bits + 2].count(addr >> (32 - bits - 2) << (32 - bits - 2))) bits += 2;
	if (M[bits + 1].count(addr >> (32 - bits - 1) << (32 - bits - 1))) bits += 1;
	if (bits == 31 && M[32].count(addr)) return M[32][addr];
	if (bits == 0) return M[0][0];
	return M[bits][addr >> (32 - bits) << (32 - bits)];
}

评测结果