代码

# define max_entries 827088ul

#include "router.h"

int n_entries, n_nodes;
unsigned trie_childs[max_entries * 32][2];
unsigned trie_nexthop[max_entries * 32];
RoutingTableEntry *routing_table;

void init(int n, int q, const RoutingTableEntry *a) {
    n_entries = n;
    routing_table = (RoutingTableEntry*) a;
    for (unsigned i = 0; i < n_entries; ++ i) {
        unsigned addr = routing_table[i].addr, bit;
        unsigned mask_length = routing_table[i].len, current = 0;
        for (unsigned j = 0; j < mask_length; ++ j) {
            bit = (addr >> (31ul - j)) & 1ul;
            if (!trie_childs[current][bit])
                trie_childs[current][bit] = ++ n_nodes;
            current = trie_childs[current][bit];
        }
        trie_nexthop[current] = routing_table[i].nexthop;
    }
}

unsigned query(unsigned addr) {
    unsigned current = 0, nexthop = 0;
    for (unsigned i = 0; i < 32; ++ i) {
        if (trie_nexthop[current])
            nexthop = trie_nexthop[current];
        unsigned bit = (addr >> (31ul - i)) & 1ul;
        if (trie_childs[current][bit])
            current = trie_childs[current][bit];
        else break;
    }
    if (trie_nexthop[current])
        nexthop = trie_nexthop[current];
    return nexthop;
}

评测结果