代码

#include "router.h"

#include <cassert>
#include <vector>

struct Node {
	bool isEntry;
	unsigned nexthop;
	unsigned next[2];

	Node(): isEntry(false), nexthop(0), next({0, 0}) {}
};

std::vector<Node> nodes = {Node()};

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 (!nodes[o].next[digit]) {
			nodes.push_back(Node());
			nodes[o].next[digit] = nodes.size() - 1;
		}
		o = nodes[o].next[digit];
	}
	nodes[o].isEntry = true;
	nodes[o].nexthop = 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 = nodes[o].isEntry ? nodes[o].nexthop : 0;
	for (int i = 0; i < 32; ++i) {
		const int digit = !!(addr & (1u << (31 - i)));
		if (!nodes[o].next[digit]) {
			return ans;
		} else {
			o = nodes[o].next[digit];
			if (nodes[o].isEntry) {
				ans = nodes[o].nexthop;
			}
		}
	}
	return ans;
}

评测结果