QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #216030 | #6501. Graph Partitioning | levitated | WA | 164ms | 7728kb | C++14 | 601b | 2023-10-15 15:17:55 | 2023-11-04 12:36:02 |
Judging History
你现在查看的是最新测评结果
- [2024-07-16 01:40:04]
- hack成功，自动添加数据
- (/hack/741)
- [2024-07-16 01:18:05]
- hack成功，自动添加数据
- (/hack/740)
- [2024-07-04 04:49:48]
- hack成功，自动添加数据
- (/hack/719)
- [2023-11-04 12:31:21]
- hack成功，自动添加数据
- (//qoj.ac/hack/419)
- [2023-10-15 15:17:55]
- 提交
answer
//qoj6501
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, fa[N];
int gf(int x){
return x == fa[x] ? x : fa[x] = gf(fa[x]);
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n+n-2; ++ i){
fa[i] = i;
}
for(int i = 1; i <= n+n-2; ++ i){
int u, v;
scanf("%d%d", &u, &v);
if(u == v){
puts("0");
return 0;
}
if(u > v){
swap(u, v);
}
fa[gf(u)] = gf(v+n-2);
}
long long ans = 1;
for(int i = 1; i <= n+n-2; ++ i){
if(fa[i] == i){
ans = ans * 2 % 998244353;
}
}
printf("%lld\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3776kb
input:
2 1 2 1 2
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
3 1 2 2 3 1 3 2 2
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
6 3 4 1 3 3 5 1 6 6 5 4 2 5 4 1 2 4 1 5 3
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3388kb
input:
12 2 7 6 7 12 7 10 7 1 6 5 8 11 7 7 5 8 1 8 10 1 7 1 8 10 5 2 1 12 12 11 8 1 10 3 1 4 3 12 11 2 1 9 4
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
50 31 15 36 25 26 32 26 22 50 49 41 36 49 35 39 18 2 3 23 18 33 15 1 45 4 47 36 34 23 3 49 16 29 48 27 25 33 15 40 3 50 50 40 14 49 36 31 6 22 1 4 36 35 1 21 49 26 32 29 48 36 36 46 41 23 41 10 32 48 8 31 30 15 20 39 39 39 16 39 27 1 27 32 2 5 31 20 7 21 20 39 11 37 24 30 35 10 10 36 1 29 39 2 39 9 ...
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
500 289 21 238 284 123 225 289 119 177 391 336 381 77 104 450 132 478 38 397 144 17 466 244 65 287 402 434 198 140 353 77 391 253 154 248 16 103 296 453 433 334 185 459 404 348 363 414 478 495 454 218 325 466 180 404 119 57 36 17 378 424 374 148 434 141 61 100 239 406 461 76 3 459 481 242 200 50 467...
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
5000 2829 1670 679 1395 65 1242 1599 3742 4840 3702 1201 812 603 3457 1385 2163 3509 1562 603 2624 2390 2464 4938 4289 3091 3754 2900 4169 1387 2359 3628 1143 4339 2544 4775 863 1915 4473 3847 2807 4311 3652 4611 99 504 4157 4925 4851 2696 2399 2234 2096 2553 3645 3934 2946 1047 642 1678 172 2721 48...
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 1ms
memory: 5520kb
input:
50000 17692 10864 23137 40234 13161 7801 45246 36612 13632 29693 17696 1590 12317 13571 21391 9281 7843 45687 39078 20858 17991 32357 35558 11113 8946 15602 2322 24939 11570 29188 21553 26417 14953 30965 2816 28991 48893 42836 16173 43854 21447 41459 38205 26906 10580 31882 37638 45028 20087 32659 5...
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 148ms
memory: 7368kb
input:
500000 184237 361613 315453 33984 428578 148814 397177 161775 359148 409762 9627 259320 325182 163506 290026 34824 78676 291084 139250 289935 64488 78051 260578 351713 396094 189069 360589 349175 108985 379843 187497 240811 80547 476388 489970 301599 359273 163026 207752 235127 315709 130611 49900 6...
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
12 3 4 6 2 12 7 5 4 7 9 8 10 5 3 9 12 1 3 4 2 8 4 11 1 10 12 2 1 12 10 4 10 1 7 6 3 11 8 6 11 12 11 6 5
output:
4
result:
ok 1 number(s): "4"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
50 50 46 4 2 48 49 40 42 24 50 33 34 2 7 49 50 17 2 37 42 38 34 43 14 11 28 15 2 12 48 46 4 46 41 26 22 38 47 27 1 15 1 7 19 31 25 42 26 1 6 38 28 27 36 10 2 44 23 22 3 9 11 18 8 28 8 50 44 29 35 43 1 14 3 35 45 12 47 45 22 32 47 16 38 21 9 48 17 50 45 15 39 34 11 16 49 20 4 16 35 40 31 18 22 4 26 6...
output:
4
result:
ok 1 number(s): "4"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
500 471 365 445 482 195 74 365 157 32 151 337 455 358 165 449 379 398 395 115 120 410 429 237 436 5 4 440 430 208 246 63 201 174 297 500 485 284 357 411 57 44 206 40 32 261 328 496 448 435 467 313 97 427 479 92 481 274 226 198 110 475 463 163 100 172 188 420 89 64 51 56 154 36 44 455 429 329 234 4 1...
output:
8
result:
ok 1 number(s): "8"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
5000 3072 2309 4985 4981 3902 2929 4256 1581 3839 694 4010 69 2403 8 3632 4308 4656 10 1849 1907 2502 1026 3351 4886 3280 3604 1200 2040 3171 4389 156 4458 1599 2060 3864 3644 556 4320 1603 1391 4103 4788 4913 4653 3069 4118 4129 4124 312 157 4162 296 3788 4672 2147 528 3983 3027 4342 3313 135 1288 ...
output:
8
result:
ok 1 number(s): "8"
Test #15:
score: 0
Accepted
time: 12ms
memory: 4212kb
input:
50000 26470 43494 4993 27623 20976 25927 2928 9310 127 39594 35979 22097 19310 34587 13025 29653 43843 29990 14802 15986 35773 20928 27149 29703 7564 10907 7413 17188 48855 11129 35445 48752 813 2071 42080 32979 21156 18261 14229 38793 49879 48354 36779 11776 11829 25294 36534 29197 32948 8068 32650...
output:
32
result:
ok 1 number(s): "32"
Test #16:
score: 0
Accepted
time: 156ms
memory: 7484kb
input:
499996 93967 109058 475419 496621 167709 327464 53124 315975 357260 187306 4269 82964 127845 346887 255033 62789 492122 463194 248059 463783 106580 27729 455746 48519 358632 232738 353721 492689 338489 67130 424505 446804 461139 478588 358313 380725 473759 446316 495978 449758 233359 497373 70129 24...
output:
64
result:
ok 1 number(s): "64"
Test #17:
score: 0
Accepted
time: 152ms
memory: 7492kb
input:
499997 493148 302135 145237 138060 309828 349135 67999 277325 470833 408457 306761 437493 16706 137176 29697 111767 396058 75038 109539 47792 117255 496752 146306 417356 470903 191761 386524 301250 63495 18852 454580 407743 187389 250189 86915 30074 205821 154974 266279 262060 60537 34874 30090 6326...
output:
32
result:
ok 1 number(s): "32"
Test #18:
score: 0
Accepted
time: 157ms
memory: 7496kb
input:
499998 217129 452283 499232 498899 22873 19929 333821 278970 459228 227999 264827 452844 87670 2329 363983 456123 71227 487635 66717 110074 122229 1310 487527 476012 72380 153168 339691 239156 470287 39223 313596 51345 82035 161143 12672 14856 31973 4740 126477 265156 39653 411342 56898 345467 21260...
output:
64
result:
ok 1 number(s): "64"
Test #19:
score: 0
Accepted
time: 154ms
memory: 7488kb
input:
499999 85305 82417 374512 190598 417298 226229 293831 295059 440770 457038 45263 28161 11 3 346497 446763 239687 188366 258544 74176 263578 35207 254249 147109 377430 215147 42153 44100 427385 405317 47168 213368 36117 41231 212563 369865 16887 10782 356222 473078 356263 101904 51874 62294 377057 19...
output:
1024
result:
ok 1 number(s): "1024"
Test #20:
score: 0
Accepted
time: 164ms
memory: 7488kb
input:
500000 424192 435221 176451 265555 123262 27219 404518 297753 98842 458976 440749 38111 277647 277752 490819 489368 298912 291892 9150 31978 373040 142397 14235 4309 493409 473693 413319 264083 385861 438598 336509 164765 283991 444026 334434 283956 465585 122836 393317 144868 419423 443461 493421 4...
output:
128
result:
ok 1 number(s): "128"
Test #21:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
12 3 4 6 2 12 7 9 4 6 9 8 10 5 3 9 12 1 3 4 2 8 3 4 1 10 12 2 1 12 8 6 10 2 7 7 3 11 8 6 8 12 11 7 5
output:
2
result:
ok 1 number(s): "2"
Test #22:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
50 50 46 4 2 48 49 40 42 24 26 33 38 3 7 49 50 17 14 37 42 37 34 43 42 23 28 3 2 43 48 46 44 45 41 24 22 38 43 27 23 15 14 16 19 26 25 27 26 1 6 33 28 27 28 10 9 44 43 4 3 9 11 18 14 10 8 49 44 29 32 2 1 14 12 35 40 42 47 45 43 32 33 35 38 10 9 21 17 50 45 15 19 34 32 44 49 20 17 32 35 40 39 18 23 2...
output:
2048
result:
ok 1 number(s): "2048"
Test #23:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
500 366 365 445 447 195 194 159 157 147 151 337 341 168 165 381 379 398 394 115 120 410 414 432 436 5 4 435 430 243 246 198 201 294 297 490 485 284 286 60 57 204 206 40 37 324 328 451 448 435 437 313 312 427 432 477 481 274 272 198 195 465 463 163 161 187 188 92 89 64 61 151 154 42 44 455 454 239 23...
output:
4680626
result:
ok 1 number(s): "4680626"
Test #24:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
5000 3072 3068 4983 4981 2931 2929 4256 4251 697 694 4010 4009 2403 2399 4303 4308 4656 4655 1849 1850 1030 1026 3351 3354 3600 3604 1200 1205 3171 3173 156 157 2059 2060 3647 3644 556 560 1603 1599 4103 4105 4657 4653 3069 3072 4129 4124 160 157 297 296 3788 3793 2147 2145 3031 3027 3314 3313 1284 ...
output:
114837367
result:
ok 1 number(s): "114837367"
Test #25:
score: 0
Accepted
time: 12ms
memory: 4036kb
input:
50000 26470 26474 27622 27623 20976 20980 9305 9310 127 128 35979 35975 19310 19312 29651 29653 29993 29990 15982 15986 35773 35769 27149 27152 10902 10907 7413 7417 11134 11129 35445 35447 2068 2071 32981 32979 21156 21151 38789 38793 48357 48354 36779 36778 25292 25294 29200 29197 32948 32944 3265...
output:
577119782
result:
ok 1 number(s): "577119782"
Test #26:
score: 0
Accepted
time: 135ms
memory: 7672kb
input:
499996 109054 109058 475419 475422 167709 167710 53124 53127 187310 187306 82963 82964 346883 346887 255033 255031 463196 463194 248059 248061 106580 106576 48520 48519 358632 358630 353721 353724 67132 67130 424505 424509 461139 461140 358313 358317 446319 446316 449759 449758 233359 233363 242712 ...
output:
841419083
result:
ok 1 number(s): "841419083"
Test #27:
score: 0
Accepted
time: 138ms
memory: 7480kb
input:
499997 302140 302135 138064 138060 309828 309829 277323 277325 408458 408457 306761 306766 137171 137176 111762 111767 75042 75038 47794 47792 117255 117257 146306 146308 470903 470899 301251 301250 63495 63492 407744 407743 187389 187392 86915 86912 205821 205819 262062 262060 34877 34874 30090 300...
output:
605492347
result:
ok 1 number(s): "605492347"
Test #28:
score: 0
Accepted
time: 144ms
memory: 7728kb
input:
499998 217129 217130 498900 498899 22873 22872 333821 333820 459228 459225 264827 264828 2333 2329 363983 363988 487632 487635 110070 110074 122229 122226 476015 476012 153167 153168 239158 239156 470287 470286 51350 51345 161142 161143 14852 14856 31973 31972 126477 126478 411340 411342 345462 3454...
output:
298551969
result:
ok 1 number(s): "298551969"
Test #29:
score: 0
Accepted
time: 146ms
memory: 7708kb
input:
499999 85305 85303 374512 374508 226233 226229 295054 295059 440770 440774 45263 45258 11 8 446759 446763 239687 239683 258544 258543 263578 263575 147114 147109 377430 377427 44096 44100 405322 405317 213367 213368 41227 41231 212563 212567 16887 16884 356222 356223 356263 356260 62291 62294 190334...
output:
743216918
result:
ok 1 number(s): "743216918"
Test #30:
score: 0
Accepted
time: 142ms
memory: 7728kb
input:
500000 424192 424193 265552 265555 123262 123260 404518 404513 458972 458976 440749 440747 277749 277752 489369 489368 291894 291892 31977 31978 142401 142397 14235 14232 473695 473693 264085 264083 385861 385865 164769 164765 444021 444026 283960 283956 122841 122836 144873 144868 443458 443461 446...
output:
723134178
result:
ok 1 number(s): "723134178"
Test #31:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
12 4 12 9 7 4 5 7 6 5 6 9 12 7 1 1 2 3 11 5 8 11 5 4 3 10 9 2 4 6 10 8 7 8 9 12 11 11 10 12 10 2 3 8 10
output:
2
result:
ok 1 number(s): "2"
Test #32:
score: 0
Accepted
time: 161ms
memory: 7476kb
input:
500000 428428 307092 418698 361606 296441 296442 1801 17851 319827 336109 295856 326738 109847 109846 18286 310348 311073 438174 152038 152037 411653 492931 426360 197712 378607 378606 452793 452792 422229 185434 85779 85778 390337 390338 140882 140883 425640 391068 456023 456022 328045 328046 47157...
output:
2
result:
ok 1 number(s): "2"
Test #33:
score: 0
Accepted
time: 151ms
memory: 7496kb
input:
500000 115858 115859 330845 28266 301554 301555 209219 284978 152107 333207 248278 248277 9633 9634 409223 409224 392549 392550 97315 97316 132987 203624 64531 64532 138581 138582 413353 413354 254168 254169 5451 5452 456854 456853 420060 497822 270090 248735 198080 198079 204269 265467 215033 21503...
output:
4
result:
ok 1 number(s): "4"
Test #34:
score: 0
Accepted
time: 159ms
memory: 7416kb
input:
500000 414842 423910 454688 454689 240526 240527 15050 81076 274677 368553 210352 210351 268735 268736 473919 496210 426830 428605 312669 312670 174996 174995 397286 397287 203172 203173 356637 170539 267240 267239 361779 361778 168978 168979 298897 298898 273961 409484 88265 86157 8531 8532 341833 ...
output:
8
result:
ok 1 number(s): "8"
Test #35:
score: 0
Accepted
time: 155ms
memory: 7544kb
input:
500000 108618 101576 302817 302818 7175 7176 75626 55143 11379 8478 452653 474223 361252 361251 175113 175112 210560 196587 292077 392138 389515 389514 498577 487491 461898 461899 447930 334420 454224 451358 292277 347269 429390 429391 207376 207375 265547 265546 391197 391198 153429 153428 197014 1...
output:
16
result:
ok 1 number(s): "16"
Test #36:
score: 0
Accepted
time: 162ms
memory: 7724kb
input:
500000 75259 75260 328529 388128 303264 478292 43503 43504 91134 77936 346755 346756 122076 122077 208385 208386 186361 435325 239193 407392 417363 456277 398486 372940 478743 308508 236116 236117 17300 17301 8685 8684 443669 393701 110599 115806 54776 35394 252686 252687 226624 343024 41182 38854 1...
output:
32
result:
ok 1 number(s): "32"
Test #37:
score: 0
Accepted
time: 161ms
memory: 7560kb
input:
500000 333063 335272 379861 379860 459364 461021 356577 353597 430299 430300 484313 480703 195914 195915 44882 44492 129128 129144 158887 155825 433328 432123 474438 474267 108629 108628 44069 42962 450834 450833 85142 85141 455531 455532 3186 3187 174759 174760 191008 189735 65150 65982 53448 53438...
output:
766755083
result:
ok 1 number(s): "766755083"
Test #38:
score: 0
Accepted
time: 146ms
memory: 7416kb
input:
500000 261422 263011 408790 405743 482131 482593 122043 121787 196162 195847 415804 413226 52656 52655 16338 17409 108303 108304 188710 188679 231394 233036 101423 107529 147795 147796 195317 195022 430411 431713 413076 413086 15491 15492 466757 466938 32972 32647 380388 380961 18094 18100 117442 11...
output:
967605111
result:
ok 1 number(s): "967605111"
Test #39:
score: 0
Accepted
time: 149ms
memory: 7536kb
input:
500000 391363 391612 34168 35067 123105 123104 241402 241403 195864 194401 364057 363666 29810 30629 229823 229824 66397 66398 486124 485014 313179 316359 331360 331359 56215 56772 345982 347012 96666 95352 218593 218523 55045 55044 414478 414477 136249 136250 236470 236521 369026 369944 9755 9754 1...
output:
930295578
result:
ok 1 number(s): "930295578"
Test #40:
score: 0
Accepted
time: 144ms
memory: 7484kb
input:
500000 355306 355305 140797 140796 104619 104618 316529 316530 135701 135722 247514 247513 88344 88327 410069 410070 57292 57291 189056 189111 228405 228384 211804 211803 336096 335959 152077 152079 474402 474370 369678 369687 47874 47881 167762 167761 396184 396185 30774 30773 412666 412665 35737 3...
output:
722525511
result:
ok 1 number(s): "722525511"
Test #41:
score: 0
Accepted
time: 140ms
memory: 7524kb
input:
500000 464294 464279 431832 431833 339745 339740 125826 125819 58301 58300 97908 97909 33597 33596 91189 91188 65715 65716 218149 218148 220522 220508 455877 455883 114151 114152 50566 50565 382164 382166 458753 458754 313641 313640 1206 1208 228632 228636 248510 248509 126358 126339 377136 377135 4...
output:
196867112
result:
ok 1 number(s): "196867112"
Test #42:
score: 0
Accepted
time: 143ms
memory: 7520kb
input:
500000 152484 152492 153158 153155 166883 166882 413394 413395 211859 211858 256361 256360 17515 17514 127520 127548 417893 417906 301874 301873 256444 256448 240978 240981 4118 4119 180568 180562 35277 35292 430176 430177 59161 59162 247984 247987 456178 456198 247477 247476 184895 184872 91618 916...
output:
888438655
result:
ok 1 number(s): "888438655"
Test #43:
score: 0
Accepted
time: 134ms
memory: 7556kb
input:
500000 57435 57436 28384 28398 303887 303889 1075 1076 102998 102999 399340 399337 137134 137131 380299 380300 271688 271686 461504 461508 247426 247425 448913 448915 170610 170609 226561 226563 191082 191081 19495 19499 150353 150351 310399 310402 243884 243889 414505 414511 310327 310325 168265 16...
output:
78278423
result:
ok 1 number(s): "78278423"
Test #44:
score: 0
Accepted
time: 133ms
memory: 7472kb
input:
500000 193912 193915 363232 363229 197953 197958 11079 11078 161817 161818 142307 142304 447974 447975 212548 212550 373045 373044 480071 480069 431608 431607 345118 345120 222775 222776 449942 449941 249303 249305 204257 204256 426254 426251 392858 392859 27923 27926 289248 289247 469419 469422 295...
output:
792253081
result:
ok 1 number(s): "792253081"
Test #45:
score: 0
Accepted
time: 132ms
memory: 7488kb
input:
500000 381287 381286 320247 320250 375707 375708 460275 460276 379161 379163 198741 198742 237188 237189 460616 460615 106219 106221 220404 220405 390047 390046 107721 107723 460084 460085 407856 407859 412321 412317 235535 235534 325484 325485 138080 138079 264216 264217 204492 204491 400943 400941...
output:
526952120
result:
ok 1 number(s): "526952120"
Test #46:
score: 0
Accepted
time: 136ms
memory: 7712kb
input:
500000 460366 460367 237079 237080 283700 283699 410735 410734 410219 410218 193927 193928 375657 375658 303162 303161 349315 349316 34267 34268 394941 394940 34104 34105 189339 189338 155894 155893 366703 366702 359004 359005 130280 130281 347721 347722 251756 251757 378063 378062 435383 435384 373...
output:
97555046
result:
ok 1 number(s): "97555046"
Extra Test:
score: -3
Extra Test Failed : Wrong Answer on 1
time: 1ms
memory: 3596kb
input:
5 1 2 1 3 1 4 2 3 2 4 3 4 1 2 4 5
output:
4
result:
wrong answer 1st numbers differ - expected: '0', found: '4'