QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #392161 | #4686. Tours | chenyitaoooo | WA | 1ms | 4312kb | C++14 | 1.2kb | 2024-04-17 10:31:28 | 2024-04-17 10:31:29 |
Judging History
answer
#include<bits/stdc++.h>
#define LL unsigned long long
#define Ri register int
using namespace std;
const int N=2005;
mt19937_64 rnd(time(0));
LL hs[N];
unordered_map<LL,int>A;
int h[N],cnt=2,tot,fa[N],dfn[N],n,m;
struct abc{
int to,nxt,id;
}e[N*2];
void add(int u,int v,int id){
e[cnt].to=v;
e[cnt].nxt=h[u];
e[cnt].id=id;
h[u]=cnt++;
}
void dfs(int s){
dfn[s]=++tot;
for(Ri i=h[s]; i!=0; i=e[i].nxt){
int v=e[i].to;
if(dfn[v]==0) fa[v]=s,dfs(v);
else{
if(fa[v]==s || fa[s]==v) continue;
if(dfn[v]<dfn[s]){
LL o=rnd();
hs[s]^=o,hs[v]^=o,A[o]++;
}
}
}
}
void dfs2(int s){
for(Ri i=h[s]; i!=0; i=e[i].nxt){
int v=e[i].to;
if(fa[v]==s) dfs2(v),hs[s]^=hs[v];
}
}
int main(){
scanf("%d %d",&n,&m);
for(Ri i=1; i<=m; ++i){
int x,y;
scanf("%d %d",&x,&y);
add(x,y,i),add(y,x,i);
}
for(Ri i=1; i<=n; ++i){
if(dfn[i]==0) dfs(i),dfs2(i);
}
for(Ri i=1; i<=n; ++i){
// printf("%llu ",hs[i]);
if(hs[i]!=0) A[hs[i]]++;
}
int ans=0;
for(Ri i=1; i<=n; ++i){
if(A[hs[i]]>0){
// printf("%llu %d\n",hs[i],A[hs[i]]);
ans=__gcd(ans,A[hs[i]]),A[hs[i]]=0;
}
}
for(Ri i=1; i<=ans; ++i){
if(ans%i==0) printf("%d ",i);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4180kb
input:
4 5 1 2 2 3 3 4 1 4 1 3
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
6 6 1 2 2 3 1 3 1 4 2 5 3 6
output:
1 3
result:
ok 2 number(s): "1 3"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
4 5 1 2 3 4 2 3 1 4 1 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 4176kb
input:
6 6 1 2 2 3 1 4 2 5 1 3 3 6
output:
1 3
result:
ok 2 number(s): "1 3"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
9 10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 1 8 4 9 6 9
output:
1 2
result:
ok 2 number(s): "1 2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
6 7 1 2 2 3 3 4 4 5 5 6 1 6 3 6
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3884kb
input:
33 36 2 22 12 18 27 28 9 19 26 27 6 21 15 16 2 3 7 24 3 12 4 23 28 29 5 14 29 30 1 10 11 13 6 13 16 25 14 21 4 16 10 19 10 11 5 15 1 8 3 20 7 13 25 26 29 31 17 23 8 18 12 24 25 30 31 32 17 20 15 22 9 18
output:
1 3
result:
ok 2 number(s): "1 3"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
33 35 10 13 6 13 9 19 5 15 29 31 2 3 4 16 3 20 7 13 31 32 12 24 2 22 17 23 26 27 17 20 16 25 3 12 28 29 1 8 12 18 27 28 14 21 10 19 25 26 5 14 15 16 9 18 4 23 25 30 1 10 8 18 7 24 29 30 6 21 15 22
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: 0
Accepted
time: 1ms
memory: 4188kb
input:
2000 2000 1036 1254 1453 1496 342 1815 186 346 840 1555 138 1503 416 1376 660 1253 1279 1799 209 1554 624 1278 792 884 333 1703 393 894 551 1192 1705 1805 302 930 115 1384 151 1156 71 209 82 1637 858 1854 19 1798 348 703 1692 1744 261 1029 143 1631 336 1227 1493 1564 493 1966 553 1587 953 1128 214 1...
output:
1 2 4 5 8 10 16 20 25 40 50 80 100 125 200 250 400 500 1000 2000
result:
ok 20 numbers
Test #10:
score: 0
Accepted
time: 1ms
memory: 3996kb
input:
1820 1872 677 1254 114 163 1751 1815 532 1640 290 380 253 1429 174 1163 1005 1431 521 1324 37 1553 369 1764 658 1170 1456 1574 224 663 752 1460 128 441 831 1013 730 1583 500 983 374 1274 1394 1478 422 1223 1310 1632 1133 1508 914 1258 151 907 221 233 549 1374 342 895 1591 1699 1041 1273 231 747 1419...
output:
1 2 3 6 9 18
result:
ok 6 numbers
Test #11:
score: 0
Accepted
time: 1ms
memory: 4236kb
input:
1521 1584 1138 1283 95 542 137 1042 1043 1390 147 1396 382 709 651 828 909 1124 286 1485 31 171 925 1254 360 501 900 1229 69 1358 166 199 633 1178 310 1390 679 1482 844 1333 761 1208 38 1512 449 875 13 1467 77 217 622 736 45 1163 365 1346 106 1084 494 832 465 930 283 771 704 1468 375 870 82 1336 113...
output:
1 2 3 4 6 12
result:
ok 6 numbers
Test #12:
score: 0
Accepted
time: 1ms
memory: 4280kb
input:
1433 1467 43 1268 90 1143 237 271 444 1375 232 1407 1026 1139 861 943 981 1003 77 1229 416 966 606 1370 351 438 687 1379 1030 1186 1373 1428 715 762 553 1426 238 1012 120 618 345 857 827 1118 548 1085 245 333 82 910 202 570 80 781 666 797 122 1022 75 989 674 881 298 1139 160 584 801 1085 607 715 751...
output:
1 3 9
result:
ok 3 number(s): "1 3 9"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3944kb
input:
1569 1625 1043 1553 57 369 481 1231 99 227 113 262 239 354 175 887 819 1230 27 115 76 820 1086 1498 482 1193 1299 1447 570 604 121 508 100 208 77 572 52 1296 198 639 103 945 256 381 745 1173 1033 1350 13 1414 233 1399 402 1417 1394 1441 206 623 264 482 1155 1336 1176 1433 50 1066 542 850 666 1508 80...
output:
1 5
result:
ok 2 number(s): "1 5"
Test #14:
score: 0
Accepted
time: 1ms
memory: 3956kb
input:
1035 1072 448 654 201 211 139 650 224 255 430 883 494 517 199 999 717 763 661 813 145 574 68 908 626 990 7 805 54 875 600 968 279 462 335 543 266 665 598 676 177 447 790 1034 273 909 475 814 464 973 210 560 290 905 650 708 288 994 10 183 261 564 492 967 273 300 481 735 184 1013 123 911 536 550 460 5...
output:
1 2 4 8
result:
ok 4 number(s): "1 2 4 8"
Test #15:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
162 198 41 83 15 121 29 76 62 75 78 114 58 80 5 75 85 119 45 137 3 56 149 156 46 63 79 107 125 150 33 78 43 149 27 87 20 33 13 136 60 90 60 110 30 97 102 152 25 31 6 79 24 67 16 78 68 115 77 78 103 124 117 161 117 139 55 67 19 146 45 112 26 104 45 49 108 144 145 154 130 134 13 111 57 78 35 159 4 65 ...
output:
1 3
result:
ok 2 number(s): "1 3"
Test #16:
score: 0
Accepted
time: 1ms
memory: 4004kb
input:
1894 1932 384 1664 1204 1508 733 1583 818 1515 879 1799 197 1165 657 919 559 1893 241 1104 347 1283 516 916 179 1041 305 477 1116 1135 1254 1561 280 742 269 975 34 862 1033 1659 74 382 307 1600 99 1553 1298 1565 955 1579 308 478 947 1595 1686 1793 190 1836 878 1260 732 1498 889 1570 436 1723 393 100...
output:
1 7
result:
ok 2 number(s): "1 7"
Test #17:
score: 0
Accepted
time: 1ms
memory: 4312kb
input:
63 1953 24 25 30 53 16 28 20 36 34 51 33 52 3 11 9 35 28 52 52 54 22 51 33 46 2 45 35 43 4 48 4 35 2 7 26 59 21 35 21 43 9 58 37 63 7 26 17 32 7 11 34 56 6 54 18 62 33 44 15 52 50 53 17 46 12 42 9 31 9 11 35 47 1 13 21 42 26 43 2 24 27 35 5 39 6 9 1 51 16 46 6 62 18 34 59 63 22 62 22 53 14 39 49 55 ...
output:
1
result:
ok 1 number(s): "1"
Test #18:
score: 0
Accepted
time: 1ms
memory: 4312kb
input:
89 1939 29 62 14 25 5 60 24 26 1 8 3 68 47 85 41 81 47 55 22 75 20 37 42 87 46 53 48 55 54 72 61 66 7 43 70 74 63 89 29 51 21 56 18 49 20 31 14 34 22 85 75 86 52 68 12 32 44 55 41 42 37 82 36 82 5 67 52 74 5 18 35 40 14 60 11 14 7 10 46 82 7 60 40 62 18 29 71 72 82 88 21 63 15 59 15 16 23 81 11 87 2...
output:
1
result:
ok 1 number(s): "1"
Test #19:
score: 0
Accepted
time: 1ms
memory: 4048kb
input:
409 1944 69 134 162 172 50 327 3 17 152 256 19 302 246 371 289 394 228 376 210 270 318 336 352 405 171 324 21 398 70 236 68 349 316 344 84 386 223 344 125 223 293 327 88 253 39 165 151 395 201 322 68 403 336 383 215 256 73 138 5 399 260 268 189 272 13 248 145 154 62 304 115 376 34 399 262 347 317 39...
output:
1
result:
ok 1 number(s): "1"
Test #20:
score: 0
Accepted
time: 1ms
memory: 4048kb
input:
509 1828 245 248 384 386 127 261 260 480 437 466 127 382 158 476 482 498 241 375 159 216 232 408 74 270 32 293 126 249 59 445 146 291 129 234 81 164 243 437 258 262 229 320 126 185 118 423 221 488 185 204 220 227 96 472 112 149 106 432 46 100 399 494 38 306 174 290 76 497 20 396 33 66 102 325 60 417...
output:
1
result:
ok 1 number(s): "1"
Test #21:
score: 0
Accepted
time: 1ms
memory: 4052kb
input:
2000 1999 1552 1932 553 1152 1006 1967 606 1381 1549 1775 1283 1992 994 1000 367 1864 1047 1989 475 1284 1033 1688 827 1786 746 1018 651 756 73 1178 307 539 114 1924 653 667 693 1087 222 1656 241 1841 165 1725 433 476 66 1099 169 1490 609 1257 506 1108 691 1513 1111 1683 1044 1811 1107 1885 839 886 ...
output:
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 30 32 36 40 45 48 60 72 80 90 96 120 144 160 180 240 288 360 480 720 1440
result:
ok 36 numbers
Test #22:
score: 0
Accepted
time: 0ms
memory: 4044kb
input:
1302 1302 893 1045 149 798 202 1034 252 789 269 920 915 989 96 496 1142 1302 647 868 54 1127 161 704 128 1294 51 718 325 825 423 798 344 809 504 1070 548 756 276 1116 8 41 782 1294 602 685 137 976 315 1028 75 562 36 1208 20 302 383 1080 62 392 167 1022 7 126 452 595 791 1182 57 1061 295 842 457 1276...
output:
1 2 3 6 7 14 21 42
result:
ok 8 numbers
Test #23:
score: 0
Accepted
time: 1ms
memory: 4008kb
input:
1932 1989 390 911 1384 1761 679 791 931 1855 315 1346 201 331 167 1560 72 1206 255 1838 1777 1854 693 1869 1225 1343 588 825 904 1120 413 773 853 1521 884 924 628 638 370 1080 1004 1821 342 817 1315 1448 289 352 1389 1730 921 1602 880 1307 164 263 284 1624 500 1928 130 260 1177 1583 1871 1915 1248 1...
output:
1 17
result:
ok 2 number(s): "1 17"
Test #24:
score: 0
Accepted
time: 1ms
memory: 3932kb
input:
561 572 290 330 81 158 158 166 501 548 387 482 54 121 521 535 106 397 263 466 230 520 332 400 55 374 182 209 138 219 154 506 494 510 45 346 190 421 290 383 56 361 123 157 380 538 345 525 225 318 82 356 40 340 245 451 420 520 470 556 279 347 95 102 333 378 71 76 12 513 19 109 260 325 93 277 19 353 40...
output:
1 13
result:
ok 2 number(s): "1 13"
Test #25:
score: 0
Accepted
time: 1ms
memory: 3876kb
input:
573 585 96 357 358 495 136 375 200 538 1 112 170 524 125 273 189 572 525 562 24 443 152 173 224 250 470 572 76 299 289 371 161 561 269 435 114 122 225 442 65 175 207 319 73 469 6 327 144 357 389 557 256 534 398 413 87 413 519 567 312 353 40 60 142 553 111 508 416 568 344 520 499 549 99 546 90 319 12...
output:
1
result:
ok 1 number(s): "1"
Test #26:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
230 246 13 198 31 100 54 181 10 211 210 218 151 178 175 228 66 164 15 81 156 214 36 200 154 228 73 84 57 210 127 144 81 167 131 154 40 143 86 157 48 58 208 230 164 230 4 132 22 159 67 138 63 78 171 184 69 121 51 209 9 38 111 167 65 75 18 217 120 146 35 186 165 204 119 225 163 223 143 144 76 80 95 14...
output:
1 2 3 6
result:
ok 4 number(s): "1 2 3 6"
Test #27:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
436 468 328 330 46 78 219 400 165 329 278 391 45 387 166 402 66 213 102 358 185 368 91 136 33 378 73 102 111 150 95 405 150 402 6 223 119 351 110 381 178 407 175 212 379 416 153 310 198 241 259 319 114 177 66 341 26 354 302 364 232 385 175 397 23 432 252 355 40 300 128 420 25 332 253 403 97 125 21 3...
output:
1 3 9
result:
ok 3 number(s): "1 3 9"
Test #28:
score: 0
Accepted
time: 1ms
memory: 3932kb
input:
2000 714 13 198 31 100 54 181 10 211 210 218 151 178 175 228 66 164 15 81 156 214 36 200 154 228 73 84 57 210 127 144 81 167 131 154 40 143 86 157 48 58 208 230 164 230 4 132 22 159 67 138 63 78 171 184 69 121 51 209 9 38 111 167 65 75 18 217 120 146 35 186 165 204 119 225 163 223 143 144 76 80 95 1...
output:
1 3
result:
ok 2 number(s): "1 3"
Test #29:
score: 0
Accepted
time: 1ms
memory: 4228kb
input:
2000 715 13 198 31 100 54 181 10 211 210 218 151 178 175 228 66 164 15 81 156 214 36 200 154 228 73 84 57 210 127 144 81 167 131 154 40 143 86 157 48 58 208 230 164 230 4 132 22 159 67 138 63 78 171 184 69 121 51 209 9 38 111 167 65 75 18 217 120 146 35 186 165 204 119 225 163 223 143 144 76 80 95 1...
output:
1 3
result:
ok 2 number(s): "1 3"
Test #30:
score: 0
Accepted
time: 1ms
memory: 3988kb
input:
1725 1990 597 1010 914 1360 1005 1490 854 944 292 383 230 745 259 1658 944 1281 485 586 193 1268 1231 1375 1409 1472 1069 1451 1409 1630 252 1304 766 988 1122 1458 265 1682 510 1078 775 845 138 1030 435 743 1040 1357 278 986 754 872 493 1645 1144 1574 679 1234 1017 1123 151 1026 951 1200 1506 1637 4...
output:
1 5
result:
ok 2 number(s): "1 5"
Test #31:
score: 0
Accepted
time: 0ms
memory: 4052kb
input:
1827 1992 620 1798 467 1613 264 1212 200 258 1660 1729 74 1326 327 1069 1051 1363 428 501 78 1439 513 1393 343 855 705 1396 370 897 553 1323 190 1776 1137 1192 194 1767 841 1068 99 1216 1378 1439 332 1012 132 443 243 914 944 1419 1177 1523 87 1818 635 1118 183 1763 1280 1295 940 1187 1559 1663 498 1...
output:
1 2 4
result:
ok 3 number(s): "1 2 4"
Test #32:
score: 0
Accepted
time: 1ms
memory: 3920kb
input:
1760 1980 536 1508 254 1599 1064 1521 319 1216 866 1361 279 647 39 227 1530 1537 568 1676 1156 1242 916 1597 409 927 91 909 815 1001 160 1278 195 1007 39 848 493 1386 55 1288 476 1624 1304 1745 43 1521 217 602 661 1499 13 1695 1184 1428 144 335 862 1180 1274 1557 550 817 539 857 1066 1437 95 1479 11...
output:
1 3
result:
ok 2 number(s): "1 3"
Test #33:
score: 0
Accepted
time: 1ms
memory: 3972kb
input:
1856 1990 799 1430 856 1191 151 1851 793 1353 117 1144 858 936 890 1110 714 740 1158 1754 1394 1849 555 1652 416 1077 1706 1751 267 1394 64 714 88 1334 903 1087 204 290 622 1772 520 725 381 798 506 1794 305 1660 37 66 10 619 1270 1692 264 634 598 974 1284 1768 877 1306 56 962 269 286 484 1558 191 10...
output:
1 5
result:
ok 2 number(s): "1 5"
Test #34:
score: 0
Accepted
time: 1ms
memory: 4056kb
input:
1997 1998 994 1781 670 1387 843 1075 1277 1770 784 1533 675 1192 1047 1323 267 1405 561 565 681 1749 243 421 31 1798 537 1856 1757 1878 1941 1986 25 1465 759 1587 6 1133 549 1044 1429 1819 557 1346 363 1761 936 1147 487 855 1931 1978 1339 1484 220 613 349 1667 286 1443 123 966 359 1124 1286 1987 131...
output:
1 2 3 6 9 18 37 74 111 222 333 666
result:
ok 12 numbers
Test #35:
score: 0
Accepted
time: 1ms
memory: 3924kb
input:
1652 1988 1297 1437 315 389 138 1096 1317 1474 1310 1315 194 601 939 977 332 1295 275 1502 1039 1326 878 1248 1034 1293 283 454 1372 1452 942 996 1133 1226 285 1111 537 1291 459 1200 799 1074 811 1620 582 1190 714 1376 695 1117 1198 1305 778 869 197 1362 760 1017 1492 1495 709 1400 466 1499 1258 156...
output:
1 2
result:
ok 2 number(s): "1 2"
Test #36:
score: 0
Accepted
time: 1ms
memory: 3980kb
input:
1772 1986 777 1502 1511 1719 1324 1385 1412 1491 302 1246 451 1258 1201 1407 850 872 1002 1292 866 1150 572 1748 1084 1210 234 1105 736 854 1015 1068 599 637 1172 1549 1545 1623 222 694 512 1268 424 592 877 1315 3 237 466 1366 1060 1692 437 1101 1223 1334 768 1468 1257 1711 302 1585 1729 1763 487 73...
output:
1 3
result:
ok 2 number(s): "1 3"
Test #37:
score: 0
Accepted
time: 1ms
memory: 3920kb
input:
1817 1984 387 625 1077 1128 1222 1780 2 739 1184 1626 1 681 1269 1360 244 1129 602 1304 703 1244 1631 1697 404 1769 110 1618 890 1140 1239 1787 12 360 209 681 345 1451 923 1322 128 1795 263 979 315 1393 689 1073 20 1340 10 34 961 1669 471 1739 121 620 444 988 98 1321 180 426 1428 1607 1420 1432 188 ...
output:
1 2 4
result:
ok 3 number(s): "1 2 4"
Test #38:
score: 0
Accepted
time: 1ms
memory: 4232kb
input:
1834 1970 510 1085 329 1732 348 535 417 1573 936 1111 668 1591 235 1702 60 1179 1334 1354 167 1122 128 1518 349 958 390 807 473 1370 461 1131 75 380 922 1433 288 419 265 847 358 803 319 412 1439 1527 348 458 1015 1539 1553 1799 256 1055 269 1304 585 1791 240 1315 325 1645 120 676 518 804 364 663 158...
output:
1 2 5 10
result:
ok 4 number(s): "1 2 5 10"
Test #39:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
1849 1956 1513 1642 503 1259 962 1582 1164 1313 753 1103 80 890 135 1241 1177 1483 923 1479 745 1548 448 1119 228 1354 1206 1388 840 1479 1686 1807 1360 1427 161 1456 772 1424 929 1066 401 877 230 1753 1676 1820 500 1292 478 759 455 1559 918 1135 255 652 1409 1485 1170 1400 1094 1817 105 499 326 179...
output:
1 2 3 6
result:
ok 4 number(s): "1 2 3 6"
Test #40:
score: 0
Accepted
time: 0ms
memory: 3992kb
input:
1891 1988 679 1696 208 1175 202 1118 354 1713 137 1183 152 1634 829 1129 558 712 758 1322 1050 1789 446 952 468 904 259 1705 560 652 589 1308 1163 1713 988 1150 697 1534 128 324 7 895 1023 1515 1710 1876 1486 1571 160 743 249 1884 14 1000 651 1154 622 1325 166 1239 745 1268 1482 1525 127 491 62 419 ...
output:
1 7
result:
ok 2 number(s): "1 7"
Test #41:
score: -100
Wrong Answer
time: 1ms
memory: 3896kb
input:
6 7 1 2 2 3 1 4 2 5 3 6 4 5 5 6
output:
1 3
result:
wrong answer Output contains longer sequence [length = 2], but answer contains 1 elements