代码

# define max_entries 827088ul

# include "router.h"

int n_nodes;
unsigned trie_childs[max_entries * 32][2];
unsigned trie_nexthop[max_entries * 32];

void init(int n, int q, const RoutingTableEntry *a) {
    int n_entries = n;
    RoutingTableEntry *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, nexthop = trie_nexthop[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;
                trie_nexthop[n_nodes] = nexthop;
            }
            nexthop = trie_nexthop[current];
            current = trie_childs[current][bit];
        }
        trie_nexthop[current] = routing_table[i].nexthop;
    }
}

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

评测结果