QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#99803#6354. 4whateverWA 3ms14260kbC++171.6kb2023-04-23 19:20:482023-04-23 19:23:03

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-23 19:23:03]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:14260kb
  • [2023-04-23 19:20:48]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'