提交记录 14358
提交时间 |
评测时间 |
2020-09-24 19:27:47 |
2020-09-24 19:27:54 |
#include "router.h"
#include <cstring>
#include <arpa/inet.h>
long long nexthop_trie1[34000000];
long long nexthop_trie8[18000000];
int nodefr8to1[18000000];
long long *sub_trie[18000000];
unsigned Reverse(unsigned a, int len = 32)
{
unsigned ret = 0;
for (int cnt = len; cnt > 0; a >>= 1, cnt--)
{
ret <<= 1;
ret |= a&1;
}
return ret;
}
void init(int n, int q, const RoutingTableEntry *a) {
memset(nexthop_trie1, -1, sizeof(nexthop_trie1));
memset(nexthop_trie8, -1, sizeof(nexthop_trie8));
for (int i = 0; i < n; i++)
{
if (a[i].len > 24)
{
unsigned addr = a[i].addr;
int cnt = 0;
for (int l = 8; l <= 24; l += 8)
{
cnt = cnt << 8 | (addr & 255);
cnt++;
addr >>= 8;
}
if (sub_trie[cnt] == NULL)
{
sub_trie[cnt] = new long long[540];
memset(sub_trie[cnt], -1, sizeof(long long) * 540);
}
int sub_cnt = 1;
addr = Reverse(addr, 8);
for (int l = 25; l <= a[i].len; l++)
{
sub_cnt = sub_cnt << 1 | (addr & 1);
addr >>= 1;
}
sub_trie[cnt][sub_cnt] = a[i].nexthop;
}
if (a[i].len <= 24)
{
int cnt8 = 0;
if (a[i].len % 8 == 0)
{
unsigned addr = a[i].addr;
int cnt = 0;
for (int l = 8; l <= a[i].len; l += 8)
{
cnt = cnt << 8 | (addr & 255);
cnt++;
addr >>= 8;
}
nexthop_trie8[cnt] = a[i].nexthop;
cnt8 = cnt;
}
unsigned addr = Reverse(ntohl(a[i].addr));
int cnt = 1;
for (int l = 1; l <= a[i].len; l++)
{
cnt = cnt << 1 | (addr & 1);
addr >>= 1;
}
nexthop_trie1[cnt] = a[i].nexthop;
if (a[i].len % 8 == 0)
nodefr8to1[cnt8] = cnt;
}
}
}
unsigned query(unsigned addr_in) {
unsigned addr = addr_in;
unsigned ret = 0;
int cnt = 0;
int len = 0;
int cnt8 = 0;
if (nexthop_trie8[0] != -1)
ret = nexthop_trie8[0];
for (int l = 8; l <= 24; l += 8)
{
cnt = cnt << 8 | (addr & 255);
cnt++;
addr >>= 8;
if (nexthop_trie8[cnt] != -1)
{
ret = nexthop_trie8[cnt];
cnt8 = cnt;
len = l;
}
}
if (sub_trie[cnt] != NULL)
{
int sub_cnt = 1;
addr = Reverse(addr, 8);
for (int l = 25; l <= 32; l++)
{
sub_cnt = sub_cnt << 1 | (addr & 1);
addr >>= 1;
if (sub_trie[cnt][sub_cnt] != -1)
{
len = l;
ret = sub_trie[cnt][sub_cnt];
}
}
}
if (len < 24)
{
addr = Reverse(ntohl(addr_in)) >> len;
cnt = nodefr8to1[cnt8];
for (int l = len + 1; l <= 24; l++)
{
cnt = cnt << 1 | (addr & 1);
addr >>= 1;
if (len < l && nexthop_trie1[cnt] != -1)
{
ret = nexthop_trie1[cnt];
len = l;
}
}
}
return ret;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 33.174 ms | 396 MB + 780 KB | Accepted | Score: 25 | 显示更多 |
Testcase #2 | 68.823 ms | 459 MB + 28 KB | Accepted | Score: 25 | 显示更多 |
Testcase #3 | 314.461 ms | 459 MB + 28 KB | Accepted | Score: 25 | 显示更多 |
Testcase #4 | 552.313 ms | 459 MB + 28 KB | Accepted | Score: 25 | 显示更多 |
Judge Duck Online | 评测鸭在线
Server Time: 2024-04-24 05:35:08 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用