QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#393963 | #2535. Cijanobakterije | lfxxx# | 70 ✓ | 43ms | 16684kb | C++14 | 1.2kb | 2024-04-19 18:48:20 | 2024-07-04 03:36:40 |
Judging History
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