代码

#include "router.h"
#include <arpa/inet.h>
struct Trie{
    struct node{
        node* son[2];
        unsigned via;
        node(){
            via=0;
            son[0]=nullptr;
            son[1]=nullptr;
        }
    };
    //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>>(31ul-i))&1ul;
            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 = root->via;
        bool x;
        for(int i=31;i>=0;i--)
        {
            x=addr>>i&1ul;
            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(htonl(a[i].addr),a[i].len,a[i].nexthop);
    }
}
unsigned query(unsigned addr){
    return trie.query(htonl(addr));
}

评测结果