QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#722496#2722. Marshmallow MoleculesSimonLJK5 11ms5640kbC++17764b2024-11-07 19:15:002024-11-07 19:15:01

Judging History

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

  • [2024-11-07 19:15:01]
  • 评测
  • 测评结果:5
  • 用时:11ms
  • 内存:5640kb
  • [2024-11-07 19:15:00]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+99;
int n,m;
struct edge{
	int v,nxt;
}edg[N];
int cntedge,hd[N];
void add(int u,int v){
	edg[++cntedge]=(edge){v,hd[u]};
	hd[u]=cntedge;
}
int id[N],sz[N]; 
int find(int x){
	if(id[x]==x) return x;
	return id[x]=find(id[x]);
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	int u,v;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		add(u,v);
	}
	for(int i=1;i<=n;i++) id[i]=i,sz[i]=1;
	int fu,fv;
	long long ans=0;
	for(u=1;u<=n;u++){
		sz[find(u)]--;
		ans+=sz[find(u)];
		for(int i=hd[u];i;i=edg[i].nxt){
			v=edg[i].v;
			fu=find(u); fv=find(v);
			if(fu==fv) continue;
			ans++;
			id[fv]=fu; sz[fu]+=sz[fv];
		}
	}
	cout<<ans;
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 1ms
memory: 3700kb

input:

100 4900
15 25
10 36
87 93
60 75
43 62
12 16
53 62
5 32
15 87
20 96
84 89
58 91
12 49
66 91
6 17
56 85
11 72
44 82
25 69
1 42
40 62
5 83
39 99
52 92
28 47
34 72
33 62
4 84
34 52
55 62
38 69
36 69
82 91
40 50
69 85
33 66
41 44
28 60
96 100
41 74
42 50
28 36
61 89
54 99
44 86
45 61
24 75
20 31
23 29
6...

output:

4948

result:

ok single line: '4948'

Test #2:

score: 0
Wrong Answer
time: 1ms
memory: 3668kb

input:

100 2000
30 54
4 27
67 70
75 88
94 96
37 56
6 19
29 59
31 70
34 99
18 69
39 79
47 63
14 90
37 45
50 94
36 41
80 100
68 71
10 92
37 75
34 91
69 91
59 63
53 85
54 86
64 79
57 96
66 96
31 38
27 80
12 25
35 63
5 99
28 61
57 71
10 81
21 43
44 49
37 52
35 100
64 94
67 90
35 46
54 91
38 77
25 40
6 80
6 60
...

output:

4712

result:

wrong answer 1st lines differ - expected: '4721', found: '4712'

Subtask #2:

score: 0
Wrong Answer

Test #14:

score: 0
Wrong Answer
time: 10ms
memory: 4560kb

input:

5000 100000
1007 2107
610 4713
352 2900
1869 2260
3688 4056
1528 4136
1021 4034
1654 2324
799 3245
4575 4615
3552 4045
2322 3284
2287 3417
1619 4398
901 1538
2545 4698
3300 4618
2273 4855
1890 2475
2433 3158
653 2221
284 1845
3225 3573
1451 3707
1074 4210
284 3646
729 3732
2554 3901
3232 3513
2649 3...

output:

11589666

result:

wrong answer 1st lines differ - expected: '11309962', found: '11589666'

Subtask #3:

score: 5
Accepted

Test #26:

score: 5
Accepted
time: 11ms
memory: 5472kb

input:

100000 99020
2976 97036
5108 36137
82 903
11925 33740
30856 70930
4105 43498
5500 66211
13684 81739
3416 70119
5792 89390
23098 83444
5033 27428
24910 64719
1714 51173
13329 34411
3859 33637
4127 33246
181 46040
8259 93728
1881 32818
604 47012
12645 65438
8226 19448
7637 87170
2828 70329
243 7934
44...

output:

3851818389

result:

ok single line: '3851818389'

Test #27:

score: 5
Accepted
time: 11ms
memory: 5592kb

input:

100000 99893
1719 75153
237 35956
16388 19581
14378 78657
69903 84628
58266 58297
320 45250
2164 94317
13451 17062
73014 98393
5041 5082
15462 21916
38735 80715
7245 21268
33986 98231
2245 28788
31001 73166
74515 94536
66148 72235
800 2507
45065 46517
15955 64664
4758 51907
18105 22123
17499 74852
3...

output:

2462112722

result:

ok single line: '2462112722'

Test #28:

score: 5
Accepted
time: 11ms
memory: 5508kb

input:

100000 99900
3215 11099
41057 60010
30319 66637
42476 84769
66980 68240
84489 96888
30255 36867
15772 18310
37275 47722
35210 39664
36975 43180
52829 86179
69326 95686
6352 14441
45670 51396
50368 51411
1817 3167
38972 45081
21316 33467
79960 85622
89183 91753
6661 10531
52574 70802
24353 27151
7889...

output:

1230469117

