代码

# 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];
unsigned one_bit_prefix[33], addr_mask[33];
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;
    for (unsigned i = 0; i < 32; ++ i) {
        unsigned bit = (addr >> (31ul - i)) & 1ul;
        if (trie_childs[current][bit])
            current = trie_childs[current][bit];
        else
            return trie_nexthop[current];
    }
    return trie_nexthop[current];
}

评测结果