提交记录 14382
提交时间 |
评测时间 |
2020-09-26 15:55:13 |
2020-09-26 15:55:20 |
#include "router.h"
#include <stdint.h>
#include <netinet/in.h>
#include <new>
#include <unordered_set>
inline uint32_t mask(unsigned char len) {
return len == 0 ? 0 : ((~0) << (32 - len));
}
struct Node {
uint32_t prefix;
unsigned char len;
bool valid;
Node *next[2];
} *pool = 0, *pool_end = 0;
const size_t ALLOC_AMOUNT = 1 << 20;
Node *alloc() {
if (pool == pool_end) {
pool = new Node[ALLOC_AMOUNT];
pool_end = pool + ALLOC_AMOUNT;
}
return pool ++;
}
Node *root = 0;
Node *trie_find(uint32_t addr, unsigned char lenlim = 32, bool validonly = true) {
Node *found = 0;
for (Node *cur = root; cur;) {
if ((addr & mask(cur->len)) != (cur->prefix & mask(lenlim))) break;
if (! validonly || cur->valid) found = cur;
if (cur->len >= lenlim) break;
size_t b = (addr & (1 << (31 - cur->len))) ? 1 : 0;
cur = cur->next[b];
}
return found;
}
void trie_add(uint32_t prefix, unsigned char len) {
Node *f = trie_find(prefix, len, false);
Node new_node { .prefix = prefix, .len = len, .valid = 1, .next { 0, 0 } };
if (f == 0) {
root = new(alloc()) Node(new_node);
} else {
if (f->len == len) {
f->valid = true;
} else if (f->len > len) {
size_t side = (f->prefix & (1 << (31 - len))) ? 1 : 0;
Node *saved = new(alloc()) Node(*f);
*f = new_node;
f->next[side] = saved;
} else {
size_t side = (prefix & (1 << (31 - f->len))) ? 1 : 0;
f->next[side] = new(alloc()) Node(new_node);
}
}
}
struct EntryHash {
size_t operator()(const RoutingTableEntry &entry) const {
return std::hash<uint64_t>()(
uint64_t(entry.addr) | (uint64_t(entry.len) << 32)
);
}
};
struct EntryEquals {
bool operator()(const RoutingTableEntry &a, const RoutingTableEntry &b) const {
return a.addr == b.addr && a.len == b.len;
}
};
std::unordered_set<RoutingTableEntry, EntryHash, EntryEquals> hash_table;
void init(int n, int q, const RoutingTableEntry *a) {
hash_table.reserve(n);
for (size_t i = 0; i < (size_t) n; i ++) {
trie_add(ntohl(a[i].addr), a[i].len);
hash_table.insert(a[i]);
}
}
unsigned query(unsigned addr) {
Node *node = trie_find(addr);
if (! node) return 0;
auto key = RoutingTableEntry {
.addr = htonl(node->prefix), .len = node->len
};
auto it = hash_table.find(key);
return it->nexthop;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 13.81 us | 28 KB | Accepted | Score: 25 | 显示更多 |
Testcase #2 | 143.647 ms | 72 MB + 664 KB | Accepted | Score: 25 | 显示更多 |
Testcase #3 | 160.732 ms | 72 MB + 664 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #4 | 177.578 ms | 72 MB + 664 KB | Wrong Answer | Score: 0 | 显示更多 |
Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 04:49:32 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用