代码

#include "router.h"
struct RoutingTableNode {
    RoutingTableNode *nx[2];
    bool hasRoute;
    unsigned int nexthop;
    RoutingTableNode() {
        nx[0] = nx[1] = nullptr;
        hasRoute = false;
    }
    ~RoutingTableNode() {
        if (nx[0]) {
            delete nx[0];
        }
        if (nx[1]) {
            delete nx[1];
        }
    }
} *root = nullptr;
void init(int n, int q, const RoutingTableEntry *a) {
    root = new RoutingTableNode();
    for (int i = 0; i < n; i++) {
        RoutingTableNode *now = root;
        unsigned int addr = a[i].addr;
        addr = ((addr & 0xffff) << 16) | (addr >> 16); // 2143
        addr = ((addr & 0x00ff00ff) << 8) | ((addr & 0xff00ff00) >> 8); //1234
        for (int i = 0; i < a[i].len; i++) {
            int nw = (addr & 0x80000000) != 0 ;
            addr <<= 1;
            if (!now->nx[nw]) {
                now->nx[nw] = new RoutingTableNode();
            }
            now = now->nx[nw];
        }
        now->hasRoute = true;
        now->nexthop = a[i].nexthop;
    }
}

unsigned query(unsigned addr) {
    RoutingTableNode *now = root;
    addr = ((addr & 0xffff) << 16) | (addr >> 16); // 2143
    addr = ((addr & 0x00ff00ff) << 8) | ((addr & 0xff00ff00) >> 8); //1234
    RoutingTableNode *found = nullptr;
    if (now->hasRoute) {
        found = now;
    }
    for (int i = 0; i < 32; i++) {
        int nw = (addr & 0x80000000) != 0;
        addr <<= 1;
        if (!now->nx[nw]) {
            break;
        }
        now = now->nx[nw];
        if (now->hasRoute) {
            found = now;
        }
    }
    if (!found) {
        return 0;
    }
    return found->nexthop;
}

评测结果