代码

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

struct MyEntry
{
    unsigned addr, len, nexthop;
};
bool operator<(const MyEntry &a, const MyEntry &b)
{
    if(a.addr != b.addr) return a.addr < b.addr;
    return a.len < b.len;
}

vector<pair<unsigned, unsigned>> V;
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((MyEntry) {a[i].addr, a[i].len, a[i].nexthop});
    S.insert((MyEntry) {0, 0, 0});
    for(auto it = S.begin(); it != S.end(); ++it)
    {
        auto jt = it; ++jt;
        // printf("S %u %u\n", it->addr, it->len);
        // printf("j %u %u\n", jt->addr, it->addr + pow2(32 - it->len) - 1u);
        if(jt != S.end() && jt->addr <= it->addr + pow2(32 - it->len) - 1u)
        {
            S.insert((MyEntry) {it->addr, it->len + 1, it->nexthop});
            S.insert((MyEntry) {it->addr | pow2(31 - it->len), it->len + 1, it->nexthop});
        }
        else
        {
            // printf("V %u %u\n", it->addr, it->nexthop);
            V.push_back(make_pair(it->addr, it->nexthop));
        }
    }
}

unsigned query(unsigned addr)
{
    return lower_bound(V.begin(), V.end(), make_pair(addr, ~0u))[-1].second;
}

评测结果