提交记录 15127


用户 题目 状态 得分 用时 内存 语言 代码长度
tangh18 router32. 测测你的路由器 Compile Error 0 0 ns 0 KB C++11 3.28 KB
提交时间 评测时间
2020-11-28 22:47:44 2020-11-28 22:47:46
#include "router.h"

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

struct DictNode
{
  /* data */
  RoutingTableEntry e_;
  DictNode *parent = nullptr;
  DictNode *lc = nullptr; // 0
  DictNode *rc = nullptr; // 1
  bool isEntry = 0;
  bool isLeft = 1; // 1 left, 0 right
  int depth = 0;

  bool hasLc(){return lc != nullptr;}
  bool hasRc(){return rc != nullptr;}
  DictNode(){}
  DictNode(DictNode *p){this->parent = p;}
  DictNode(RoutingTableEntry e_){this->e_ = e_;}
  DictNode(RoutingTableEntry e_, DictNode *p){this->e_ = e_; this->parent = p;}
};
DictNode* root = new DictNode();

DictNode* find(unsigned addr, unsigned len){
  addr = big2little32(addr);
  // addr = truncated(addr, 32, 32 - len);
  int cur_depth = 0; // start from 1
  DictNode* cur_node = root;
  while (cur_depth <= len){
    cur_depth++;
    int digit = (1 << (32 - cur_depth));
    digit = addr & digit;
    if(digit){
      if(cur_node->hasRc()){
        cur_node = cur_node->rc;
        continue;
      }
    }
    else{
      if(cur_node->hasLc()){
        cur_node = cur_node->lc;
        continue;
      }
    }
    break;
  }
  return cur_node;
}

DictNode* findQuery(unsigned addr, unsigned len){
  DictNode* ans = root;
  addr = big2little32(addr);
  // addr = truncated(addr, 32, 32 - len);
  int cur_depth = 0; // start from 1
  DictNode* cur_node = root;
  while (cur_depth <= len){
    if(cur_node->isEntry)
      ans = cur_node;
    cur_depth++;
    int digit = (1 << (32 - cur_depth));
    digit = addr & digit;
    if(digit){
      if(cur_node->hasRc()){
        cur_node = cur_node->rc;
        continue;
      }
    }
    else{
      if(cur_node->hasLc()){
        cur_node = cur_node->lc;
        continue;
      }
    }
    break;
  }
  return ans;
}

void insertNode(RoutingTableEntry entry, DictNode* last){
  unsigned addr = big2little32(entry.addr);
  // addr = truncated(addr, 32, 32 - entry.len);
  int cur_depth = last->depth + 1;
  DictNode* cur_node = last;
  for(int i = cur_depth; i <= entry.len; i++){
    unsigned digit = (1 << (32 - i));
    digit = addr & digit;
    // printf("cur depth: %d, digit: %d, addr: %x\n", i, digit, addr);
    DictNode* node = new DictNode(cur_node);
    node->depth = i;
    if(digit){
      cur_node->rc = node;
      node->isLeft = 0;
    }
    else{
      cur_node->lc = node;
      node->isLeft = 1;
    }
    cur_node = node;
  }
  cur_node->e_ = entry;
  cur_node->isEntry = 1;
}

void deleteNode(DictNode *node, unsigned len){
  while(node->parent != nullptr){
    DictNode* fa = node->parent;
    if(
      (!(fa->hasLc() && fa->hasRc())) &&
      (!node->isEntry || node->depth == len)
    ){
      if(node->isLeft)
        fa->lc = nullptr;
      else
        fa->rc = nullptr;
      delete node;
      node = fa;
      continue;
    }
    break;
  }
}

void init(int n, int q, const RoutingTableEntry *a) {
	for(int i = 0; i < n; i++){
        unsigned addr = big2little32(a[i].addr);
        DictNode* cur = find(a[i]->addr, a[i]->len);
        insertNode(*a, cur);
    }
}

unsigned query(unsigned addr) {
  addr = big2little32(addr);
  DictNode* cur = findQuery(addr, 32);
  if(!cur->isEntry)
    return 0;
  else
    return big2little32(cur->e_.nexthop);
}

CompilationN/AN/ACompile ErrorScore: N/A


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 21:24:06 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用