QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#880808 | #2708. Through Another Maze Darkly | hhoppitree | 0 | 1637ms | 13844kb | C++20 | 2.0kb | 2025-02-03 20:53:36 | 2025-02-03 20:53:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 8e5 + 5;
vector<int> G[N];
int fa[N], cur[N], in[N], out[N], ord[N << 1], ord_c;
vector< pair<long long, int> > qry;
int res[N];
void dfs(int x) {
if (fa[x]) {
int ini = G[x][0];
rotate(G[x].begin(), find(G[x].begin(), G[x].end(), fa[x]), G[x].end());
cur[x] = find(G[x].begin(), G[x].end(), ini) - G[x].begin();
}
in[x] = out[x] = ++ord_c, ord[ord_c] = x;
for (auto v : G[x]) {
if (v == fa[x]) continue;
fa[v] = x, dfs(v);
out[x] = ++ord_c, ord[ord_c] = x;
}
}
int usd[N];
long long clk;
void Dfs(int x) {
while (qry.back().first == clk) {
res[qry.back().second] = x;
qry.pop_back();
}
if (!usd[x]) {
usd[x] = (cur[x] == 0);
for (auto v : G[x]) {
if (v != fa[x]) usd[x] &= usd[v];
}
}
if (usd[x]) {
if (x == 1) {
while (!qry.empty()) {
res[qry.back().second] = ord[(qry.back().first - clk) % (out[x] - in[x]) + 1];
qry.pop_back();
}
return;
}
while (!qry.empty() && qry.back().first <= clk + (out[x] - in[x])) {
res[qry.back().second] = ord[in[x] + (qry.back().first - clk)];
qry.pop_back();
}
clk += out[x] - in[x];
++clk;
Dfs(G[x][0]);
return;
}
++clk;
cur[x] = (cur[x] + 1) % G[x].size();
Dfs(G[x][cur[x]]);
}
signed main() {
int n, q; scanf("%d%d", &n, &q);
for (int i = 1; i <= n; ++i) {
int x; scanf("%d", &x), G[i].resize(x);
for (auto &t : G[i]) scanf("%d", &t);
cur[i] = 0;
}
for (int i = 1; i <= q; ++i) {
long long x; scanf("%lld", &x);
qry.push_back({x, i});
}
sort(qry.rbegin(), qry.rend());
dfs(1), Dfs(1);
for (int i = 1; i <= q; ++i) printf("%d\n", res[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 4
Accepted
time: 0ms
memory: 12116kb
input:
2 50 1 2 1 1 483013971750400 493702549856377 4 5 1 4 381229502997833 382547776777558 4 5 935071356171379 1 4 5 3 916882396464891 45105149657595 175937189687321 832190252361123 173405899224767 37441426025858 912409855136716 123727567495025 655283329521574 4 2 3 1 863693821551240 1 520529294828528 1 3...
output:
1 2 1 2 2 1 2 1 1 2 2 2 1 2 2 2 2 2 2 2 1 1 2 1 1 1 2 2 1 2 1 2 2 1 2 1 1 2 2 2 2 2 2 2 2 2 2 2 1 2
result:
ok 50 lines
Test #2:
score: 4
Accepted
time: 1637ms
memory: 13844kb
input:
10000 10000 1 2 2 1 3 2 4 2 2 5 3 2 4 6 2 5 7 2 6 8 2 7 9 2 10 8 2 11 9 2 12 10 2 11 13 2 14 12 2 13 15 2 16 14 2 15 17 2 16 18 2 17 19 2 20 18 2 21 19 2 20 22 2 21 23 2 24 22 2 25 23 2 24 26 2 27 25 2 28 26 2 29 27 2 28 30 2 29 31 2 32 30 2 33 31 2 34 32 2 35 33 2 34 36 2 35 37 2 38 36 2 37 39 2 40...
output:
5469 3362 4022 5239 303 4942 9052 1321 5178 4470 972 8879 1547 4460 2181 2578 5421 5343 763 9715 1146 4989 244 2884 1155 5396 6393 114 1127 3565 679 678 4342 2506 7026 1240 9240 3521 617 4739 4846 4151 3380 5510 2231 5960 715 265 799 3619 3753 2085 1843 930 584 2017 4361 2204 6691 1689 7681 7577 163...
result:
ok 10000 lines
Test #3:
score: 0
Time Limit Exceeded
input:
100000 100000 1 2 2 1 3 2 4 2 2 5 3 2 4 6 2 7 5 2 6 8 2 9 7 2 10 8 2 9 11 2 10 12 2 11 13 2 12 14 2 13 15 2 16 14 2 17 15 2 18 16 2 19 17 2 18 20 2 19 21 2 20 22 2 23 21 2 22 24 2 25 23 2 24 26 2 25 27 2 26 28 2 29 27 2 28 30 2 29 31 2 30 32 2 33 31 2 34 32 2 35 33 2 36 34 2 35 37 2 38 36 2 39 37 2 ...
output:
result:
Subtask #2:
score: 0
Wrong Answer
Test #8:
score: 4
Accepted
time: 1ms
memory: 12184kb
input:
100 1999 1 81 2 31 23 2 35 30 1 89 2 96 46 1 73 2 15 55 1 95 2 81 48 2 88 26 2 98 44 2 54 52 2 92 64 1 61 3 7 79 91 1 47 2 23 60 1 61 1 46 2 91 73 1 30 1 78 2 17 2 3 28 51 71 2 86 46 3 62 10 57 1 80 2 24 36 1 56 2 21 3 1 2 1 51 1 75 2 38 88 2 3 90 3 64 28 41 3 95 72 96 1 34 3 77 45 78 2 90 52 1 36 2...
output:
40 68 80 93 53 92 16 24 75 56 51 50 63 9 76 73 64 56 10 91 26 64 47 13 76 44 25 81 7 74 21 36 100 1 56 57 81 94 59 36 59 28 20 64 9 42 93 32 15 50 76 46 10 15 95 46 89 9 37 97 52 47 92 96 62 20 52 72 45 61 68 44 1 49 12 29 20 90 4 42 93 88 93 43 48 84 87 59 69 34 6 100 47 34 68 94 7 72 71 94 1 93 64...
result:
ok 1999 lines
Test #9:
score: 4
Accepted
time: 1ms
memory: 12208kb
input:
300 2000 1 12 2 31 64 1 183 1 227 1 191 2 67 265 3 297 45 138 2 156 81 2 38 57 1 300 4 89 217 258 91 4 1 119 50 283 1 140 1 186 3 40 89 167 3 82 299 263 3 233 65 199 2 265 54 1 145 3 74 34 75 2 70 40 1 224 2 288 71 1 39 1 212 1 212 1 32 2 165 272 1 132 1 268 2 227 2 3 27 173 144 1 130 3 20 105 253 4...
output:
80 117 7 144 64 90 191 248 119 183 13 107 96 283 279 275 48 205 48 125 107 291 13 15 90 253 147 276 162 240 101 180 277 53 175 80 268 89 96 253 219 251 282 126 54 236 194 149 164 156 297 152 59 139 47 81 130 94 290 20 149 89 62 188 257 234 215 16 14 130 45 96 182 184 6 263 94 183 190 56 215 210 80 1...
result:
ok 2000 lines
Test #10:
score: 4
Accepted
time: 6ms
memory: 12248kb
input:
1000 1999 1 922 3 801 144 493 2 86 439 1 185 2 752 321 2 168 195 1 221 2 358 526 1 74 2 972 547 3 728 601 295 2 766 876 2 190 443 3 974 520 211 2 141 668 2 544 66 1 644 3 881 964 398 2 819 471 1 769 2 888 121 2 534 865 2 176 66 2 426 47 2 609 263 2 232 145 3 335 917 568 2 812 967 2 131 476 3 562 319...
output:
627 370 45 825 139 338 962 135 808 588 73 649 677 137 538 437 171 374 479 775 456 532 301 580 767 162 952 561 96 984 982 233 182 186 99 780 876 519 27 808 926 284 548 28 280 87 616 527 422 983 371 566 384 138 836 789 539 563 12 19 97 670 458 99 860 204 58 431 348 578 929 121 557 701 217 116 347 891 ...
result:
ok 1999 lines
Test #11:
score: 4
Accepted
time: 1ms
memory: 12316kb
input:
2000 2000 1 1460 2 1930 1024 2 607 532 1 1502 3 153 1236 1441 1 1531 1 1342 1 1277 2 1191 1101 1 597 1 648 2 1238 701 1 1421 2 1749 1831 1 1424 4 1756 555 1040 1507 1 1244 1 510 2 839 1844 4 347 461 1415 1220 3 320 859 1789 1 841 3 1358 1640 751 2 1965 265 2 1206 70 1 1652 1 940 3 1636 864 159 5 532...
output:
1839 154 62 975 1927 491 337 254 833 1153 1716 1854 1933 689 20 1763 675 1425 979 832 61 1364 1137 807 169 853 1635 1606 403 450 164 211 1595 1918 1030 1613 1996 688 361 823 1671 951 1032 1257 203 735 641 393 1890 408 1957 1619 169 39 1402 253 1918 945 407 1962 1358 357 1856 1244 115 463 5 1915 1772...
result:
ok 2000 lines
Test #12:
score: 4
Accepted
time: 2ms
memory: 12268kb
input:
2000 2000 1 465 1 219 7 1613 96 1758 171 1352 677 486 1 106 5 804 1934 1259 1840 1206 1 1867 2 1082 247 2 1508 823 1 1061 1 457 1 24 3 771 1444 1285 1 1854 3 864 1070 305 1 1004 2 191 1158 1 1817 1 726 2 1383 1373 2 1069 1074 1 1667 3 687 788 797 4 914 1811 1795 584 3 11 1293 1047 1 416 2 628 1451 1...
output:
541 1889 753 747 1383 903 717 988 741 90 1225 921 243 1906 541 1617 920 913 1836 1109 391 136 509 300 1538 393 1488 385 1369 1264 1338 594 1664 777 308 148 1724 498 1599 1917 282 239 1563 1541 164 556 580 1341 335 1026 1793 317 501 441 1769 1693 297 732 1899 480 1177 1011 777 1280 1921 1425 1853 107...
result:
ok 2000 lines
Test #13:
score: 4
Accepted
time: 4ms
memory: 12312kb
input:
2000 2000 1 1480 1 1224 5 1019 1067 394 953 1336 1 894 2 985 984 10 1125 743 1043 1704 185 1369 24 204 105 1981 2 1397 666 3 203 172 1640 1 384 2 1483 686 1 861 1 1738 1 211 2 542 213 3 200 84 671 3 811 1445 411 1 527 1 118 2 1267 222 2 846 1843 1 1797 1 823 1 1955 3 6 927 872 1 481 1 1929 5 1183 64...
output:
496 659 654 694 1972 1085 1801 1672 1979 1777 376 466 1575 1974 1258 438 265 647 1098 981 598 1197 472 1829 1101 552 1376 15 622 325 636 121 755 535 1257 1929 1542 1734 697 1279 1281 1014 1245 1271 804 998 354 1716 1140 22 182 200 1455 118 275 967 957 1125 701 1636 101 1392 1437 447 1218 1895 481 18...
result:
ok 2000 lines
Test #14:
score: 0
Wrong Answer
time: 1ms
memory: 12316kb
input:
2000 2000 3 1965 867 216 3 504 203 1669 1 1363 4 787 1341 1487 1737 3 604 1134 1379 3 1783 1141 1676 2 23 877 1 196 3 526 230 566 1 710 2 1128 353 3 873 1542 1415 3 1055 1080 449 1 817 3 242 1259 1016 2 389 539 1 1920 3 1048 1297 495 2 1498 212 4 1096 779 434 1447 1 1208 1 655 4 1574 7 668 851 1 402...
output:
1366 1046 1348 1003 1350 840 1687 498 1770 1783 1472 13 740 1078 75 394 719 526 156 896 747 805 116 77 1959 67 879 165 723 1035 486 1054 32 88 291 1579 2 1176 795 1643 501 834 1543 578 301 1385 1138 783 43 534 1003 176 193 896 1091 1239 569 1203 1555 1845 643 1254 594 1051 1265 754 1607 1362 1893 6 ...
result:
wrong answer 36th lines differ - expected: '1369', found: '1579'
Subtask #3:
score: 0
Time Limit Exceeded
Test #22:
score: 12
Accepted
time: 418ms
memory: 13068kb
input:
10000 1 2 3966 68 3 2420 8027 7361 4 4397 3878 7053 3025 1 3527 1 6483 1 6315 1 6766 1 3578 1 7847 2 736 1196 2 5323 1422 4 185 6443 1672 2620 2 9096 3858 4 6059 7339 320 6152 2 9992 8688 1 3759 1 9465 2 7095 7885 1 5026 1 7073 1 3167 2 2357 5976 3 5923 3540 2909 1 5943 4 3999 8702 310 7596 2 3397 3...
output:
4514
result:
ok single line: '4514'
Test #23:
score: 0
Time Limit Exceeded
input:
50000 1 2 15283 20176 1 5327 2 2011 12771 2 12567 27002 2 42574 44146 2 18013 4544 3 26813 813 15729 3 8128 29696 48494 2 26583 39839 1 37109 2 20729 32370 3 14178 6531 24505 3 8387 45873 30531 4 29722 38862 48458 32534 1 19633 3 43804 5234 15918 2 45699 31966 1 40759 4 21540 9672 18134 47351 2 3795...
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
0%