代码

#include "router.h"
#include <arpa/inet.h>
#include <unordered_map>

unsigned nexthop_trie[17000000] = {0};
std::unordered_map <unsigned, unsigned> hashmap;

void init(int n, int q, const RoutingTableEntry *a) {
    for (int i = 0; i < n; i++)
    {
        unsigned addr = a[i].addr;
        if (a[i].len == 32)
            hashmap[a[i].addr] = a[i].nexthop;
        else
        {
            int cnt = 0;
            for (int l = a[i].len; l > 0; l -= 8)
            {
                cnt = (cnt << 8) + (addr & 255) + 1;
                addr >>= 8;
            }
            nexthop_trie[cnt] = a[i].nexthop;
        }
    }
}

unsigned query(unsigned addr) {
    if (hashmap.find(addr) != hashmap.end())
        return hashmap[addr];
    int ret = 0;
    int cnt = 0;
    for (int l = 24; l > 0; l -= 8)
    {
        cnt = (cnt << 8) + (addr & 255) + 1;
        addr >>= 8;
        if (nexthop_trie[cnt] != 0)
            ret = nexthop_trie[cnt];
    }
    return ret;
}

评测结果