代码

#include "router.h"

typedef struct {
  RoutingTableEntry entry;
  int next[2];
} TrieNode;

TrieNode trie[1000000];
int index = 0;

void update(RoutingTableEntry entry) {
  int ptr = 0;
  for (int i = 0; i < entry.len; i++) {
    int b = (entry.addr >> i) & 0x1;
    if (trie[ptr].next[b] == 0) {
      trie[ptr].next[b] = ++index;
      ptr = index;
      trie[ptr].entry.addr = entry.addr & ((1 << (i + 1)) - 1);
    } else {
      ptr = trie[ptr].next[b];
    }
  }
  trie[ptr].entry.len = entry.len;
  trie[ptr].entry.nexthop = entry.nexthop;
}

void init(int n, int q, const RoutingTableEntry *a) {
  for (int i = 0; i < n; i++) {
    update(a[i]);
  }
}

unsigned query(unsigned addr) { return 0; }

评测结果