代码

#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 >> 24) + (((addr >> 16) & 0xff) << 8) +
         (((addr >> 8) & 0xff) << 16) + ((addr & 0xff) << 24);
        for (int i = 0; i < a[i].len; i++) {
            bool nw = addr & 0x80000000;
            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 >> 24) + (((addr >> 16) & 0xff) << 8) +
         (((addr >> 8) & 0xff) << 16) + ((addr & 0xff) << 24);
    RoutingTableNode *found = nullptr;
    if (now->hasRoute) {
        found = now;
    }
    for (int i = 0; i < 32; i++) {
        bool nw = addr & 0x80000000;
        addr <<= 1;
        if (!now->nx[nw]) {
            if (!found) {
                return 0;
            }
            return found->nexthop;
        }
        now = now->nx[nw];
        if (now->hasRoute) {
            found = now;
        }
    }
    if (!found) {
        return 0;
    }
    return found->nexthop;
}

评测结果