代码

#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;

void init(int n, int q, const RoutingTableEntry *a)
{
	set<MyEntry> S;
    S.insert((MyEntry) {0, 0, 0});
    for(int i = 0; i < n; i++) S.insert((MyEntry) {a->addr, a->len, a->nexthop});
    for(auto it = S.begin(); it != S.end(); ++it)
    {
        auto jt = it; ++jt;
        if(jt != S.end() && jt->addr == it->addr)
        {
            if(jt->len != it->len + 1) S.insert((MyEntry) {it->addr, it->len + 1, it->nexthop});
            S.insert((MyEntry) {it->addr | 1u << (31 - it->len), it->len + 1, it->nexthop});
        }
        else 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;
}

评测结果