QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#99803 | #6354. 4 | whatever | WA | 3ms | 14260kb | C++17 | 1.6kb | 2023-04-23 19:20:48 | 2023-04-23 19:23:03 |
Judging History
answer
#include <cstdio>
#include <queue>
#include <vector>
#include <bitset>
#include <functional>
#include <algorithm>
#define pb push_back
#define ull unsigned long long
using std::bitset;
using std::vector;
using std::priority_queue;
const int N=100005;
int n, m, deg[N], id[N], top;
ull bs[N/8][N/8/64+5], ans;
bitset<N> rs[N];
vector<int> e[N], f[N], g[N];
inline void set(ull *a, int x)
{
a[x>>8]|=(1ull<<(x&63));
}
inline int ask(ull *a, ull *b, int lim)
{
int ret=0;
for(int i=0; i<=lim; ++i) ret+=__builtin_popcountll(a[i]&b[i]);
return ret;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=1, x, y; i<=m; ++i) scanf("%d%d", &x, &y), e[x].pb(y), rs[x].set(y), rs[y].set(x), ++deg[x], ++deg[y];
for(int i=1; i<=n; ++i) for(int x:e[i])
{
if(deg[x]<deg[i]) f[x].pb(i), g[i].pb(x);
else f[i].pb(x), g[x].pb(i);
}
for(int u=1; u<=n; ++u)
{
top=0;
for(int v:f[u]) id[v]=++top;
if(top*8<=m)
{
int lim=((top)>>8)+2;
for(int i=1; i<=top+1; ++i) std::fill(bs[i], bs[i]+lim+1, 0);
for(int a:f[u]) for(int b:f[u]) if(rs[a][b]) set(bs[id[a]], id[b]);
for(int v:g[u])
{
std::fill(bs[top+1], bs[top+1]+lim+1, 0);
for(int x:f[u]) if(rs[v][x])
{
int t=ask(bs[id[x]], bs[top+1], lim);
// printf("%d %d %d %d\n", u, v, x, t);
ans+=t;
set(bs[top+1], id[x]);
}
}
}
else
{
for(int v:g[u])
{
rs[n+1].reset();
for(int x:f[u]) if(rs[v][x])
{
int t=(rs[x]&rs[n+1]).count();
// printf("f %d %d %d %d\n", u, v, x, t);
ans+=t;
rs[n+1].set(x);
}
}
}
}
printf("%llu\n", ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 10980kb
input:
5 9 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 1ms
memory: 11348kb
input:
4 0
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 14260kb
input:
50 50 28 35 12 24 31 50 10 24 21 44 5 31 23 36 31 45 6 39 4 8 13 37 42 48 17 45 19 33 12 21 19 32 16 43 12 47 25 31 40 48 8 49 43 48 6 42 27 34 13 39 17 40 13 35 3 49 20 24 5 12 43 44 15 37 24 27 8 43 4 22 17 38 28 47 29 46 3 15 9 49 1 41 43 45 3 6 37 48 13 30 11 43 8 25 33 38 16 32 32 41
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: -100
Wrong Answer
time: 3ms
memory: 11768kb
input:
100 4900 64 78 3 13 93 96 48 64 34 64 5 76 66 74 44 78 17 20 30 73 5 34 24 100 23 65 4 70 22 95 47 70 6 89 15 70 70 82 88 90 29 80 27 64 16 59 28 99 67 68 85 99 37 85 8 46 71 78 40 95 6 21 27 66 16 89 11 83 17 57 19 36 21 70 27 86 27 45 5 56 10 64 23 33 87 91 37 40 21 55 75 79 54 96 3 77 70 78 36 93...
output:
3646493
result:
wrong answer 1st numbers differ - expected: '3689634', found: '3646493'