QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#859783 | #2708. Through Another Maze Darkly | GGapaggl | 25 ✓ | 938ms | 375376kb | C++14 | 3.3kb | 2025-01-17 23:31:27 | 2025-01-17 23:31:27 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwrh = (b); i <= stOwrh; i++)
#define per(i, a, b) for(int i = (a), stOwrh = (b); i >= stOwrh; i--)
#define int long long
using namespace std;
using LL = long long;
using VI = vector<int>;
using AI = array<int, 2>;
struct DSU {
vector<int> fa;
DSU() {}
DSU(int n) {init(n); }
void init(int n) {
fa.resize(n + 1);
iota(fa.begin(), fa.end(), 0);
}
int find(int x) {
while(x != fa[x]) x = fa[x] = fa[fa[x]];
return x;
}
bool merge(int x, int y) {
x = find(x), y = find(y);
if(x == y) return false;
fa[x] = y;
return true;
}
bool same(int x, int y) {
return find(x) == find(y);
}
}dsu;
constexpr int N = 2e6 + 5;
int n, q;
int dfn[N], fa[N], fst[N], lst[N], nxt[N], tag[N], ans[N];
AI que[N];
vector<int> G[N], ps[N], T[N];
void dfs(int x) {
for(auto to : G[x]) if(to != fa[x])
fa[to] = x, dfs(to);
}
void dfs1(int x) {
int &tim = dfn[N - 1];
dfn[++tim] = x, ps[x].emplace_back(tim); fst[x] = tim;
for(auto to : T[x]) {
dfs1(to);
dfn[++tim] = x, ps[x].emplace_back(tim);
}
}
void del(int x) {
// nxt[x] = dsu.find(x % dfn[N - 1] + 1);
dsu.merge(x, x % dfn[N - 1] + 1);
tag[x] = 0;
}
int calc(int x, int y) {
x += y; x %= dfn[N - 1];
if(x == 0) x = dfn[N - 1];
return dfn[x];
}
int dis(int x, int y) {
return (x < y ? y - x : dfn[N - 1] + y - x);
}
void work(int p, int tim, int qt) {
int x = dfn[p];
if(tag[p]) {
for(auto it : ps[x]) del(it);
while(qt <= q && que[qt][0] == tim) ans[que[qt][1]] = x, qt++;
work(G[x][G[x].size() > 1], tim + 1, qt);
}
else {
int np = dsu.find(p);
if(!tag[np]) {
while(qt <= q) ans[que[qt][1]] = calc(p, que[qt][0] - tim), qt++;
return ;
}
int nt = tim + dis(p, np);
while(qt <= q && que[qt][0] < nt) ans[que[qt][1]] = calc(p, que[qt][0] - tim), qt++;
work(np, nt, qt);
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> q;
vector<int> deg(n + 1);
rep(i, 1, n) {
cin >> deg[i];
for(int j = 1, x; j <= deg[i]; j++)
cin >> x, G[i].emplace_back(x);
}
dfs(1);
rep(i ,1, n) {
int pos = 0;
if(i != 1) while(G[i][pos] != fa[i]) pos++;
(pos += 1) %= deg[i];
for(int j = 1; j <= deg[i] && G[i][pos] != fa[i]; (pos += 1) %= deg[i], j++)
T[i].emplace_back(G[i][pos]);
}
dfs1(1); dfn[N - 1]--;
dsu.init(dfn[N - 1] + 10);
per(i, dfn[N - 1], 1) {
int x = dfn[i]; lst[x] = i;
if(fst[x] == i) {
for(auto &to : G[x]) {
if(!lst[to]) to = fst[to];
else to = lst[to];
}
}
}
rep(i, 1, q) cin >> que[i][0], que[i][1] = i;
sort(que +1, que + 1 + q);
fill_n(tag, N, 1);
fill_n(ans, N, -1);
work(1, 0, 1);
rep(i ,1, q) cout << ans[i] << '\n';
// rep(i, 1, dfn[N - 1]) cerr << fst[i] << " \n"[i == dfn[N - 1]];
// rep(i, 1, dfn[N - 1]) cerr << lst[i] << " \n"[i == dfn[N - 1]];
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 4
Accepted
Test #1:
score: 4
Accepted
time: 30ms
memory: 183220kb
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: 22ms
memory: 187180kb
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: 4
Accepted
time: 61ms
memory: 212212kb
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:
31379 30432 33347 46595 8067 27571 26757 35321 55063 1105 18874 66964 4228 83 32195 12401 58756 43534 35740 69026 34540 73840 24980 12726 3056 19085 58558 29514 53090 26632 50230 6403 24583 51658 50425 62238 9641 41793 39786 40065 62452 28110 39165 74121 12962 17341 80469 75340 46384 79336 58233 149...
result:
ok 100000 lines
Test #4:
score: 4
Accepted
time: 368ms
memory: 371256kb
input:
800000 800000 1 2 2 1 3 2 2 4 2 3 5 2 4 6 2 5 7 2 6 8 2 7 9 2 8 10 2 9 11 2 10 12 2 11 13 2 12 14 2 13 15 2 14 16 2 15 17 2 16 18 2 17 19 2 18 20 2 19 21 2 20 22 2 21 23 2 22 24 2 23 25 2 24 26 2 25 27 2 26 28 2 27 29 2 28 30 2 29 31 2 30 32 2 31 33 2 32 34 2 33 35 2 34 36 2 35 37 2 36 38 2 37 39 2 ...
output:
134368 98483 198192 491390 349324 533747 508517 311779 601207 216024 503799 169953 52289 319706 265768 146045 540942 500102 2441 193374 524434 481674 446295 789582 356275 789796 720195 234900 374666 654419 404212 44601 13185 164761 389167 428423 131890 68036 39951 423287 525186 432814 746826 717096 ...
result:
ok 800000 lines
Test #5:
score: 4
Accepted
time: 387ms
memory: 375208kb
input:
800000 800000 1 2 2 3 1 2 4 2 2 5 3 2 6 4 2 7 5 2 8 6 2 9 7 2 10 8 2 11 9 2 12 10 2 13 11 2 14 12 2 15 13 2 16 14 2 17 15 2 18 16 2 19 17 2 20 18 2 21 19 2 22 20 2 23 21 2 24 22 2 25 23 2 26 24 2 27 25 2 28 26 2 29 27 2 30 28 2 31 29 2 32 30 2 33 31 2 34 32 2 35 33 2 36 34 2 37 35 2 38 36 2 39 37 2 ...
output:
303559 446998 637944 31908 384943 596265 73359 189040 168637 29242 174729 27961 161703 530830 13512 14944 466594 33249 413001 436390 244264 295511 321664 414146 260352 123198 519093 198848 616773 18004 443531 427649 360779 173591 66173 29087 111810 119709 362949 379425 193505 357403 39553 482143 538...
result:
ok 800000 lines
Test #6:
score: 4
Accepted
time: 393ms
memory: 371840kb
input:
800000 800000 1 2 2 1 3 2 2 4 2 5 3 2 6 4 2 7 5 2 6 8 2 9 7 2 10 8 2 9 11 2 12 10 2 13 11 2 12 14 2 13 15 2 16 14 2 15 17 2 16 18 2 19 17 2 18 20 2 19 21 2 22 20 2 23 21 2 22 24 2 25 23 2 26 24 2 27 25 2 28 26 2 27 29 2 30 28 2 31 29 2 32 30 2 31 33 2 34 32 2 33 35 2 34 36 2 35 37 2 38 36 2 37 39 2 ...
output:
428390 492719 69111 437249 344847 253807 394011 630742 271977 130831 329038 120318 640616 140912 71741 362642 195190 352386 94598 29129 113310 192292 307026 537803 367745 503197 728984 117973 300802 157339 197354 3502 119855 178168 500706 23225 784043 338723 128301 403719 271353 172133 139809 601917...
result:
ok 800000 lines
Test #7:
score: 4
Accepted
time: 177ms
memory: 218500kb
input:
100000 800000 1 2 2 1 3 2 2 4 2 5 3 2 6 4 2 5 7 2 6 8 2 7 9 2 8 10 2 9 11 2 12 10 2 11 13 2 12 14 2 15 13 2 14 16 2 15 17 2 18 16 2 19 17 2 20 18 2 19 21 2 22 20 2 21 23 2 22 24 2 25 23 2 26 24 2 27 25 2 28 26 2 27 29 2 30 28 2 29 31 2 32 30 2 31 33 2 34 32 2 33 35 2 36 34 2 37 35 2 36 38 2 37 39 2 ...
output:
1221 40 215 52 121 493 278 1289 402 358 484 310 777 186 459 239 477 718 340 216 105 1010 176 185 440 119 340 87 274 478 765 775 332 1131 297 125 32 419 217 37 686 89 183 129 892 705 119 73 372 610 8 912 400 626 117 641 58 568 620 564 661 689 28 273 815 245 646 804 364 573 365 106 135 220 214 254 75 ...
result:
ok 800000 lines
Subtask #2:
score: 4
Accepted
Test #8:
score: 4
Accepted
time: 22ms
memory: 184776kb
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: 25ms
memory: 186336kb
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: 16ms
memory: 185116kb
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: 31ms
memory: 184680kb
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: 34ms
memory: 184776kb
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: 22ms
memory: 186516kb
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: 4
Accepted
time: 28ms
memory: 186448kb
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 1369 2 1176 795 1643 501 834 1543 578 301 1385 1138 952 43 534 1003 176 193 553 1091 1239 569 1203 1555 1845 643 1254 594 1051 1265 754 1607 1727 1893 6 ...
result:
ok 2000 lines
Test #15:
score: 4
Accepted
time: 24ms
memory: 184700kb
input:
2000 1999 1 1798 1 1256 2 1171 1403 3 809 1162 1291 1 187 2 762 1853 2 1979 1934 2 120 897 2 83 1488 1 812 1 1548 3 1839 1752 637 2 186 1514 2 995 1848 3 1661 1952 1339 2 1264 1427 1 319 4 1622 1848 1655 145 2 784 1246 1 33 3 1690 778 66 3 837 1450 206 2 954 270 2 421 1163 3 638 734 170 2 570 1161 3...
output:
1124 1448 1504 181 1898 1645 1665 152 1706 1443 1121 759 694 1313 142 1386 748 1831 588 1496 1557 729 1424 1165 185 244 1652 307 1629 907 469 1075 1260 1934 1431 245 898 1768 599 1060 544 1191 159 1003 1882 637 330 110 1543 794 40 1457 450 1923 1607 209 1673 593 1587 637 348 952 1256 973 233 198 726...
result:
ok 1999 lines
Test #16:
score: 4
Accepted
time: 27ms
memory: 184628kb
input:
1999 2000 1 399 3 922 1215 1527 1 1286 2 720 1288 1 385 3 680 926 1477 4 1895 1793 1900 959 2 1124 646 1 1440 2 1433 175 2 1078 1643 2 1689 1286 3 1006 1556 502 3 1343 1385 176 3 1295 316 1444 1 1725 4 394 452 761 1093 4 1022 1954 90 611 4 1656 1183 406 1359 2 593 1915 1 1776 2 853 365 1 1687 2 1693...
output:
913 1506 721 94 375 1068 544 1214 1883 443 251 390 172 78 352 108 675 730 1739 1996 1847 1471 456 960 469 1060 664 1064 1695 571 819 1890 1151 1584 514 1381 1743 1097 275 41 450 1303 711 626 212 726 1330 863 219 79 1302 280 1090 962 691 1266 1041 1470 1400 1330 1804 1100 336 691 736 28 1954 1148 438...
result:
ok 2000 lines
Test #17:
score: 4
Accepted
time: 27ms
memory: 185612kb
input:
2000 1999 2 437 1126 1 820 1 1967 2 1986 599 2 924 1111 2 700 1325 2 537 999 2 1550 192 2 988 1682 3 1063 260 444 1 1808 2 1223 658 2 58 519 3 1633 1279 1866 3 404 887 1009 1 579 3 684 1740 304 2 1660 1843 2 1340 990 1 1564 1 1093 2 1766 38 2 1610 1495 2 1830 1396 3 1807 1935 241 3 964 458 735 3 153...
output:
852 1459 819 989 1358 1553 278 371 1528 1762 1786 892 1428 1880 754 1595 1592 330 1909 1499 1661 1143 1527 1780 452 74 1169 335 920 1219 64 1366 1901 11 1616 663 298 1572 1854 1366 81 1771 1530 1989 782 751 291 315 1662 604 1797 554 766 1440 1087 46 589 1019 1003 497 89 1875 177 1998 751 1456 1619 3...
result:
ok 1999 lines
Test #18:
score: 4
Accepted
time: 30ms
memory: 184544kb
input:
1999 2000 2 1788 834 2 340 1244 2 583 93 2 1773 1413 2 100 1416 2 866 1920 2 620 1996 2 1638 1131 2 527 1150 2 1534 666 2 1890 441 2 1194 1782 2 186 791 2 1072 257 2 904 1138 2 310 1581 2 1909 577 2 1859 1607 2 1229 1492 2 1255 300 2 1320 1159 2 1140 1265 2 1531 298 2 328 918 2 1611 126 2 908 1125 2...
output:
10 1542 1835 351 783 244 1542 1287 860 212 1726 544 1263 1761 156 739 1753 299 1534 692 1253 1298 1537 235 549 1875 1908 1984 1153 225 546 1386 862 1362 58 1205 1113 1301 357 593 1202 1454 1355 1947 1575 446 529 428 1189 148 1833 245 487 1991 240 276 500 1580 707 266 687 1902 9 1642 1903 1502 502 52...
result:
ok 2000 lines
Test #19:
score: 4
Accepted
time: 29ms
memory: 183812kb
input:
1999 2000 1 2 2 3 1 2 4 2 2 5 3 2 6 4 2 7 5 2 8 6 2 9 7 2 10 8 2 11 9 2 12 10 2 13 11 2 14 12 2 15 13 2 16 14 2 17 15 2 18 16 2 19 17 2 20 18 2 21 19 2 22 20 2 23 21 2 24 22 2 25 23 2 26 24 2 27 25 2 28 26 2 29 27 2 30 28 2 31 29 2 32 30 2 33 31 2 34 32 2 35 33 2 36 34 2 37 35 2 38 36 2 39 37 2 40 3...
output:
15 306 506 19 345 397 123 53 166 423 93 166 277 9 30 11 589 18 352 348 313 6 454 120 123 202 52 2 218 73 178 122 141 211 44 472 99 94 50 373 77 253 63 106 1218 212 500 172 175 5 448 262 198 141 227 42 228 98 101 247 450 30 369 135 405 163 324 22 520 20 172 348 298 176 104 38 187 58 174 32 128 375 33...
result:
ok 2000 lines
Test #20:
score: 4
Accepted
time: 26ms
memory: 185360kb
input:
1999 2000 1 2 2 3 1 2 4 2 2 3 5 2 6 4 2 5 7 2 6 8 2 9 7 2 8 10 2 11 9 2 12 10 2 11 13 2 12 14 2 15 13 2 16 14 2 15 17 2 16 18 2 19 17 2 18 20 2 21 19 2 20 22 2 21 23 2 24 22 2 25 23 2 26 24 2 25 27 2 28 26 2 29 27 2 28 30 2 31 29 2 30 32 2 31 33 2 32 34 2 35 33 2 34 36 2 35 37 2 38 36 2 37 39 2 38 4...
output:
257 104 199 199 1 429 224 266 26 1498 284 74 6 200 16 6 421 426 97 177 18 481 92 23 45 318 171 249 187 216 162 4 366 190 220 287 22 209 14 173 2 364 164 344 152 131 136 7 153 97 49 277 427 102 454 172 57 110 112 299 141 230 451 140 383 483 210 111 92 52 256 114 488 68 26 655 334 253 75 42 6 265 237 ...
result:
ok 2000 lines
Test #21:
score: 4
Accepted
time: 28ms
memory: 185196kb
input:
1999 2000 2 1944 524 2 371 1993 2 1399 1469 2 1184 953 2 1973 791 2 1016 133 2 905 1395 2 607 1304 2 1792 635 2 1150 835 2 1159 1952 2 993 120 2 508 701 2 1635 1312 2 1113 903 2 378 246 2 1413 430 2 324 328 2 1649 1970 2 1366 1458 2 1428 1284 2 1447 216 2 598 707 2 519 946 2 915 1770 2 488 169 2 746...
output:
544 969 691 1385 1712 655 467 1666 1599 592 187 1982 930 1728 651 1728 507 660 266 1664 1360 887 797 1360 1 1274 482 76 464 691 123 660 646 891 1504 90 398 1190 1410 320 761 1204 1758 1301 899 1181 121 1469 786 1734 260 228 544 1504 1840 509 661 467 1385 74 985 1776 321 1218 592 661 1532 1241 114 53...
result:
ok 2000 lines
Subtask #3:
score: 12
Accepted
Test #22:
score: 12
Accepted
time: 34ms
memory: 185620kb
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: 12
Accepted
time: 46ms
memory: 194992kb
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:
34951
result:
ok single line: '34951'
Test #24:
score: 12
Accepted
time: 101ms
memory: 205496kb
input:
100000 1 2 27134 41126 3 40041 15370 16427 2 37589 31514 3 15114 95794 47171 1 5156 3 41845 96235 50799 3 17792 67060 57776 1 15670 2 79238 20844 2 93180 95396 3 60528 97759 61907 2 65459 24434 1 39266 2 67947 98363 1 52481 2 1485 11699 2 16000 75047 2 9541 30450 1 95566 2 48358 36805 2 36908 42249 ...
output:
59683
result:
ok single line: '59683'
Test #25:
score: 12
Accepted
time: 78ms
memory: 202516kb
input:
100000 1 3 12848 89841 83960 2 85048 42918 3 6437 55031 86261 2 38792 33493 2 94239 26148 1 147 3 38208 73193 6613 2 44185 65773 2 55474 92484 2 59210 21501 2 38502 27204 4 4846 60417 75871 99303 2 27138 59645 1 77914 1 11739 2 28495 7056 3 43220 77471 22841 4 98455 83304 82997 56084 1 85877 1 30298...
output:
45133
result:
ok single line: '45133'
Test #26:
score: 12
Accepted
time: 690ms
memory: 312120kb
input:
800000 1 1 468214 3 170834 405662 780050 1 405996 1 530574 2 219438 335094 1 559532 1 305995 2 697599 676682 2 759587 461333 2 447996 430434 1 272291 2 588063 79339 1 252249 3 74445 665000 643949 6 596108 430841 718006 44435 646836 722797 1 417371 3 237265 12905 707490 1 508178 3 625856 797492 43186...
output:
346113
result:
ok single line: '346113'
Test #27:
score: 12
Accepted
time: 738ms
memory: 307924kb
input:
800000 1 3 34953 549036 64946 1 242439 1 545119 1 294726 1 448131 1 214009 1 745703 2 549597 157197 2 451265 470102 1 132662 3 438870 377747 294508 1 16621 1 606182 2 382204 350084 1 144919 2 610539 633262 1 729929 1 610363 2 64654 130074 2 195411 184073 3 616565 95430 689058 2 563703 308368 3 38486...
output:
598891
result:
ok single line: '598891'
Test #28:
score: 12
Accepted
time: 706ms
memory: 308380kb
input:
800000 1 1 369668 1 723745 2 108568 683565 1 543202 4 416112 734831 393479 751358 2 420035 627057 2 268296 779872 1 170684 3 329230 458624 741070 1 110597 3 36704 417827 16656 1 655278 3 469579 679196 51885 4 660372 379932 279781 269658 2 225837 723611 1 88210 1 420720 2 312898 194565 1 606668 2 443...
output:
535203
result:
ok single line: '535203'
Test #29:
score: 12
Accepted
time: 698ms
memory: 315432kb
input:
800000 1 2 771711 524796 1 609600 4 687168 576958 254247 646637 1 190754 2 592765 763470 3 737967 37497 26269 3 379412 21551 573424 3 690100 318437 740538 3 82004 266266 103965 3 313511 425572 651154 2 363236 386203 3 515468 457467 138806 5 147020 420610 431472 666192 302733 2 466941 666723 3 211523...
output:
786894
result:
ok single line: '786894'
Test #30:
score: 12
Accepted
time: 812ms
memory: 333064kb
input:
800000 1 2 94008 666236 2 253254 603703 2 361984 111051 1 24501 2 306038 555203 2 368434 110819 1 517209 1 247427 2 286963 253357 1 511574 1 355646 2 764388 315441 1 461640 2 20888 418358 1 633372 2 81184 266550 1 127384 2 242998 565901 2 626582 374578 1 116783 2 583218 140283 2 739512 740779 2 3123...
output:
470819
result:
ok single line: '470819'
Test #31:
score: 12
Accepted
time: 804ms
memory: 339840kb
input:
799999 1 2 535253 525255 2 694109 359059 2 55700 126442 2 156417 64974 2 682396 83228 2 96315 301091 2 548173 766457 2 701233 662198 2 301605 748263 2 159332 676820 2 644980 699416 2 488035 69956 2 499310 135154 2 442121 118714 2 617945 383688 2 480227 320145 2 548028 121909 2 429391 176732 2 616502...
output:
704279
result:
ok single line: '704279'
Test #32:
score: 12
Accepted
time: 242ms
memory: 358940kb
input:
799999 1 1 2 2 3 1 2 4 2 2 5 3 2 6 4 2 7 5 2 8 6 2 9 7 2 10 8 2 11 9 2 12 10 2 13 11 2 14 12 2 15 13 2 16 14 2 17 15 2 18 16 2 19 17 2 20 18 2 21 19 2 22 20 2 23 21 2 24 22 2 25 23 2 26 24 2 27 25 2 28 26 2 29 27 2 30 28 2 31 29 2 32 30 2 33 31 2 34 32 2 35 33 2 36 34 2 37 35 2 38 36 2 39 37 2 40 38...
output:
84911
result:
ok single line: '84911'
Test #33:
score: 12
Accepted
time: 260ms
memory: 361436kb
input:
799999 1 1 2 2 1 3 2 2 4 2 3 5 2 6 4 2 7 5 2 8 6 2 9 7 2 10 8 2 9 11 2 10 12 2 13 11 2 14 12 2 13 15 2 14 16 2 17 15 2 18 16 2 19 17 2 18 20 2 19 21 2 22 20 2 23 21 2 24 22 2 25 23 2 26 24 2 25 27 2 28 26 2 29 27 2 30 28 2 31 29 2 30 32 2 33 31 2 34 32 2 35 33 2 36 34 2 37 35 2 38 36 2 39 37 2 40 38...
output:
180883
result:
ok single line: '180883'
Subtask #4:
score: 5
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #34:
score: 5
Accepted
time: 150ms
memory: 197344kb
input:
10000 799999 1 1273 1 7673 2 1995 4263 3 3539 592 5940 2 4730 2103 4 6159 9303 6045 9518 2 5288 6114 2 2046 8975 2 2153 3985 1 2318 2 6559 7802 2 8283 847 2 1468 3166 2 1343 422 2 2462 1294 3 1711 4799 8994 2 3016 2787 2 5671 7486 3 4125 9372 9907 2 4286 2396 2 5450 7542 3 8401 3558 993 2 4478 2591 ...
output:
9183 5918 6094 8319 2247 5347 1511 8195 3029 9724 1513 932 6867 6104 5987 3527 2922 91 9232 41 748 740 141 1663 9254 6504 9807 9602 4571 397 378 6159 3800 4917 8717 5987 4642 6798 675 4319 5809 7108 7570 2099 7525 5972 818 7510 8142 8062 430 4271 3257 5519 1797 9316 4326 8814 9514 5089 6452 9242 293...
result:
ok 799999 lines
Test #35:
score: 5
Accepted
time: 187ms
memory: 207528kb
input:
50000 800000 2 1257 23580 2 177 8808 3 12568 31336 12261 2 2419 42992 2 23177 7123 3 30458 8672 17609 3 49859 49966 13486 1 46426 2 10913 1202 2 49342 10954 3 22254 40988 25436 1 3522 1 49284 1 18468 2 21371 11949 2 44886 4984 3 43256 617 8162 1 44130 2 39472 49895 3 32664 41488 48635 2 10905 12549 ...
output:
5248 44743 11907 45052 23635 48111 39387 44978 1226 18897 35779 8599 47436 25375 41321 12315 10938 46573 8700 19370 39700 2877 4113 44443 2209 30519 5042 38875 7780 43181 6031 594 1691 49951 48108 47227 13020 46398 17264 17036 25195 25803 17940 27981 45005 30833 32755 19540 30746 19565 33865 983 224...
result:
ok 800000 lines
Test #36:
score: 5
Accepted
time: 231ms
memory: 217648kb
input:
100000 799999 3 82921 99798 21853 1 83281 2 88724 33418 1 37501 2 78841 52982 1 99275 3 22189 85054 17304 1 37498 2 14978 9017 2 26582 18132 2 53331 90481 3 76544 54354 44563 3 17461 21924 68183 3 85369 82117 14615 3 93825 69110 2544 2 81479 63550 1 49042 1 96878 1 78369 3 84929 41596 89066 3 44501 ...
output:
7130 35636 64109 39386 64064 79474 49845 46450 34613 57376 61536 35337 69118 27137 30839 90018 18162 69778 68260 24092 68000 72399 4474 27935 90880 49713 415 80859 7070 16398 94794 5072 55016 70417 17079 50203 82334 45965 60085 23817 8152 65808 56012 29831 89348 30648 28711 67983 47176 36596 16025 1...
result:
ok 799999 lines
Test #37:
score: 5
Accepted
time: 815ms
memory: 321596kb
input:
800000 800000 1 662610 2 757335 638362 2 404018 316466 3 174047 22333 748861 4 584355 154715 736946 493248 1 32404 1 516411 1 703883 1 181126 1 725520 1 92627 1 680162 2 374914 470264 1 474846 3 642761 520805 250653 5 311825 150959 355389 502743 341217 2 78911 761209 4 183607 57865 385689 663487 1 3...
output:
133652 755206 178765 396215 20842 38634 181826 506628 153702 238991 778573 43982 442796 699359 667525 428889 606358 664307 86147 96368 365122 658302 627999 601456 649317 770400 524324 339652 622291 595563 534346 412462 409345 86583 64711 201439 755120 657751 356991 539627 609370 323283 60583 196267 ...
result:
ok 800000 lines
Test #38:
score: 5
Accepted
time: 852ms
memory: 322388kb
input:
800000 800000 1 402249 4 340224 9271 76722 528017 1 180416 2 347348 56892 3 370895 384246 395636 3 245757 650963 695984 1 91517 1 350475 1 407615 2 749524 757377 2 439401 239403 3 394680 328191 205805 2 760104 250623 2 574142 459912 2 152210 602857 3 217831 395955 701751 3 672435 98933 596218 1 3037...
output:
570727 574257 698161 3327 771690 112144 699312 275828 730175 591018 75114 394577 294391 567547 665911 671390 58333 416993 314466 756706 284834 441870 711168 782885 792149 178491 748769 685187 544372 179908 399752 433329 631641 798433 311688 644513 60841 379235 465813 122625 113187 473299 694248 3381...
result:
ok 800000 lines
Test #39:
score: 5
Accepted
time: 835ms
memory: 322108kb
input:
800000 800000 4 551267 28519 635681 689822 2 640912 312031 3 476926 67035 494826 2 617294 338196 3 438271 167991 551208 2 301231 619141 1 355520 2 527644 364103 1 658593 1 347499 2 327349 795743 2 171238 774956 1 153845 3 351987 589784 653472 2 298258 71747 3 390396 177220 775 5 196482 469022 61228 ...
output:
289377 209901 796921 616533 388567 669359 182184 73213 509112 323333 62191 154974 594622 428073 163579 208940 770798 490619 745931 475361 535112 432564 320419 430493 204627 220540 520679 133298 612106 582030 613676 566520 7926 122259 139180 695067 314959 236247 115458 729945 392231 464611 264832 407...
result:
ok 800000 lines
Test #40:
score: 5
Accepted
time: 865ms
memory: 324612kb
input:
800000 799999 2 335518 767380 4 632720 273919 187272 625345 3 594558 358995 74540 4 327414 68257 787144 768214 1 399376 2 209128 591181 2 69505 112336 4 328748 378262 239397 319931 4 468954 527723 559750 351367 2 142244 522152 2 562504 28128 2 714375 729779 2 545345 351825 5 798080 24487 731737 2442...
output:
186341 615384 527067 182763 54686 125589 128591 780969 521518 374558 367274 396531 318036 641404 560805 295665 744557 656417 682049 27828 272856 266490 766117 310529 591871 554150 342537 580931 397116 317771 644071 645517 56400 211967 61744 82819 44963 581895 696360 112621 755295 643533 66788 275945...
result:
ok 799999 lines
Test #41:
score: 5
Accepted
time: 938ms
memory: 348372kb
input:
800000 799999 1 92588 3 522252 681513 753681 1 692076 1 438349 3 640099 203608 426234 2 215507 472772 1 741591 3 412649 31930 282957 2 491602 764189 2 645459 675197 1 145655 2 383144 668227 2 286705 704169 2 546489 473381 3 29254 57197 226123 2 154508 18191 3 283350 190834 191187 2 312893 529016 2 3...
output:
391810 453015 649805 380870 727952 118806 210501 114464 217120 712814 654074 324975 651436 700107 464951 114942 131934 317553 306784 71704 590018 35521 15658 780356 69330 741084 245298 655355 560876 695064 246247 724405 435331 249952 782489 439170 59245 645054 581239 120670 607482 557361 78121 40891...
result:
ok 799999 lines
Test #42:
score: 5
Accepted
time: 937ms
memory: 371940kb
input:
799999 800000 2 698204 370526 2 189362 616426 2 116748 540116 2 372846 360014 2 263981 483590 2 472923 640114 2 126739 483885 2 692431 294891 2 45858 798561 2 665774 434197 2 719934 606185 2 14658 140656 2 661453 226870 2 261530 425092 2 589417 578780 2 791602 414246 2 708893 521883 2 93406 249628 2...
output:
378120 302071 771377 604333 138620 70471 627199 563785 276855 434640 62508 413695 157878 39841 774586 766868 678581 722589 607575 3159 286172 687464 656885 683010 9188 26664 313395 190588 60064 561737 650753 187520 444519 684195 274279 54630 725543 552968 564225 120630 378814 587933 791037 197954 29...
result:
ok 800000 lines
Test #43:
score: 5
Accepted
time: 380ms
memory: 375376kb
input:
799999 800000 1 2 2 3 1 2 4 2 2 5 3 2 6 4 2 7 5 2 8 6 2 9 7 2 10 8 2 11 9 2 12 10 2 13 11 2 14 12 2 15 13 2 16 14 2 17 15 2 18 16 2 19 17 2 20 18 2 21 19 2 22 20 2 23 21 2 24 22 2 25 23 2 26 24 2 27 25 2 28 26 2 29 27 2 30 28 2 31 29 2 32 30 2 33 31 2 34 32 2 35 33 2 36 34 2 37 35 2 38 36 2 39 37 2 ...
output:
148972 102779 26193 77277 8202 62931 160530 68166 51066 57278 8616 47266 39007 650 227985 76186 66535 50561 95103 228366 83238 64175 111010 113477 82125 29457 3420 71266 101615 201956 5637 113169 55485 183482 27801 126686 196012 28241 137159 96496 11915 187006 16662 68326 82031 159132 62114 105500 7...
result:
ok 800000 lines
Test #44:
score: 5
Accepted
time: 413ms
memory: 371468kb
input:
799999 800000 1 2 2 3 1 2 2 4 2 3 5 2 6 4 2 7 5 2 8 6 2 9 7 2 10 8 2 9 11 2 10 12 2 13 11 2 12 14 2 13 15 2 16 14 2 15 17 2 18 16 2 19 17 2 20 18 2 19 21 2 20 22 2 21 23 2 22 24 2 25 23 2 24 26 2 25 27 2 28 26 2 27 29 2 30 28 2 31 29 2 30 32 2 31 33 2 34 32 2 35 33 2 34 36 2 37 35 2 36 38 2 39 37 2 ...
output:
173601 62921 97466 331812 16869 148839 107245 162747 15155 32 11684 102474 93754 9597 134610 152121 68032 71615 161918 26714 44202 101406 19205 51399 101352 28188 40163 52916 81420 103954 39012 174579 108229 20128 104346 5810 14073 205695 47042 30486 21868 21448 19660 65953 272937 244854 62083 20502...
result:
ok 800000 lines
Test #45:
score: 5
Accepted
time: 928ms
memory: 349780kb
input:
799999 800000 2 102564 653962 2 220822 7079 2 415047 372125 2 218899 120150 2 689915 781637 2 282215 310982 2 666595 349303 2 645756 542338 2 763228 687327 2 43064 359053 2 116545 635285 2 589317 234128 2 693709 531018 2 487287 733319 2 214496 518842 2 234534 519786 2 20803 145039 2 708198 582412 2 ...
output:
321963 225918 636466 23197 297457 249497 746967 191197 685621 670163 651010 720999 656570 9570 228508 552976 512386 368494 353629 138578 106005 119926 448360 768083 349661 529620 486716 221034 463733 504160 134112 140774 131721 283552 43726 229025 278119 435455 608478 630800 363278 794807 786003 882...
result:
ok 800000 lines
Extra Test:
score: 0
Extra Test Passed