代码

#include "router.h"
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <map>
#include <utility>

struct Node
{
    uint32_t nexthop;
    bool valid;
    Node *lc = nullptr;
    Node *rc = nullptr;
    Node(uint32_t nexthop)
    {
        this->nexthop = nexthop;
        this->valid = 0;
    }
};

struct DictTree
{
    Node *root = nullptr;
    void insert(RoutingTableEntry entry)
    {
        if (entry.len == 0)
            return;
        if (!root)
        {
            root = new Node(0);
        }
        uint32_t address = entry.addr;
        int len = entry.len;
        Node *cur = root;
        while (len)
        {
            if (address & 1)
            {
                if (cur->rc)
                    cur = cur->rc;
                else
                    cur->rc = new Node(0);
            }
            else
            {
                if (cur->lc)
                    cur = cur->lc;
                else
                    cur->lc = new Node(0);
            }
            address = address >> 1;
            --len;
        }
        cur->nexthop = entry.nexthop;
        cur->valid = 1;
    }
    Node *query(uint32_t address, int len)
    {
        Node *cur = root;
        Node *result = nullptr;
        while (len)
        {
            if (cur->valid)
                result = cur;
            if (address & 1)
            {
                if (cur->rc)
                    cur = cur->rc;
                else
                    return result;
            }
            else
            {
                if (cur->lc)
                    cur = cur->lc;
                else
                    return result;
            }
            address = address >> 1;
            --len;
        }
        return result;
    }
};

/*
  RoutingTable Entry 的定义如下：
  typedef struct {
    uint32_t addr; // 大端序，IPv4 地址
    uint32_t len; // 小端序，前缀长度
    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 **精确** 匹配。
 */
DictTree tree;

void init(int n, int q, const RoutingTableEntry *a)
{
    for (int i = 0; i < n; ++i)
    {
        tree.insert(a[i]);
    }
}

unsigned query(unsigned addr)
{
    Node *target = tree.query(addr, 32);
    if (target)
    {
        return target->nexthop;
    }
    return 0;
}

评测结果