提交记录 11337
提交时间 |
评测时间 |
2019-11-24 16:36:12 |
2020-08-01 02:42:32 |
#include "router.h"
#include <stdint.h>
#include <stdlib.h>
class TrieNode {
public:
TrieNode *child[2];
RoutingTableEntry *entry;
int len;
TrieNode(int _len) {
child[0] = child[1] = nullptr;
entry = nullptr;
len = _len;
}
~TrieNode() {
delete child[0], child[1];
delete entry;
}
} *trieRoot = new TrieNode(0);
bool getBit(uint32_t addr, int pos) {
if (pos < 8)
return ((addr & 255) >> (7 - pos)) & 1;
else if (pos < 16)
return (((addr >> 8) & 255) >> (15 - pos)) & 1;
else if (pos < 24)
return (((addr >> 16) & 255) >> (23 - pos)) & 1;
else
return (((addr >> 24) & 255) >> (31 - pos)) & 1;
}
void update(bool insert, RoutingTableEntry entry) {
TrieNode* node = trieRoot;
for (int i = 0; i < entry.len; i++) {
bool bit = getBit(entry.addr, i);
if (node->child[bit] == nullptr) node->child[bit] = new TrieNode(i + 1);
node = node->child[bit];
}
if (insert) {
if (node->entry != nullptr) delete node->entry;
node->entry = new RoutingTableEntry(entry);
} else {
delete node->entry;
node->entry = nullptr;
}
}
void init(int n, int q, const RoutingTableEntry *a) {
for (int i = 0; i < n; i++) update(true, a[i]);
}
unsigned query(unsigned addr) {
int nexthop = 0;
TrieNode* node = trieRoot;
for (int i = 0; i < 32; i++) {
bool bit = getBit(addr, i);
if (node->child[bit] == nullptr) return nexthop;
node = node->child[bit];
if (node->entry != nullptr) nexthop = node->entry->nexthop;
}
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 12.22 us | 28 KB | Accepted | Score: 25 | 显示更多 |
Testcase #2 | 66.483 ms | 119 MB + 768 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #3 | 235.62 ms | 119 MB + 768 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #4 | 404.417 ms | 119 MB + 768 KB | Wrong Answer | Score: 0 | 显示更多 |
Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 03:01:18 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用