#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(addr, unsigned(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 cur->e_.nexthop;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 11.86 us | 28 KB | Accepted | Score: 25 | 显示更多 |
Testcase #2 | 5.767 ms | 9 MB + 500 KB | Accepted | Score: 25 | 显示更多 |
Testcase #3 | 13.351 ms | 9 MB + 500 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #4 | 21.027 ms | 9 MB + 500 KB | Wrong Answer | Score: 0 | 显示更多 |