提交记录 11278


用户 题目 状态 得分 用时 内存 语言 代码长度
function2 router32. 测测你的路由器 Accepted 100 292.258 ms 67768 KB C++11 1.44 KB
提交时间 评测时间
2019-11-12 13:35:48 2020-08-01 02:41:15
#include <stdint.h>
#include <cstdlib>
#include <iostream>
#include <utility>
#include "router.h"

static uint32_t rev_bytes(const uint32_t &val) {
    return (val & 0xff) << 24 | (val & 0xff00) << 8 | (val & 0xff0000) >> 8 |
           (val & 0xff000000) >> 24;
}

struct RouterTable {
    struct node_t {
        node_t *ch[2];
        uint32_t nexthop;
        bool val;

        node_t() {
            ch[0] = ch[1] = nullptr;
            val = 0;
        }
    };
    node_t *root = nullptr;

    void insert(const RoutingTableEntry &entry) {
        auto addr = rev_bytes(entry.addr);
        if (!root) root = new node_t;
        auto u = root;
        for (int i = 0; i < entry.len; i++) {
            auto &v = u->ch[addr >> (31 - i) & 1];
            if (!v) v = new node_t;
            u = v;
        }
        u->val = 1;
        u->nexthop = entry.nexthop;
    }

    const node_t *query(uint32_t addr) {
        addr = rev_bytes(addr);
        if (!root) return nullptr;
        const node_t *ret = root->val ? root : nullptr;
        auto u = root;
        for (int i = 31; i >= 0; i--) {
            u = u->ch[addr >> i & 1];
            if (!u) break;
            if (u->val) ret = u;
        }
        return ret;
    }
};
static RouterTable table;

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

unsigned query(unsigned addr) {
	auto node = table.query(addr);
    return node ? node->nexthop : 0u;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #138.97 us36 KBAcceptedScore: 25

Testcase #247.154 ms66 MB + 184 KBAcceptedScore: 25

Testcase #3170.128 ms66 MB + 184 KBAcceptedScore: 25

Testcase #4292.258 ms66 MB + 184 KBAcceptedScore: 25


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