代码

#include "router.h"
#include <bits/stdc++.h>
#include <arpa/inet.h>
using namespace std;

struct MyEntry
{
    unsigned len, addr, nexthop;
};
bool operator<(const MyEntry &a, const MyEntry &b)
{
    return *(unsigned long long *) &a < *(unsigned long long *) &b;
}

struct VEntry
{
    unsigned addr, nexthop;
};
bool operator<(const VEntry &a, const VEntry &b)
{
    return a.addr < b.addr;
}

vector<VEntry> V;
const int FAST_OFFSET = 18;
VEntry *fastV[1 << FAST_OFFSET | 1];
set<MyEntry> S;

unsigned pow2(unsigned x)
{
    if(x >= 32) return 0;
    return 1u << x;
}

void init(int n, int q, const RoutingTableEntry *a)
{
    for(int i = 0; i < n; i++) S.insert(S.end(), (MyEntry) {a[i].len, htonl(a[i].addr), a[i].nexthop});
    S.insert(S.begin(), (MyEntry) {0, 0, 0});
    for(auto it = S.begin(); it != S.end();)
    {
        auto jt = it; ++jt;
        if(jt != S.end() && jt->addr <= it->addr + pow2(32 - it->len) - 1u)
        {
            S.insert(it, (MyEntry) {it->len + 1, it->addr, it->nexthop});
            S.insert(it, (MyEntry) {it->len + 1, it->addr | pow2(31 - it->len), it->nexthop});
        }
        else V.push_back((VEntry) {it->addr, it->nexthop});
        jt = it; ++jt;
        S.erase(it); it = jt;
    }
    for(int i = 0; i <= (1 << FAST_OFFSET); ++i) fastV[i] = lower_bound(V.data(), V.data() + V.size(), (VEntry) {i << (32 - FAST_OFFSET), 0});
}

unsigned query(unsigned addr)
{
    addr = htonl(addr);
    int tm = addr >> (32 - FAST_OFFSET);
    return lower_bound(fastV[tm], fastV[tm + 1], (VEntry) {addr + 1, 0})[-1].nexthop;
}

评测结果