提交记录 11257
提交时间 |
评测时间 |
2019-11-11 00:38:19 |
2020-08-01 02:40:58 |
#include "router.h"
#include <stdint.h>
#include <stdlib.h>
#include <arpa/inet.h>
#include <vector>
#define DUCK
#ifdef DUCK
struct TrieNode {
uint32_t next_hop;
uint32_t child[2];
bool valid;
};
constexpr uint32_t MAX_SIZE = 827088;
std::vector<TrieNode> trie_buffer;
void init(int n, int q, const RoutingTableEntry *a) {
trie_buffer.reserve(MAX_SIZE * 32);
trie_buffer.resize(1);
for(int i = 0; i < n; ++i) {
uint32_t addr = ntohl(a[i].addr);
uint32_t len = a[i].len;
uint32_t curr = 0;
while(len) {
bool dir = (addr >> (--len)) & 1;
if(!trie_buffer[curr].child[dir]) {
trie_buffer[curr].child[dir] = trie_buffer.size();
trie_buffer.resize(trie_buffer.size() + 1);
}
curr = trie_buffer[curr].child[dir];
}
trie_buffer[curr].valid = true;
trie_buffer[curr].next_hop = a[i].nexthop;
}
}
unsigned query(unsigned addr) {
addr = ntohl(addr);
uint32_t curr = 0, len = 32;
while(len) {
bool dir = (addr >> (--len)) & 1;
if(trie_buffer[curr].child[dir]) {
curr = trie_buffer[curr].child[dir];
} else break;
}
if(trie_buffer[curr].valid)
return trie_buffer[curr].next_hop;
else
return 0;
}
#else
/*
RoutingTable Entry 的定义如下:
typedef struct {
uint32_t addr; // 大端序,IPv4 地址
uint32_t len; // 小端序,前缀长度
uint32_t if_index; // 小端序,出端口编号
uint32_t nexthop; // 大端序,下一跳的 IPv4 地址
} RoutingTableEntry;
约定 addr 和 nexthop 以 **大端序** 存储。
这意味着 1.2.3.4 对应 0x04030201 而不是 0x01020304。
保证 addr 仅最低 len 位可能出现非零。
当 nexthop 为零时这是一条直连路由。
你可以在全局变量中把路由表以一定的数据结构格式保存下来。
*/
/**
* @brief 插入/删除一条路由表表项
* @param insert 如果要插入则为 true ,要删除则为 false
* @param entry 要插入/删除的表项
*
* 插入时如果已经存在一条 addr 和 len 都相同的表项,则替换掉原有的。
* 删除时按照 addr 和 len 匹配。
*/
void update(bool insert, RoutingTableEntry entry) {
// TODO:
}
/**
* @brief 进行一次路由表的查询,按照最长前缀匹配原则
* @param addr 需要查询的目标地址,大端序
* @param nexthop 如果查询到目标,把表项的 nexthop 写入
* @param if_index 如果查询到目标,把表项的 if_index 写入
* @return 查到则返回 true ,没查到则返回 false
*/
bool query(uint32_t addr, uint32_t *nexthop, uint32_t *if_index) {
// TODO:
*nexthop = 0;
*if_index = 0;
return false;
}
#endif
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 11.58 us | 28 KB | Accepted | Score: 25 | 显示更多 |
Testcase #2 | 65.395 ms | 20 MB + 472 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #3 | 193.829 ms | 20 MB + 472 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #4 | 321.936 ms | 20 MB + 472 KB | Wrong Answer | Score: 0 | 显示更多 |
Judge Duck Online | 评测鸭在线
Server Time: 2024-04-20 09:30:43 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用