代码

#include "router.h"

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

const int MAX_N = 900000;
const int MAX_N_NODES = MAX_N * 32;

struct TrieNode {
	TrieNode *s[2];
	uint32_t nexthop;
};

static TrieNode nodes[MAX_N_NODES], *last_node = nodes, *root;

static inline TrieNode * new_node() {
	return last_node++;
}

static void trie_insert(TrieNode *root, uint32_t addr, int len, uint32_t nexthop) {
	int bit_id = 32 - len;
	for (int i = 31; i >= bit_id; i--) {
		TrieNode *&t = root->s[(addr >> i) & 1];
		if (!t) t = new_node();
		root = t;
	}
	
	root->nexthop = nexthop;
}

static uint32_t trie_query(TrieNode *root, uint32_t addr) {
	uint32_t ans = root->nexthop;
	for (int i = 31; i >= 0; i--) {
		TrieNode *t = root->s[(addr >> i) & 1];
		if (!t) return ans;
		if (t->nexthop) ans = t->nexthop;
		root = t;
	}
	return ans;
}

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

unsigned query(unsigned addr) {
	return trie_query(root, htonl(addr));
}

评测结果