代码

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

unsigned table[1 << 25];

int top = 0;
unsigned shop[0x100000][128];

void ins(unsigned addr, int len, unsigned nexthop)
{
    if(len <= 25)
    {
        addr >>= 7;
        for(int T = 1 << (25 - len); T--; ++addr) table[addr] = nexthop;
    }
    else
    {
        unsigned &son = table[addr >> 7];
        if(son<0xfff00000)
        {
            --top;
            for(int i = 0; i < 128; i++) shop[top+0x100000][i] = son; son=top;
        }
        addr &= 127u;
        for(int T = 1 << (32 - len); T--; ++addr) shop[son+0x100000][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);
    unsigned ent = table[addr >> 7];
    if(ent>0xfff00000) return shop[ent+0x100000][addr & 127u];
    else return ent;
}

评测结果