代码

#include "router.h"

namespace trie {

const unsigned MaxN = 2827088;

unsigned cnt;
unsigned ch[MaxN * 32 + 5][2];
unsigned val[MaxN * 32 + 5];

inline void insert(unsigned addr, unsigned char len, unsigned nexthop) {
  unsigned u = 0;
  for (int i = 31; i >= 32 - len; --i) {
    unsigned c = (addr >> i) & 1;
    if (ch[u][c] == 0) ch[u][c] = ++cnt;
    u = ch[u][c];
  }
  val[u] = nexthop;
}

inline unsigned query(unsigned addr) {
  int u = 0, res = 0;
  for (int i = 31; i >= 0; --i) {
    unsigned c = (addr >> i) & 1;
    if (ch[u][c] == 0) return res;
    u = ch[u][c];
    if (val[u] != 0) res = val[u];
  }
  return res;
}

}

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);
}

评测结果