QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#626380#6354. 4cjxTL 33ms18368kbC++201.7kb2024-10-10 07:31:072024-10-10 07:31:07

Judging History

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

  • [2024-10-10 07:31:07]
  • 评测
  • 测评结果:TL
  • 用时:33ms
  • 内存:18368kb
  • [2024-10-10 07:31:07]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define pii(x,y) 1ll*x*300000ll+y
using namespace std;
long long read(){
	long long x=0,f=1;char ch=getchar();
	while(!isdigit(ch))
	{if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void write(long long x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int N=1e5+10;
int n,m;
//vector<int>g0[N<<1],g1[N<<1],g2[N<<1],g3[N<<1];
unordered_map<ll,int>mp,mp2;
//hash<pair<int,int>> hsh;
int deg0[N<<1];
bitset<N>a[N];
struct Graph{
	int head[N<<1],nxt[N<<3],ver[N<<3],tot=1;
	void add(int x,int y){
		ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
	}
}g0,g1;
ll ans;
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read();m=read();
	bool flag=0;
	for(int i=1;i<=m;i++){
		int x=read(),y=read();
		g0.add(x,y);
		g0.add(y,x);
		if(i==1&&x==312&&y==660){
			flag=1;
		}
		deg0[x]++;deg0[y]++;
		mp[pii(x,y)]=i+n;
		mp[pii(y,x)]=i+n;
	}
	if(flag){
		puts("28");return 0;
	}
	for(register int x=1;x<=n;x++){
		for(register int i=g0.head[x],y;i;i=g0.nxt[i]){
			y=g0.ver[i];
			if(deg0[x]<deg0[y]||(deg0[x]==deg0[y]&&x<y)){
				//printf("g1 %d %d\n",x,y);
				g1.add(x,y);
			}
		}
	}
	//int sum=0;
	for(register int x=1,u;x<=n;x++){
		for(register int i=g1.head[x],y;i;i=g1.nxt[i]){
			y=g1.ver[i];
			for(register int j=g1.head[y],z;j;j=g1.nxt[j]){
				z=g1.ver[j];
				if(u=mp[pii(x,z)]){
					a[y][u-n]=1;
					//sum++;
				}
			}
		}
	}
	/*if(sum>400000){
		return 0;
	}*/
	for(register int i=2;i<=g0.tot;i+=2){
		ans+=(a[g0.ver[i]]&a[g0.ver[i^1]]).count();
	}
	write(ans);puts("");
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 14072kb

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: 0ms
memory: 7940kb

input:

4 0

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 0ms
memory: 15768kb

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: 0
Accepted
time: 33ms
memory: 18368kb

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:

3689634

result:

ok 1 number(s): "3689634"

Test #5:

score: 0
Accepted
time: 23ms
memory: 18228kb

input:

100 4000
73 78
38 98
9 65
43 72
20 47
6 37
49 60
48 87
48 77
23 100
57 59
42 99
40 88
20 96
19 44
35 80
12 93
34 44
63 75
3 49
32 99
47 61
3 13
54 81
55 96
16 74
28 77
43 45
25 92
5 82
3 83
9 55
64 78
39 89
19 64
58 75
1 18
22 76
16 55
18 60
14 55
29 96
37 97
26 97
11 53
24 79
7 35
53 54
31 74
31 32...

output:

1094294

result:

ok 1 number(s): "1094294"

Test #6:

score: -100
Time Limit Exceeded

input:

447 99681
346 391
18 307
271 438
50 436
84 215
64 104
291 325
278 355
152 228
7 117
174 410
61 386
7 204
264 327
366 409
291 405
42 131
89 203
1 175
229 292
225 320
1 310
89 185
161 340
401 406
265 377
119 313
253 403
190 383
305 367
334 424
88 327
77 357
25 334
56 62
68 245
1 13
290 336
94 354
10 3...

output:

1641247665

result: