代码

#include "router.h"
#include <cstdint>

#define NCHILD 2

#define BIT_BE32(x, b) ((__builtin_bswap32(x) & (1 << (32 - (b)))) ? 1 : 0)

class TrieNode {
  public:
    TrieNode *child[NCHILD] = {nullptr};

    bool end;
    unsigned nexthop;

    TrieNode() {
        this->end = false;
    }
};

TrieNode root;

void insert(RoutingTableEntry entry) {
    TrieNode *p = &root;

    for(int i = 0; i < entry.len; i++) {
        int v = BIT_BE32(entry.addr, i);
        if(p->child[v] == nullptr) {
            p->child[v] = new TrieNode();
        }

        p = p->child[v];
    }

    p->end = true;
    p->nexthop = entry.nexthop;
}

void init(int n, int q, const RoutingTableEntry *a) {
    root.end = false;
    for(int i = 0; i < n; i++) {
        insert(a[i]);
    }
}

unsigned query(unsigned addr) {
    TrieNode *p = &root;

    for(int i = 0; i < 32; i++) {
        int v = BIT_BE32(addr, i);
        if(p->child[v] != nullptr) {
            p = p->child[v];
        } else if(p->end) {
            return p->nexthop;
        } else {
            return 0;
        }
    }

    return 0;
}

评测结果