代码

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

unsigned inv24(unsigned x)
{
    char a[4]; memcpy(a, &x, sizeof(a));
    swap(a[0], a[2]); memcpy(&x, a, sizeof(a));
    return x;
}

void ins(unsigned addr, int len, unsigned nexthop)
{
    if(len <= 24)
    {
        addr >>= 8;
        for(int T = 1 << (24 - len); T--; ++addr) table[inv24(addr)].nexthop = nexthop;
    }
    else
    {
        unsigned key = inv24(addr >> 8);
        unsigned *&son = table[key].son;
        if(!son)
        {
            son = shop[++top];
            for(int i = 0; i < 256; i++) son[i] = table[key].nexthop;
        }
        addr &= 255u;
        for(int T = 1 << (32 - len); T--; ++addr) 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)
{
    VEntry &ent = table[addr & 0xffffffu];
    if(ent.son) return ent.son[addr >> 24];
    else return ent.nexthop;
}

评测结果