代码

#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 leaf_push(int now,int f_nexthop)
{
    if (t[now].nexthop) f_nexthop = t[now].nexthop;
    if(t[now].ch[0]&&t[now].ch[1])
    {
        leaf_push(t[now].ch[0],f_nexthop);
        leaf_push(t[now].ch[1],f_nexthop);
    }
    else if (t[now].ch[0])
    {
        t[now].ch[1] = ++cnt;
        t[cnt].ch[0] = t[cnt].ch[1] = 0;
        t[cnt].nexthop = f_nexthop;
        leaf_push(t[now].ch[0],f_nexthop);
    }
    else if (t[now].ch[1])
    {
        t[now].ch[0] = ++cnt;
        t[cnt].ch[0] = t[cnt].ch[1] = 0;
        t[cnt].nexthop = f_nexthop;
        leaf_push(t[now].ch[1],f_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);
    leaf_push(0,0);
}

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].ch[c]) break;
        n = t[n].ch[c];
    }
    return t[n].nexthop;
}

评测结果