result:

ok single line: '1230469117'

Test #29:

score: 5
Accepted
time: 11ms
memory: 5460kb

input:

100000 98979
6146 34482
5140 86086
15474 73948
97 16533
9889 61282
1880 75753
4975 96342
59 3976
201 45655
8672 86427
2312 24929
24243 86289
692 30146
717 47964
20606 73190
12483 73291
21841 95121
6529 46724
1170 24787
974 14021
13242 35132
133 2714
12539 71980
26588 85706
1252 9415
2417 27116
1301 ...

output:

3232411268

result:

ok single line: '3232411268'

Test #30:

score: 5
Accepted
time: 7ms
memory: 5528kb

input:

100000 99910
363 1509
46092 55973
1282 4663
66733 99422
4471 7278
46679 73220
8724 88050
36959 76558
32919 92312
2201 4437
1633 11029
50837 89041
12188 81117
27592 57859
232 811
21537 72260
133 140
7744 19173
39664 55781
67413 71464
56750 99720
20401 61461
32373 76547
23791 56062
13778 19928
45972 7...

output:

2481369952

result:

ok single line: '2481369952'

Test #31:

score: 5
Accepted
time: 11ms
memory: 5508kb

input:

100000 99894
20586 22241
83458 92563
4793 4876
15416 17413
77379 86271
49068 72690
5554 8984
67850 79522
57928 65580
3202 3529
7253 10135
53243 55945
55563 68379
26173 29069
32887 39945
30809 49823
95154 99866
61659 71168
26549 60990
26015 32060
48853 84428
3340 8574
58338 61441
38161 73381
3676 603...

output:

1219197484

result:

ok single line: '1219197484'

Test #32:

score: 5
Accepted
time: 11ms
memory: 5448kb

input:

100000 98974
5738 64383
8540 93600
19635 52609
25378 65021
201 6811
5663 63923
5533 59688
1474 33612
5573 55949
1570 5494
24037 91262
983 50443
3081 76641
830 21043
18059 89653
17033 78741
13668 46052
155 953
1943 53063
26763 76507
1394 88357
10513 91646
5612 88789
7319 68247
22305 69952
13238 54515...

output:

4037175909

result:

ok single line: '4037175909'

Test #33:

score: 5
Accepted
time: 11ms
memory: 5512kb

input:

100000 99920
15367 29210
38519 69788
8567 28914
2382 38225
21008 60979
94538 97337
1845 6708
33576 45151
34386 91697
1765 3925
29178 83337
24962 29739
2106 2447
12232 14923
15690 83453
6179 25460
45939 87298
928 2928
21451 90309
18722 23982
4147 21506
39014 53802
8209 10244
17174 32060
1855 3740
268...

output:

2481130031

result:

ok single line: '2481130031'

Test #34:

score: 5
Accepted
time: 7ms
memory: 5640kb

input:

100000 99904
44171 49968
58010 87940
18741 35900
25812 56653
15973 18946
7421 11516
26622 48349
10351 18213
40578 44743
18453 22132
42593 58917
49709 57808
59175 70545
24896 25874
47624 84036
40647 42405
69770 75103
19126 29273
56799 58873
3002 3253
7618 10423
40215 40351
25280 44598
49417 74247
493...

output:

1164946111

result:

ok single line: '1164946111'

Test #35:

score: 5
Accepted
time: 11ms
memory: 5468kb

input:

100000 98998
5034 37396
7531 76242
907 22776
1136 17936
5499 31369
11567 73607
2646 82050
5328 25550
19206 89978
4805 26562
298 6341
6038 38219
2572 31407
2646 11809
7625 32723
15561 96975
814 18391
2989 34013
850 8155
11060 86255
124 1832
68 18979
17362 57933
4273 83311
15846 56183
18375 85415
1207...

output:

4016504110

result:

ok single line: '4016504110'

Test #36:

score: 5
Accepted
time: 11ms
memory: 5592kb

input:

100000 99904
34 28894
14959 24183
74569 80751
13227 21322
76772 94480
2024 2382
11039 51608
2065 31148
19164 72488
5984 54363
11319 14262
3786 35337
54105 92939
15970 85191
33625 38563
9021 96191
75727 81703
14217 82816
43198 82609
18276 64739
2509 27281
5267 9618
30926 75962
33583 68063
82270 94683...

output:

2483186538

result:

ok single line: '2483186538'

Test #37:

score: 5
Accepted
time: 11ms
memory: 5632kb

input:

100000 99886
50108 53909
17497 32406
30592 34527
35107 36052
27363 44558
8815 13175
59334 59827
13576 13676
43324 57846
13469 14695
55393 64420
28240 30872
44504 58694
84869 86404
80988 93101
9694 19133
13191 21837
13030 14270
4651 5410
19915 20438
38755 43997
68228 95508
80645 85558
39218 50624
129...

output:

1114405226

result:

ok single line: '1114405226'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%