代码

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

const int GG = 21;

const int IGG = 32 - GG;
const unsigned IGGM = (1u << IGG) - 1;

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

int top = 0;
unsigned shop[1 << (GG - 4)][1 << IGG];

void ins(unsigned addr, int len, unsigned nexthop)
{
    if(len <= GG)
    {
        addr >>= IGG;
        for(int T = 1 << (GG - len); T--; ++addr) table[addr].nexthop = nexthop;
    }
    else
    {
        unsigned &son = table[addr >> IGG].son;
        if(!son)
        {
            son = ++top;
            for(int i = 0; i < (1 << IGG); i++) shop[son][i] = table[addr >> IGG].nexthop;
        }
        addr &= IGGM;
        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 >> IGG];
    if(ent.son) return shop[ent.son][addr & IGGM];
    else return ent.nexthop;
}

评测结果