代码

#include "router.h"

typedef struct {
  unsigned char len;
  unsigned nexthop;
  int next[2];
} TrieNode;

TrieNode trie[30000000];
int trie_index = 0;

unsigned ntohl(unsigned addr) {
  return (addr >> 24) + (((addr >> 16) & 0xff) << 8) +
         (((addr >> 8) & 0xff) << 16) + ((addr & 0xff) << 24);
}

void update(RoutingTableEntry entry) {
  entry.addr = ntohl(entry.addr);

  if (entry.addr == 0 && entry.len == 0) {
    trie[0].len = 1;
    trie[0].nexthop = entry.nexthop;
    return;
  }

  int ptr = 0;
  for (int i = 0; i < entry.len; i++) {
    int b = (entry.addr >> (31 - i)) & 1;
    if (trie[ptr].next[b] == 0) {
      trie[ptr].next[b] = ++trie_index;
    }
    ptr = trie[ptr].next[b];
  }
  trie[ptr].len = entry.len;
  trie[ptr].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) {
  addr = ntohl(addr);

  if (addr == 0 && trie[0].len == 1) {
    return trie[0].nexthop;
  }

  unsigned nexthop = 0;

  int ptr = 0;
  for (int i = 0; i < 32; i++) {
    int b = (addr >> (31 - i)) & 1;
    if (trie[ptr].next[b] == 0) {
      break;
    }
    ptr = trie[ptr].next[b];
    if (trie[ptr].len != 0) {
      nexthop = trie[ptr].nexthop;
    }
  }

  return nexthop;
}

评测结果