提交记录 11337


用户 题目 状态 得分 用时 内存 语言 代码长度
Recursion router32. 测测你的路由器 Wrong Answer 25 404.417 ms 122624 KB C++ 1.43 KB
提交时间 评测时间
2019-11-24 16:36:12 2020-08-01 02:42:32
#include "router.h"
#include <stdint.h>
#include <stdlib.h>

class TrieNode {
public:
	TrieNode *child[2];
	RoutingTableEntry *entry;
	int len;
	
	TrieNode(int _len) {
		child[0] = child[1] = nullptr;
		entry = nullptr;
		len = _len;
	}
	~TrieNode() {
		delete child[0], child[1];
		delete entry;
	}
} *trieRoot = new TrieNode(0);

bool getBit(uint32_t addr, int pos) {
	if (pos < 8)
		return ((addr & 255) >> (7 - pos)) & 1;
	else if (pos < 16)
		return (((addr >> 8) & 255) >> (15 - pos)) & 1;
	else if (pos < 24)
		return (((addr >> 16) & 255) >> (23 - pos)) & 1;
	else
		return (((addr >> 24) & 255) >> (31 - pos)) & 1;
}

void update(bool insert, RoutingTableEntry entry) {
	TrieNode* node = trieRoot;
	for (int i = 0; i < entry.len; i++) {
		bool bit = getBit(entry.addr, i);
		if (node->child[bit] == nullptr) node->child[bit] = new TrieNode(i + 1);
		node = node->child[bit];
	}
	if (insert) {
		if (node->entry != nullptr) delete node->entry;
		node->entry = new RoutingTableEntry(entry);
	} else {
		delete node->entry;
		node->entry = nullptr;
	}
}

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

unsigned query(unsigned addr) {
	int nexthop = 0;
	TrieNode* node = trieRoot;
	for (int i = 0; i < 32; i++) {
		bool bit = getBit(addr, i);
		if (node->child[bit] == nullptr) return nexthop;
		node = node->child[bit];
		if (node->entry != nullptr) nexthop = node->entry->nexthop;
	}
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #112.22 us28 KBAcceptedScore: 25

Testcase #266.483 ms119 MB + 768 KBWrong AnswerScore: 0

Testcase #3235.62 ms119 MB + 768 KBWrong AnswerScore: 0

Testcase #4404.417 ms119 MB + 768 KBWrong AnswerScore: 0


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