QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#393963#2535. Cijanobakterijelfxxx#70 ✓43ms16684kbC++141.2kb2024-04-19 18:48:202024-07-04 03:36:40

Judging History

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

  • [2024-07-04 03:36:40]
  • 评测
  • 测评结果:70
  • 用时:43ms
  • 内存:16684kb
  • [2024-04-19 18:48:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
bool be;
constexpr int N = 1e5 + 5;
int n, m, dep[N];
vector<int>e[N], vec;
bool vis[N];
void dfs(int u, int f)
{
	vis[u] = 1;
	vec.emplace_back(u);
	dep[u] = dep[f] + 1;
	for (int v : e[u]) {
		if (v != f) {
			dfs(v, u);
		}
	}
}
int getlen(int u)
{
	vec.clear();
	dfs(u, u);
	int d = 0, id = 0;
	for (int x : vec) {
		if (dep[x] > d) {
			d = dep[x];
			id = x;
		}
		dep[x] = 0;
	}
	dfs(id, id);
	int ans = 0;
	for (int x : vec) {
		ans = max(ans, dep[x]);
	}
	return ans;
}
bool en;
int main() {
	cerr << (&be - &en) / 1024.0 / 1024 << " MB\n--------------------------------" << endl;
#ifdef IAKIOI
	freopen("in.in", "r", stdin);
//	freopen("out.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		e[u].emplace_back(v);
		e[v].emplace_back(u);
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		if (!vis[i]) {
			ans += getlen(i);
		}
	}
	cout << ans << endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 15
Accepted

Test #1:

score: 15
Accepted
time: 5ms
memory: 7000kb

input:

16666 16665
7505 4569
7505 12144
4569 6205
6205 6191
6205 4330
6205 4099
6205 11830
6191 4895
6191 12563
12144 5484
4569 14034
6191 8334
11830 6187
12144 418
5484 9017
6191 14006
6187 9841
8334 2471
12563 10763
12144 1130
1130 864
2471 13825
4330 3249
10763 10733
10733 5900
418 1047
4330 8505
12563 ...

output:

41

result:

ok single line: '41'

Test #2:

score: 0
Accepted
time: 3ms
memory: 7720kb

input:

33333 33332
16108 10076
10076 32065
16108 22737
22737 5752
16108 14604
22737 32488
5752 31603
22737 31689
32488 30786
5752 15580
14604 9667
10076 18208
32488 19971
14604 19327
31689 24335
5752 5922
10076 26152
19971 7815
24335 17444
14604 20661
7815 590
16108 26080
19971 21773
14604 3861
32488 27016...

output:

40

result:

ok single line: '40'

Test #3:

score: 0
Accepted
time: 18ms
memory: 8372kb

input:

50000 49999
12608 4455
12608 44407
12608 13632
44407 7078
44407 33354
44407 44410
44410 23901
12608 41316
41316 32913
44410 10545
44407 35313
4455 19646
33354 16562
4455 969
10545 36316
13632 43207
13632 21067
23901 25024
4455 2579
2579 30407
43207 19309
43207 49585
10545 6885
35313 21621
10545 6789...

output:

44

result:

ok single line: '44'

Test #4:

score: 0
Accepted
time: 21ms
memory: 9204kb

input:

66666 66665
39129 32841
32841 65300
32841 1990
32841 43911
1990 46919
39129 58203
39129 1484
1990 5121
65300 50519
32841 21902
1484 32944
39129 47512
47512 32462
1484 23985
1484 52819
1990 14171
39129 9547
5121 38300
1484 49531
58203 46637
46919 14077
14171 60320
52819 54866
49531 47347
52819 39934
...

output:

43

result:

ok single line: '43'

Test #5:

score: 0
Accepted
time: 34ms
memory: 9932kb

input:

83333 83332
61295 47338
47338 57069
57069 7516
57069 76951
61295 50844
50844 43850
50844 48401
76951 26726
50844 48326
48326 44713
44713 65487
48401 23226
7516 32166
43850 24464
48401 68692
61295 34000
50844 53133
48401 70286
26726 5566
76951 31108
32166 53085
5566 64792
50844 63635
7516 60718
7516 ...

output:

46

result:

ok single line: '46'

Test #6:

score: 0
Accepted
time: 18ms
memory: 10500kb

input:

100000 99999
64643 4229
4229 28398
64643 70858
70858 29473
70858 22054
29473 59932
28398 33977
22054 4325
29473 6666
6666 33299
6666 25235
6666 24929
28398 99629
33977 72680
25235 12811
70858 73509
12811 78498
28398 89186
4229 44393
73509 80352
25235 40159
25235 88136
72680 27319
12811 37981
28398 5...

output:

52

result:

ok single line: '52'

Subtask #2:

score: 6
Accepted

Test #7:

score: 6
Accepted
time: 17ms
memory: 16684kb

input:

99997 99926
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52...

output:

99997

result:

ok single line: '99997'

Test #8:

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

input:

16666 8389
3 4
4 5
7 8
11 12
12 13
15 16
17 18
19 20
20 21
25 26
27 28
29 30
31 32
32 33
35 36
38 39
39 40
45 46
46 47
48 49
50 51
54 55
55 56
56 57
61 62
63 64
66 67
67 68
69 70
71 72
73 74
74 75
75 76
76 77
77 78
78 79
81 82
82 83
83 84
86 87
91 92
97 98
98 99
102 103
103 104
104 105
105 106
106 1...

output:

16666

result:

ok single line: '16666'

Test #9:

score: 0
Accepted
time: 4ms
memory: 7216kb

input:

33333 16780
1 2
2 3
4 5
6 7
7 8
8 9
10 11
14 15
16 17
17 18
18 19
20 21
27 28
28 29
30 31
31 32
32 33
35 36
36 37
37 38
38 39
39 40
44 45
46 47
47 48
49 50
50 51
53 54
54 55
55 56
58 59
64 65
66 67
67 68
69 70
71 72
73 74
74 75
78 79
79 80
80 81
81 82
82 83
83 84
84 85
86 87
87 88
88 89
89 90
92 93
...

output:

33333

result:

ok single line: '33333'

Test #10:

score: 0
Accepted
time: 6ms
memory: 7596kb

input:

50000 24891
6 7
8 9
9 10
10 11
11 12
14 15
19 20
22 23
23 24
27 28
28 29
31 32
35 36
37 38
38 39
40 41
41 42
43 44
45 46
48 49
49 50
51 52
53 54
56 57
57 58
59 60
62 63
63 64
65 66
66 67
67 68
70 71
71 72
73 74
74 75
75 76
76 77
79 80
80 81
81 82
83 84
84 85
87 88
91 92
92 93
94 95
95 96
96 97
98 99...

output:

50000

result:

ok single line: '50000'

Subtask #3:

score: 6
Accepted

Test #11:

score: 6
Accepted
time: 1ms
memory: 6276kb

input:

2 0

output:

2

result:

ok single line: '2'

Test #12:

score: 0
Accepted
time: 1ms
memory: 6540kb

input:

2 1
1 2

output:

2

result:

ok single line: '2'

Test #13:

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

input:

4 3
1 2
1 3
2 4

output:

4

result:

ok single line: '4'

Test #14:

score: 0
Accepted
time: 1ms
memory: 6200kb

input:

4 2
1 3
2 4

output:

4

result:

ok single line: '4'

Test #15:

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

input:

16666 14267
2 1
2 3
1 4
2 5
1 6
2 7
2 8
2 9
1 11
1 12
1 13
1 14
2 15
2 16
1 17
1 18
2 19
1 20
1 21
1 22
2 23
1 24
1 25
1 26
1 27
1 28
2 29
1 30
2 31
2 32
1 36
2 37
2 38
1 39
1 40
2 41
1 42
1 43
1 44
1 45
1 46
1 48
2 49
1 50
2 53
1 54
2 55
2 56
1 57
2 58
2 59
1 60
2 61
1 62
2 63
2 64
1 65
1 66
2 67
2...

output:

2402

result:

ok single line: '2402'

Test #16:

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

input:

33333 28466
2 1
1 3
2 4
2 5
1 6
1 7
1 8
1 9
1 10
1 11
1 13
1 15
2 16
2 17
1 18
1 19
2 20
2 21
2 22
2 23
2 24
1 25
2 26
2 27
2 28
1 29
1 30
2 31
1 35
2 36
2 38
2 39
2 40
1 41
1 42
1 43
1 44
1 45
2 46
2 47
2 49
2 50
2 51
1 52
1 53
1 54
1 55
1 56
2 57
1 58
1 60
1 62
1 63
2 64
2 65
2 66
2 67
2 68
2 69
1...

output:

4870

result:

ok single line: '4870'

Test #17:

score: 0
Accepted
time: 3ms
memory: 8064kb

input:

50000 42842
2 1
2 3
1 4
1 5
2 6
1 7
2 8
1 9
2 10
2 11
1 13
2 14
2 15
1 16
1 17
1 18
2 20
1 21
1 22
1 23
2 24
2 25
1 26
1 27
1 28
1 29
1 31
2 33
2 35
2 36
2 37
1 38
1 39
1 40
2 42
2 43
2 44
1 45
1 47
1 48
2 49
2 50
2 51
1 52
2 54
2 55
2 56
1 58
2 59
2 60
2 61
2 63
2 64
2 66
2 67
2 68
2 69
1 72
2 76
1...

output:

7161

result:

ok single line: '7161'

Subtask #4:

score: 15
Accepted

Test #18:

score: 15
Accepted
time: 1ms
memory: 6256kb

input:

1000 999
658 294
294 150
658 348
658 205
205 640
658 765
294 570
570 871
205 232
294 848
205 990
658 40
232 204
150 422
40 876
232 25
25 908
658 68
908 616
422 905
570 32
848 298
616 531
348 400
150 359
658 852
294 610
32 912
658 167
616 436
232 215
40 919
25 937
905 909
616 911
150 27
990 229
658 8...

output:

28

result:

ok single line: '28'

Test #19:

score: 0
Accepted
time: 1ms
memory: 6212kb

input:

600 99
463 511
107 260
494 218
407 554
114 186
165 584
409 397
259 544
80 542
449 420
265 178
151 325
401 216
327 216
497 435
531 78
16 258
50 563
316 345
365 587
135 274
590 461
224 299
147 599
438 552
84 207
122 262
262 117
435 518
219 216
313 164
428 155
503 361
575 334
571 4
543 336
126 363
209 ...

output:

595

result:

ok single line: '595'

Test #20:

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

input:

600 0

output:

600

result:

ok single line: '600'

Test #21:

score: 0
Accepted
time: 1ms
memory: 6580kb

input:

700 233
177 67
378 499
529 452
566 496
328 305
417 505
461 135
127 14
426 504
98 652
367 387
508 173
35 516
366 687
475 665
68 152
141 661
303 573
335 360
71 275
217 472
22 341
374 12
216 618
112 471
218 110
440 364
9 41
355 542
424 61
438 656
625 187
385 627
617 653
250 145
9 437
156 681
282 335
35...

output:

660

result:

ok single line: '660'

Test #22:

score: 0
Accepted
time: 1ms
memory: 6284kb

input:

700 609
507 668
101 507
235 101
328 101
359 101
411 235
296 507
288 380
542 380
198 288
661 288
451 288
346 451
151 542
126 233
310 233
77 126
360 126
374 233
25 374
322 126
338 98
312 338
496 338
392 338
75 496
175 338
395 98
107 129
69 107
269 129
274 69
229 274
585 274
10 269
228 591
611 591
518 ...

output:

495

result:

ok single line: '495'

Test #23:

score: 0
Accepted
time: 1ms
memory: 6272kb

input:

800 399
289 10
687 30
555 462
592 750
785 22
369 74
505 703
32 164
81 532
197 371
169 28
224 494
114 591
723 130
516 722
233 325
170 649
701 277
494 497
616 13
21 628
620 61
526 439
16 560
269 146
102 413
366 13
434 778
472 446
470 720
341 688
326 4
488 577
667 37
668 141
80 671
746 415
97 703
370 7...

output:

681

result:

ok single line: '681'

Test #24:

score: 0
Accepted
time: 1ms
memory: 6416kb

input:

800 400
602 80
541 220
587 148
7 5
744 607
697 629
290 3
46 296
144 331
24 769
22 321
283 782
328 621
636 387
200 723
513 458
228 252
310 733
614 56
52 644
286 89
243 168
540 322
119 222
764 693
658 467
47 249
657 202
649 465
466 163
792 120
165 212
485 18
382 32
698 503
611 6
673 301
362 460
269 51...

output:

800

result:

ok single line: '800'

Test #25:

score: 0
Accepted
time: 1ms
memory: 6204kb

input:

900 599
70 144
850 373
564 215
768 424
126 868
60 535
504 790
789 205
242 800
453 772
455 420
575 721
542 170
136 156
23 417
342 772
291 411
339 810
440 596
562 599
850 397
339 237
307 567
887 24
416 660
819 356
694 819
355 309
118 719
773 608
671 768
866 689
368 485
11 29
465 778
774 440
612 20
6 1...

output:

516

result:

ok single line: '516'

Test #26:

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

input:

900 768
306 503
786 503
223 306
236 786
230 236
586 306
635 425
717 425
104 425
364 425
747 717
128 104
757 221
464 757
195 464
245 221
126 245
21 757
41 472
352 472
377 41
214 472
875 472
580 214
281 88
838 88
506 281
811 281
192 506
781 811
484 714
362 714
546 714
683 714
74 546
675 484
37 100
851...

output:

692

result:

ok single line: '692'

Test #27:

score: 0
Accepted
time: 2ms
memory: 6348kb

input:

1000 832
400 570
250 533
727 269
598 866
482 986
442 363
699 255
724 153
271 330
854 212
887 711
184 255
968 548
969 925
874 836
167 41
129 290
451 149
811 983
208 451
553 275
241 155
513 468
5 595
717 978
362 612
250 550
729 236
851 606
515 191
852 190
643 589
758 970
396 269
792 651
771 360
181 53...

output:

278

result:

ok single line: '278'

Test #28:

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

input:

1000 500
466 938
48 179
598 272
852 177
190 614
820 390
258 517
448 395
907 401
555 317
465 260
644 309
120 593
204 262
85 273
916 10
836 839
602 894
374 320
1000 319
176 7
183 138
379 226
12 562
741 149
107 384
162 451
522 870
920 883
982 283
516 565
267 228
23 152
647 480
8 794
231 845
28 893
341 ...

output:

1000

result:

ok single line: '1000'

Subtask #5:

score: 28
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #29:

score: 28
Accepted
time: 41ms
memory: 10536kb

input:

100000 99999
26260 62490
62490 385
26260 77337
385 52331
385 47020
52331 37152
47020 38095
37152 59813
26260 67008
77337 1939
38095 69919
385 50465
38095 43162
59813 43954
43954 27007
50465 27271
67008 67514
69919 12628
69919 42528
59813 52359
52331 3409
69919 15581
69919 89925
15581 97280
43162 376...

output:

47

result:

ok single line: '47'

Test #30:

score: 0
Accepted
time: 7ms
memory: 7556kb

input:

99900 16649
79168 74279
81293 52352
61268 70991
83294 43338
62182 67611
42774 34063
54956 64391
27209 1980
51879 19162
76910 39174
20432 13428
97163 35576
88198 35441
4045 90164
82763 85512
1299 87657
66491 51497
43123 19408
55033 70308
28347 33064
31175 33005
594 76852
68409 95479
88291 90392
59167...

output:

99343

result:

ok single line: '99343'

Test #31:

score: 0
Accepted
time: 22ms
memory: 9864kb

input:

99900 66600
59880 51369
86913 51369
52800 14436
69151 52800
54893 66560
57653 54893
47183 41511
78933 41511
84205 7087
57189 84205
97144 43813
29285 97144
69293 54634
32919 54634
58945 87773
91843 58945
52193 27619
85968 27619
91154 89770
98507 91154
16225 45239
2085 45239
59716 5823
87516 59716
431...

output:

99900

result:

ok single line: '99900'

Test #32:

score: 0
Accepted
time: 16ms
memory: 8212kb

input:

99800 33266
4906 22196
91278 36153
24688 8569
43257 84496
9259 39947
85724 20256
47421 79696
27628 34630
52459 85953
99628 39967
31451 51404
1151 21247
81492 93267
11526 81235
10035 19626
64082 47094
60991 98816
9170 43003
27911 353
24660 38049
80008 6646
74719 48829
58085 9457
20942 45731
7590 7650...

output:

95686

result:

ok single line: '95686'

Test #33:

score: 0
Accepted
time: 32ms
memory: 9812kb

input:

99800 89820
19834 58174
97018 19834
43674 19834
91303 43674
53762 97018
45590 97018
94204 53762
84928 19834
62709 19834
12431 10097
59001 10097
52542 10097
37975 10097
93473 10097
70764 37975
35446 12431
99586 93473
38931 37975
14199 35520
14486 14199
79080 14486
88193 14199
24436 35520
32838 35520
...

output:

63995

result:

ok single line: '63995'

Test #34:

score: 0
Accepted
time: 19ms
memory: 8680kb

input:

99700 49849
51050 43959
1741 29498
48872 50990
46370 30120
25560 58690
48891 5762
72583 43691
60074 77023
48152 15847
98005 22583
66496 25095
78321 42718
77086 74592
63571 7520
25251 77323
35735 37588
70984 46137
26461 2659
84587 36024
38243 29335
42120 88252
36228 86529
64150 12510
78583 51263
2113...

output:

83028

result:

ok single line: '83028'

Test #35:

score: 0
Accepted
time: 22ms
memory: 9720kb

input:

99700 74775
23191 79963
60027 79963
37116 23191
88011 98990
9494 88011
22478 98990
21273 38827
4011 38827
5767 21273
58951 5337
1176 5337
51789 58951
73115 39468
60250 73115
85820 73115
26412 25813
17898 25813
70479 26412
88891 66181
69268 66181
81590 69268
92184 73102
77537 92184
63813 92184
40391 ...

output:

91364

result:

ok single line: '91364'

Test #36:

score: 0
Accepted
time: 31ms
memory: 9184kb

input:

99600 66399
57552 55340
58422 94827
16766 82424
51360 16952
19562 57241
18748 65263
94770 54153
94296 22569
35667 92568
61319 57105
17402 52871
58177 85233
32449 26675
50129 27498
66600 63658
81505 35338
32012 12837
43756 78922
40590 69031
5106 2945
28923 55737
33250 56709
88448 12565
52856 19175
49...

output:

49195

result:

ok single line: '49195'

Test #37:

score: 0
Accepted
time: 32ms
memory: 9684kb

input:

99600 89640
16808 96109
4059 16808
92559 96109
15033 4059
55138 92559
63162 16808
529 4059
80264 15033
15414 96109
40789 99025
36152 40789
53366 99025
92836 99025
92991 92836
96365 92836
29010 53366
52870 99025
51489 96365
43861 25978
20654 25978
97647 25978
33022 20654
65406 33022
9332 20654
99332 ...

output:

63915

result:

ok single line: '63915'

Test #38:

score: 0
Accepted
time: 43ms
memory: 9968kb

input:

99500 82915
37315 50681
32041 56451
10547 41666
43326 86253
56158 63740
80107 89996
15270 51457
68558 93039
75077 71309
9388 57998
68967 52431
13509 27843
11740 48296
7418 40279
17328 40933
78662 46464
4841 18001
12577 28983
2481 64307
11513 50212
35767 24134
63411 57685
31229 59148
49718 57528
9033...

output:

20985

result:

ok single line: '20985'

Test #39:

score: 0
Accepted
time: 28ms
memory: 9836kb

input:

99500 79600
9609 41507
22130 9609
91548 22130
48373 41507
87538 817
80420 87538
82322 80420
92154 80420
1392 46963
54776 1392
78510 54776
34091 54776
14880 94936
83580 94936
79305 94936
89968 14880
62518 63271
57379 63271
98986 62518
35631 57379
55685 19006
49289 55685
37902 49289
15498 19006
81414 ...

output:

84655

result:

ok single line: '84655'

Extra Test:

score: 0
Extra Test Passed