代码

#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)
{
    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(S.end(), (MyEntry) {htonl(a[i].addr), a[i].len, 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(make_pair(it->addr, it->nexthop));
        jt = it; ++jt;
        S.erase(it); it = jt;
    }
}

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

评测结果