代码

#pragma GCC optimize("Ofast,no-stack-protector")
#include "router.h"
#include <bits/stdc++.h>
#include <arpa/inet.h>
using namespace std;

struct VEntry
{
    unsigned son;
    unsigned nexthop;
} table[1 << 24];

int top = 0;
unsigned shop[1 << 20][256];

void ins(unsigned addr, int len, unsigned nexthop)
{
    if(len <= 24)
    {
        addr >>= 8;
        for(int T = 1 << (24 - len); T--; ++addr) table[addr].nexthop = nexthop;
    }
    else
    {
        unsigned &son = table[addr >> 8].son;
        if(!son)
        {
            son = ++top;
            for(int i = 0; i < 256; i++) shop[son][i] = table[addr >> 8].nexthop;
        }
        addr &= 255u;
        for(int T = 1 << (32 - len); T--; ++addr) shop[son][addr] = nexthop;
    }
}

void init(int n, int q, const RoutingTableEntry *a)
{
    for(int i = 0; i < n; i++) ins(htonl(a[i].addr), a[i].len, a[i].nexthop);
}

unsigned query(unsigned addr)
{
    addr = htonl(addr);
    VEntry &ent = table[addr >> 8];
    if(ent.son) return shop[ent.son][addr & 255u];
    else return ent.nexthop;
}

评测结果