提交记录 14382


用户 题目 状态 得分 用时 内存 语言 代码长度
dram router32. 测测你的路由器 Wrong Answer 50 177.578 ms 74392 KB C++ 2.49 KB
提交时间 评测时间
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;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #113.81 us28 KBAcceptedScore: 25

Testcase #2143.647 ms72 MB + 664 KBAcceptedScore: 25

Testcase #3160.732 ms72 MB + 664 KBWrong AnswerScore: 0

Testcase #4177.578 ms72 MB + 664 KBWrong AnswerScore: 0


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