代码

# define max_entries 827088ul

# include "router.h"

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

unsigned n_nodes;
unsigned trie_childs[max_entries * 32][2];
unsigned trie_nexthop[max_entries * 32];
bool trie_is_valid[max_entries * 32];

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

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

评测结果