代码

#include "router.h"
#include <bits/stdc++.h>
#include <arpa/inet.h>
using namespace std;

// tbl1中的0后面跟一串1的话，就表示什么都没有！
// 需要满足：2^z >= n
// const int x = 18, y = 4, z = 4;
const int x = 26, y = 20, z = 20;
unsigned tbl1[1 << x], tbl2[1 << y + 32 - x], nha[1 << z];

void print2(unsigned x, int len) {
    for (int i = len; i--;)
        putchar('0' ^ x >> i & 1);
}

// O(3^x + 3^{32 - x + y}) + 32 * n)
// 当然，这是极端情况，现实情况下可能不会这么差。
void init(int n, int q, const RoutingTableEntry *a)
{
    fill(tbl1, tbl1 + (1 << x), (1 << z) - 1);
    fill(tbl2, tbl2 + (1 << y + 32 - x), (1 << z) - 1);
    int nid = 0, tbl2id = 0;
    for (int len = 32; len >= 0; --len)
        for (int i = n; i--;)
            if (a[i].len == len)
            {
                nha[nid] = a[i].nexthop;

                unsigned addr = htonl(a[i].addr);
                if (a[i].len <= x)
                {
                    int start1 = addr >> 32 - x;
                    for (int j = 1 << x - a[i].len; j--;)
                        if (tbl1[start1 + j] == (1 << z) - 1)
                            tbl1[start1 + j] = nid;
                        else if (tbl1[start1 + j] >> y == 1)
                        {
                            int start2 = (tbl1[start1 + j] & (1 << y) - 1) << 32 - x;
                            for (int k = 1 << 32 - x; k--;)
                                if (tbl2[start2 + k] == (1 << z) - 1)
                                    tbl2[start2 + k] = nid;
                        }
                }
                else
                {
                    int start1 = addr >> 32 - x, start2;
                    if (tbl1[start1] == (1 << z) - 1)
                    {
                        start2 = tbl2id;
                        tbl1[start1] = 1 << y | start2;
                        ++tbl2id;
                    }
                    else
                        start2 = tbl1[start1] & (1 << y) - 1;
                    start2 = start2 << 32 - x | addr & (1 << 32 - x) - 1;
                    for (int k = 1 << 32 - a[i].len; k--;)
                        if (tbl2[start2 + k] == (1 << z) - 1)
                            tbl2[start2 + k] = nid;
                }

                ++nid;
            }
}

unsigned query(unsigned addr)
{
    addr = htonl(addr);
    unsigned entry1 = tbl1[addr >> 32 - x];
    if (entry1 == (1 << z) - 1)
        return 0;
    else if (entry1 >> y == 0)
        return nha[entry1];
    else
    {
        int tbl2id = (entry1 & (1 << y) - 1) << 32 - x | addr & (1 << 32 - x) - 1;
        if (tbl2[tbl2id] == (1 << z) - 1)
            return 0;
        else
            return nha[tbl2[tbl2id]];
    }
}

评测结果