代码

#include "router.h"

struct node
{
    int ch[2];
    unsigned nexthop;
}t[5000000];
int cnt = 0;

unsigned rev(unsigned x)
{
    unsigned ans = 0;
    for (int i=0;i<4;++i)
    {
        ans <<= 8;
        ans |= (x & 0xff);
        x >>= 8;
    }
    return ans;
}

void ins(unsigned addr, unsigned char len, unsigned nexthop)
{
    int now = 0;
    for (int i=0;i<len;++i)
    {
        int c = (addr >> (31 - i)) & 1;
        if (!t[now].ch[c])
        {
            t[now].ch[c] = ++cnt;
            t[cnt].ch[0] = t[cnt].ch[1] = 0;
            t[cnt].nexthop = 0;
        }
        now = t[now].ch[c];
    }
    t[now].nexthop = nexthop;
}

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

unsigned query(unsigned addr) 
{
    addr = rev(addr);
    unsigned ans = 0;
    int n = 0;
    for (int i=0;i<32;++i)
    {
        int c = (addr >> (31 - i)) & 1;
        if (t[n].nexthop) ans = t[n].nexthop;
        if (!t[n].ch[c]) break;
        n = t[n].ch[c];
    }
    return ans;
}

评测结果