代码

#include "router.h"
#include <cstring>
#include <arpa/inet.h>

long long nexthop_trie[34000000];
long long *sub_trie[34000000];

unsigned Reverse(unsigned a)
{
    unsigned ret = 0;
    for (int cnt = 32; cnt > 0; a >>= 1, cnt--)
    {
        ret <<= 1;
        ret |= a&1;
    }
    return ret;
}

void init(int n, int q, const RoutingTableEntry *a) {
    memset(nexthop_trie, -1, sizeof(nexthop_trie));
    for (int i = 0; i < n; i++)
    {
        unsigned addr = Reverse(ntohl(a[i].addr));
        if (a[i].len > 24)
        {
            int cnt = 1;
            for (int l = 24; l > 0; l--)
            {
                cnt = cnt << 1 | (addr & 1);
                addr >>= 1;
            }
            if (sub_trie[cnt] == NULL)
            {
                sub_trie[cnt] = new long long[540];
                memset(sub_trie[cnt], -1, sizeof(long long) * 540);
            }
            int sub_cnt = 1;
            for (int l = a[i].len - 24; l > 0; l--)
            {
                sub_cnt = sub_cnt << 1 | (addr & 1);
                addr >>= 1;
            }
            sub_trie[cnt][sub_cnt] = a[i].nexthop;
        }
        else
        {
            int cnt = 1;
            for (int l = a[i].len; l > 0; l--)
            {
                cnt = cnt << 1 | (addr & 1);
                addr >>= 1;
            }
            nexthop_trie[cnt] = a[i].nexthop;
        }
    }
}

unsigned query(unsigned addr) {
    addr = Reverse(ntohl(addr));
    unsigned ret = 0;
    int cnt = 1;
    if (nexthop_trie[1] != -1)
        ret = nexthop_trie[1];
    for (int l = 24; l > 0; l--)
    {
        cnt = cnt << 1 | (addr & 1);
        addr >>= 1;
        if (nexthop_trie[cnt] != -1)
            ret = nexthop_trie[cnt];
    }
    if (sub_trie[cnt] != NULL)
    {
        int sub_cnt = 1;
        for (int l = 8; l > 0; l--)
        {
            sub_cnt = sub_cnt << 1 | (addr & 1);
            addr >>= 1;
            if (sub_trie[cnt][sub_cnt] != -1)
                ret = sub_trie[cnt][sub_cnt];
        }
    }
    return ret;
}

评测结果