代码

#include "router.h"
#include <stdlib.h>
#include <string.h>

static unsigned *ch0, *ch1, *nh; // nh stores (nexthop+1), 0 = none
static unsigned cnt;

void init(int n, int q, const RoutingTableEntry *a) {
    size_t maxn = (size_t)n * 33 + 2;
    ch0 = (unsigned*)malloc(maxn * sizeof(unsigned));
    ch1 = (unsigned*)malloc(maxn * sizeof(unsigned));
    nh  = (unsigned*)malloc(maxn * sizeof(unsigned));
    memset(ch0, 0, maxn * sizeof(unsigned));
    memset(ch1, 0, maxn * sizeof(unsigned));
    memset(nh,  0, maxn * sizeof(unsigned));
    cnt = 1; // root = node 1
    for (int i = 0; i < n; i++) {
        unsigned ip = __builtin_bswap32(a[i].addr);
        unsigned len = a[i].len;
        unsigned h = a[i].nexthop;
        unsigned node = 1;
        for (unsigned b = 0; b < len; b++) {
            unsigned bit = (ip >> (31 - b)) & 1u;
            unsigned *c = bit ? &ch1[node] : &ch0[node];
            if (*c == 0) *c = ++cnt;
            node = *c;
        }
        nh[node] = h + 1;
    }
}

unsigned query(unsigned addr) {
    unsigned ip = __builtin_bswap32(addr);
    unsigned node = 1, best = nh[1];
    for (int b = 0; b < 32; b++) {
        unsigned bit = (ip >> (31 - b)) & 1u;
        unsigned c = bit ? ch1[node] : ch0[node];
        if (c == 0) break;
        node = c;
        unsigned h = nh[node];
        if (h) best = h;
    }
    return best ? best - 1 : 0;
}

评测结果