提交记录 11267


用户 题目 状态 得分 用时 内存 语言 代码长度
zx1239856 router32. 测测你的路由器 Wrong Answer 50 173.154 ms 41900 KB C++ 1.63 KB
提交时间 评测时间
2019-11-11 01:53:29 2020-08-01 02:41:08
#include "router.h"
#include <stdint.h>
#include <stdlib.h>
#include <arpa/inet.h>
#include <unordered_map>

/*
  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 为零时这是一条直连路由。
  你可以在全局变量中把路由表以一定的数据结构格式保存下来。
*/

typedef struct {
    uint32_t if_index;
    uint32_t nexthop;
} SimpleEntry;

std::unordered_map<uint32_t, SimpleEntry> table_entries;

#define DUCK_OJ
#ifdef DUCK_OJ
void init(int n, int q, const RoutingTableEntry *a)
{
  for(int i = 0; i < n; ++i)
  {
    uint32_t addr = ntohl(a[i].addr) & (0xffffffff << (32 - a[i].len));
    table_entries[addr] = { 0, a[i].nexthop };
  }
}

unsigned query(unsigned addr)
{
  for(int i = 32; i > 0; --i) {
    uint32_t addr = addr & (0xffffffff << (32 - i));
    auto it = table_entries.find(addr);
    if(it != table_entries.end())
      return (*it).second.nexthop;
  }
  return 0;
}

#endif

/**
 * @brief 插入/删除一条路由表表项
 * @param insert 如果要插入则为 true ,要删除则为 false
 * @param entry 要插入/删除的表项
 * 
 * 插入时如果已经存在一条 addr 和 len 都相同的表项,则替换掉原有的。
 * 删除时按照 addr 和 len 匹配。
 */
void update(bool isInsert, RoutingTableEntry entry)
{

}

/**
 * @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;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #114.94 us24 KBAcceptedScore: 25

Testcase #2137.612 ms40 MB + 940 KBAcceptedScore: 25

Testcase #3155.577 ms40 MB + 940 KBWrong AnswerScore: 0

Testcase #4173.154 ms40 MB + 940 KBWrong AnswerScore: 0


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