代码

#include "router.h"

unsigned big2little32(unsigned big){
  big = unsigned(big);
  return (
    ((big & 0xff000000) >> 24) |
    ((big & 0x00ff0000) >> 8) |
    ((big & 0x0000ff00) << 8) |
    ((big & 0x000000ff) << 24) 
  );
}

struct DictNode
{
  /* data */
  DictNode* child[2];
  DictNode* fa = nullptr;
  RoutingTableEntry entry;
  bool isEntry = false;

  DictNode(){child[0] = child[1] = nullptr;}
  DictNode(DictNode* fa){this->fa = fa; DictNode();}
};

DictNode* root = new DictNode();

void insertNode(RoutingTableEntry entry, unsigned addr, unsigned len){
  DictNode* cur_node = root;
  addr = big2little32(addr);
  for(int i = 0; i < len; i++){
    int digit = 0x1 & (((unsigned)addr) >> (31 - i));
    // printf("cur digit: %d, cur pos: %d\n", digit, i);
    if(cur_node->child[digit] == nullptr){
      DictNode* node = new DictNode();
      cur_node->child[digit] = node;
    }
    cur_node = cur_node->child[digit];
  }
  cur_node->isEntry = 1;
  cur_node->entry = entry;
}

DictNode* queryNode(unsigned addr){
  DictNode* cur_node = root;
  DictNode* ans = root;
  addr = big2little32(addr);
  for(int i = 0; i < 32; i++){
    int digit = 0x1 & (((unsigned)addr) >> (31 - i));
    // printf("cur digit: %d, cur pos: %d\n", digit, i);
    if(cur_node->child[digit] != nullptr){
      cur_node = cur_node->child[digit];
      if(cur_node->isEntry)
        ans = cur_node;
      continue;
    }
    break;
  }
  return ans;
}

void deleteNode(unsigned addr, unsigned len){
  DictNode* cur_node = root;
  addr = big2little32(addr);
  bool isFound = false;
  for(int i = 0; i < len; i++){
    int digit = 0x1 & (((unsigned)addr) >> (31 - i));
    if(cur_node->child[digit] != nullptr){
      cur_node = cur_node->child[digit];
      if(i == len - 1){
        isFound = true;
      }
      continue;
    }
    else
      break;
  }
  if(isFound){
    cur_node->isEntry = false;
    while(cur_node->fa != nullptr){
      DictNode* fa = cur_node->fa;
      if(
        !(fa->child[0] != nullptr && fa->child[1] != nullptr) &&
        (!cur_node->isEntry)
      ){
        delete cur_node;
        cur_node = fa;
        continue;
      }
      break;
    }
  }
}

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

unsigned query(unsigned addr) {
  DictNode* cur = queryNode(addr);
  if(!cur->isEntry)
    return 0;
  else
    return cur->entry.nexthop;
}

评测结果