QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#880899	#2708. Through Another Maze Darkly	hhoppitree	4	2107ms	298768kb	C++20	1.9kb	2025-02-03 23:08:13	2025-02-03 23:08:14

Judging History

This is the latest submission verdict.

[2025-02-03 23:08:14]
Judged

Verdict: 4
Time: 2107ms
Memory: 298768kb

Show

[2025-02-03 23:08:13]
Submitted

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

const int N = 8e5 + 5;

vector<int> G[N];
int cur[N], ord[N << 1], ord_c, f[N << 1];
vector< pair<long long, int> > qry;
int res[N];

void dfs(int x, int fa = 0, int F = 0) {
    int ini = G[x][0];
    rotate(G[x].begin(), find(G[x].begin(), G[x].end(), (fa ? fa : G[x].back())), G[x].end());
    cur[x] = find(G[x].begin(), G[x].end(), ini) - G[x].begin();
    if (x != 1) ord[++ord_c] = x, f[ord_c] = F;
    for (int i = 0; i < (int)G[x].size(); ++i) {
        int v = G[x][i];
        if (v == fa) continue;
        dfs(v, x, F + (i <= cur[x])), ord[++ord_c] = x;
        f[ord_c] = F + (i <= cur[x]);
    }
}

vector<int> apd[N];

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);
    }
    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);
    int k = *max_element(f + 1, f + ord_c + 1), nw = 0;
    for (int i = 1; i <= ord_c; ++i) apd[f[i]].push_back(i);
    tree< pair<int, int>, null_type, less< pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> T;
    long long dlt = 0;
    while (!qry.empty()) {
        auto [x, id] = qry.back();
        x -= dlt;
        if (nw == k) x = (x - 1) % T.size() + 1;
        if (x <= (int)T.size()) {
            res[id] = T.find_by_order(x - 1) -> second;
            qry.pop_back();
            continue;
        }
        dlt += T.size();
        ++nw;
        for (auto p : apd[nw]) T.insert({p, ord[p]});
    }
    for (int i = 1; i <= q; ++i) printf("%d\n", res[i]);
    return 0;
}

源文件, 语言: C++20

詳細信息

Subtask #1:

score: 4

Accepted

Test #1:

score: 4

Accepted

time: 1ms

memory: 8028kb

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:

result:

ok 50 lines

Test #2:

score: 4

Accepted

time: 12ms

memory: 11320kb

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:

result:

ok 10000 lines

Test #3:

score: 4

Accepted

time: 140ms

memory: 47444kb

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:

ok 100000 lines

Test #4:

score: 4

Accepted

time: 2092ms

memory: 265020kb

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:

result:

ok 800000 lines

Test #5:

score: 4

Accepted

time: 2107ms

memory: 298768kb

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:

result:

ok 800000 lines

Test #6:

score: 4

Accepted

time: 1624ms

memory: 283200kb

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:

result:

ok 800000 lines

Test #7:

score: 4

Accepted

time: 204ms

memory: 44604kb

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:

result:

ok 800000 lines

Subtask #2:

score: 0

Wrong Answer

Test #8:

score: 4

Accepted

time: 0ms

memory: 8020kb

input:

output:

result:

ok 1999 lines

Test #9:

score: 4

Accepted

time: 2ms

memory: 8112kb

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:

result:

ok 2000 lines

Test #10:

score: 4

Accepted

time: 3ms

memory: 8200kb

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:

result:

ok 1999 lines

Test #11:

score: 4

Accepted

time: 2ms

memory: 8228kb

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:

result:

ok 2000 lines

Test #12:

score: 4

Accepted

time: 2ms

memory: 8304kb

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:

result:

ok 2000 lines

Test #13:

score: 4

Accepted

time: 3ms

memory: 8364kb

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:

result:

ok 2000 lines

Test #14:

score: 0

Wrong Answer

time: 4ms

memory: 8356kb

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:

result:

wrong answer 1st lines differ - expected: '1366', found: '1737'

Subtask #3:

score: 0

Wrong Answer

Test #22:

score: 12

Accepted

time: 3ms

memory: 9340kb

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:

result:

ok single line: '4514'

Test #23:

score: 12

Accepted

time: 17ms

memory: 14624kb

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:

ok single line: '34951'

Test #24:

score: 12

Accepted

time: 66ms

memory: 30004kb

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:

result:

ok single line: '59683'

Test #25:

score: 0

Wrong Answer

time: 81ms

memory: 34744kb

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:

result:

wrong answer 1st lines differ - expected: '45133', found: '24184'

Subtask #4:

score: 0

Skipped

Dependency #1:

100%

Accepted