代码

#pragma GCC optimize("Ofast,no-stack-protector")
#include "router.h"
#include <string.h>
#include <arpa/inet.h>

typedef struct
{
    unsigned *son;
    unsigned nexthop;
} VEntry;
VEntry 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);
}

struct Query
{
    unsigned lo: 24;
    unsigned hi: 8;
};

unsigned query(Query q)
{
    VEntry &ent = table[q.lo];
    if(ent.son) return ent.son[q.hi];
    else return ent.nexthop;
}

评测结果