QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#880808#2708. Through Another Maze Darklyhhoppitree0 1637ms13844kbC++202.0kb2025-02-03 20:53:362025-02-03 20:53:37

Judging History

This is the latest submission verdict.

  • [2025-02-03 20:53:37]
  • Judged
  • Verdict: 0
  • Time: 1637ms
  • Memory: 13844kb
  • [2025-02-03 20:53:36]
  • Submitted

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%