代码

#include "router.h"
struct Trie{
    struct node{
        node* son[2];
        unsigned via;
    };
    const int id[32]={7,6,5,4,3,2,1,0,15,14,13,12,11,10,9,8,23,22,21,20,19,18,17,16,31,30,29,28,27,26,25,24};
    node *root;
    void insert(unsigned addr,int len,unsigned nxt){
        if(root==nullptr)
        {
            root = new node();
        }
        node *tmp=root;
        bool x;
        for(int i=0;i<len;i++)
        {
            x=addr>>id[i]&1;
            if(tmp->son[x]==nullptr)
                tmp->son[x] = new node();
            tmp=tmp->son[x];
        }
        tmp->via=nxt;
    }
    unsigned query(unsigned addr){
        node *tmp=root;
        unsigned ans = 0;
        bool x;
        for(int i=0;i<32;i++)
        {
            x=addr>>id[i]&1;
            if(tmp->son[x]==nullptr) return ans;
            tmp=tmp->son[x];
            if(tmp->via!=0)
                ans=tmp->via;
        }
        return ans;
    }
}trie;
void init(int n, int q, const RoutingTableEntry *a){
    for(int i=0;i<n;i++){
        trie.insert(a[i].addr,a[i].len,a[i].nexthop);
    }
}
unsigned query(unsigned addr){
    return trie.query(addr);
}

评测结果