QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#930684#31. Railwaynhuang685#36 38ms21260kbC++233.5kb2025-03-10 05:10:512025-03-10 05:10:53

Judging History

This is the latest submission verdict.

  • [2025-03-10 05:10:53]
  • Judged
  • Verdict: 36
  • Time: 38ms
  • Memory: 21260kb
  • [2025-03-10 05:10:51]
  • Submitted

answer

#include <bits/stdc++.h>

struct HLD {
  const std::vector<std::vector<std::pair<int, int>>>& adj;
  std::vector<int> dep, tl, tr, par, pid, sub;
  std::vector<int> root, cha, ind;
  std::vector<std::vector<int>> diff;
  void dfs(int node, int& cnt, std::vector<int>& hc) {
    tl[node] = cnt++;
    for (auto [id, i] : adj[node]) {
      if (i == par[node]) {
        continue;
      }
      dep[i] = dep[node] + 1;
      par[i] = node;
      pid[i] = id;
      dfs(i, cnt, hc);
      sub[node] += sub[i];
    }
    tr[node] = cnt - 1;
    for (auto [id, i] : adj[node]) {
      if (i == par[node]) {
        continue;
      }
      if (hc[node] == -1 || sub[hc[node]] < sub[i]) {
        hc[node] = i;
      }
    }
  }
  explicit HLD(const std::vector<std::vector<std::pair<int, int>>>& adj_)
    : adj(adj_), dep(adj.size()), tl(adj.size()), tr(adj.size()),
    par(adj.size(), -1), pid(adj.size(), -1),
    sub(adj.size(), 1), root(adj.size()), cha(adj.size()), ind(adj.size())
  {
    std::vector<int> hc(adj.size(), -1);
    int cnt = 0;
    dfs(0, cnt, hc);
    cnt = 0;
    for (int i = 0; i < (int)adj.size(); ++i) {
      if (par[i] == -1 || hc[par[i]] != i) {
        cha[i] = cnt++;
        int node = i;
        int cnt2 = 0;
        while (node != -1) {
          root[node] = i;
          cha[node] = cha[i];
          ind[node] = cnt2++;
          node = hc[node];
        }
        diff.push_back(std::vector<int>(cnt2 + 1));
      }
    }
  }
  int lca(int a, int b) {
    for (; root[a] != root[b]; b = par[root[b]]) {
      if (dep[root[a]] > dep[root[b]]) {
        std::swap(a, b);
      }
    }
    if (dep[a] > dep[b]) {
      std::swap(a, b);
    }
    return a;
  }
  void add(int a, int b) {
    for (; root[a] != root[b]; b = par[root[b]]) {
      ++diff[cha[root[b]]][ind[root[b]]];
      --diff[cha[b]][ind[b] + 1];
    }
    ++diff[cha[a]][ind[a] + 1];
    --diff[cha[b]][ind[b] + 1];
  }
  int get(int node) {
    return diff[cha[node]][ind[node]];
  }
};

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, m, k;
  std::cin >> n >> m >> k;

  std::vector<std::vector<std::pair<int, int>>> adj(n);
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    std::cin >> a >> b;
    --a;
    --b;
    adj[a].emplace_back(i, b);
    adj[b].emplace_back(i, a);
  }

  HLD hld(adj);
  for (int t = 0; t < m; ++t) {
    int s;
    std::cin >> s;
    std::vector<int> a(s);
    for (int& v : a) {
      std::cin >> v;
      --v;
    }
    std::sort(a.begin(), a.end(), [&](int u, int v) {
      return hld.tl[u] < hld.tl[v];
    });
    int sz = (int)a.size();
    a.push_back(hld.lca(a[0], a.back()));
    for (int i = 0; i < sz - 1; ++i) {
      a.push_back(hld.lca(a[i], a[i + 1]));
    }
    std::sort(a.begin(), a.end(), [&](int u, int v) {
      return hld.tl[u] < hld.tl[v];
    });
    a.erase(std::unique(a.begin(), a.end()), a.end());
    std::stack<int> st;
    for (int i : a) {
      while (!st.empty() && hld.tr[st.top()] < hld.tl[i]) {
        st.pop();
      }
      if (!st.empty()) {
        hld.add(st.top(), i);
      }
      st.push(i);
    }
  }
  for (std::vector<int>& arr : hld.diff) {
    std::partial_sum(arr.begin(), arr.end(), arr.begin());
  }

  std::vector<int> ans;
  for (int i = 1; i < n; ++i) {
    if (hld.get(i) >= k) {
      ans.push_back(hld.pid[i]);
    }
  }

  std::cout << ans.size() << '\n';
  for (int id : ans) {
    std::cout << id + 1 << ' ';
  }
  std::cout << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3712kb

input:

10 10 3
1 2
1 5
1 8
2 3
2 4
2 6
3 9
6 7
6 10
2 4 9
2 2 10
2 8 10
2 2 8
2 7 9
2 6 10
2 7 9
2 6 7
2 5 10
2 1 7

output:

6
1 4 6 8 7 9 

result:

wrong answer 2nd lines differ - expected: '1 4 6 7 8 9', found: '1 4 6 8 7 9 '

Subtask #2:

score: 0
Wrong Answer

Test #15:

score: 0
Wrong Answer
time: 13ms
memory: 4808kb

input:

10000 1500 25
1 2
1 5
1 10
1 14
1 76
1 1625
1 1969
1 2025
2 3
2 34
2 320
2 519
2 577
2 2340
2 3157
2 7075
2 8630
3 4
3 38
3 215
3 248
3 272
3 1597
3 1752
3 1853
3 2104
3 5171
3 8467
4 7
4 9
4 12
4 30
4 436
4 1404
4 3559
5 6
5 8
5 60
5 74
5 79
5 281
5 627
5 770
5 848
5 2371
5 6713
5 9756
6 13
6 73
6 ...

output:

1430
1 9 18 2 36 29 37 30 3 65 31 48 4 97 102 105 66 72 73 106 91 67 80 92 93 68 94 107 32 85 122 109 10 131 137 187 19 183 216 159 165 169 171 150 161 249 160 218 56 244 195 280 151 138 196 209 310 123 38 201 179 110 340 281 259 271 81 351 342 397 49 39 333 5 103 180 40 132 152 166 272 412 423 145 ...

result:

wrong answer 2nd lines differ - expected: '1 2 3 4 5 9 10 12 13 18 19 20 ...4 9525 9550 9751 9823 9852 9902', found: '1 9 18 2 36 29 37 30 3 65 31 4... 6871 4973 8501 5655 9902 9823 '

Subtask #3:

score: 7
Accepted

Test #36:

score: 7
Accepted
time: 24ms
memory: 20888kb

input:

100000 50000 10000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 5...

output:

77461
11290 11291 11292 11293 11294 11295 11296 11297 11298 11299 11300 11301 11302 11303 11304 11305 11306 11307 11308 11309 11310 11311 11312 11313 11314 11315 11316 11317 11318 11319 11320 11321 11322 11323 11324 11325 11326 11327 11328 11329 11330 11331 11332 11333 11334 11335 11336 11337 11338 ...

result:

ok 2 lines

Test #37:

score: 7
Accepted
time: 1ms
memory: 3712kb

input:

20 25 12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
3 5 6 8
3 11 15 16
3 6 7 16
3 3 10 17
3 12 13 14
4 2 5 19 20
4 5 6 18 19
4 4 5 18 19
4 2 6 18 19
4 4 7 18 19
4 5 6 18 20
4 5 6 17 18
4 5 7 19 20
4 5 8 18 20
4 3 4 17 18
4 4 5 6 7
4 4 5 6 7
4 2 3...

output:

12
4 5 6 7 8 9 10 11 12 13 14 15 

result:

ok 2 lines

Test #38:

score: 7
Accepted
time: 28ms
memory: 20496kb

input:

100000 50000 20000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 5...

output:

44891
27596 27597 27598 27599 27600 27601 27602 27603 27604 27605 27606 27607 27608 27609 27610 27611 27612 27613 27614 27615 27616 27617 27618 27619 27620 27621 27622 27623 27624 27625 27626 27627 27628 27629 27630 27631 27632 27633 27634 27635 27636 27637 27638 27639 27640 27641 27642 27643 27644 ...

result:

ok 2 lines

Test #39:

score: 7
Accepted
time: 26ms
memory: 20452kb

input:

100000 50000 30000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 5...

output:

0


result:

ok single line: '0'

Test #40:

score: 7
Accepted
time: 23ms
memory: 21132kb

input:

100000 5000 4000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
...

output:

84308
7834 7835 7836 7837 7838 7839 7840 7841 7842 7843 7844 7845 7846 7847 7848 7849 7850 7851 7852 7853 7854 7855 7856 7857 7858 7859 7860 7861 7862 7863 7864 7865 7866 7867 7868 7869 7870 7871 7872 7873 7874 7875 7876 7877 7878 7879 7880 7881 7882 7883 7884 7885 7886 7887 7888 7889 7890 7891 7892...

result:

ok 2 lines

Test #41:

score: 7
Accepted
time: 28ms
memory: 21132kb

input:

100000 1500 450
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
5...

output:

95336
2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389...

result:

ok 2 lines

Subtask #4:

score: 29
Accepted

Test #42:

score: 29
Accepted
time: 28ms
memory: 19700kb

input:

100000 50000 50000
1 2
1 62279
2 3
2 65122
2 73814
2 79457
2 80525
3 4
3 84818
3 94649
4 5
4 97078
5 6
6 7
6 91079
7 8
7 86372
8 9
8 61967
9 10
10 11
11 12
11 73785
11 88130
12 13
12 53359
12 95417
13 14
13 99504
14 15
15 16
15 50946
15 51474
16 17
16 59256
16 72237
17 18
18 19
18 63271
19 20
20 21
...

output:

1358
39626 39628 39629 39631 39633 39635 39636 39637 39638 39640 39641 39642 39644 39645 39646 39648 39649 39652 39653 39654 39655 39657 39658 39659 39660 39661 39663 39665 39667 39668 39670 39671 39672 39673 39674 39675 39676 39677 39678 39681 39682 39684 39685 39687 39688 39689 39690 39692 39693 3...

result:

ok 2 lines

Test #43:

score: 29
Accepted
time: 33ms
memory: 16348kb

input:

100000 50000 50000
1 2
1 15517
2 3
3 4
3 5689
3 16979
3 23884
3 46692
4 5
4 40040
4 53822
4 84197
5 6
5 5730
5 6112
5 9968
5 30096
6 7
6 7773
6 22479
6 26336
6 54232
7 8
7 14903
7 23183
7 33836
8 9
8 6240
8 42540
9 10
9 6120
9 7314
9 9921
9 12838
9 34198
9 40794
10 11
10 8363
10 13153
11 12
11 5080
...

output:

812
7814 7819 7823 7831 7833 7836 7839 7842 7844 7850 7852 7856 7863 7866 7871 7876 7882 7888 7892 7899 7904 7907 7911 7913 7917 7922 7927 7934 7942 7945 7947 7952 7955 7960 7963 7965 7970 7974 7978 7982 7986 7993 7996 8000 8005 8007 8010 8016 8022 8025 8033 8036 8039 8044 8048 8053 8059 8061 8066 8...

result:

ok 2 lines

Test #44:

score: 29
Accepted
time: 35ms
memory: 15996kb

input:

100000 50000 50000
1 2
1 3
1 4
1 5
1 6
1 25
1 31
1 202
1 666
1 780
1 3194
1 41093
2 26
2 77
2 117
2 440
2 527
2 1063
2 1867
2 13853
2 15614
3 7
3 8
3 16
3 110
3 225
3 1404
3 2939
3 5271
3 42219
3 77189
4 32
4 109
4 1570
4 1614
4 2456
4 3365
4 7719
4 8233
4 58195
4 87792
5 13
5 19
5 122
5 188
5 350
5...

output:

0


result:

ok single line: '0'

Test #45:

score: 29
Accepted
time: 38ms
memory: 16036kb

input:

100000 50000 50000
1 2
1 3
1 8
1 10
1 35
1 61
1 74
1 151
1 258
1 453
1 547
1 2551
1 9831
1 13537
2 4
2 6
2 7
2 25
2 31
2 85
2 114
2 230
2 346
2 435
2 436
2 2076
2 2630
2 29441
2 31058
2 45267
3 12
3 98
3 210
3 284
3 510
3 748
3 776
3 7379
3 13801
3 47541
4 5
4 11
4 17
4 18
4 107
4 130
4 140
4 1138
4...

output:

0


result:

ok single line: '0'

Test #46:

score: 29
Accepted
time: 38ms
memory: 16036kb

input:

100000 50000 50000
1 2
1 10
1 56
1 86
1 881
1 1881
1 9653
1 16330
1 16408
1 79445
2 3
2 14
2 20
2 31
2 83
2 1138
3 4
3 12
3 15
3 23
3 6392
3 29657
3 42013
4 5
4 6
4 13
4 18
4 176
4 5357
4 7236
4 8271
4 15963
4 47479
5 7
5 8
5 39
5 48
5 55
5 590
5 771
5 1364
5 1466
5 2581
5 65537
6 27
6 94
6 125
6 53...

output:

0


result:

ok single line: '0'

Test #47:

score: 29
Accepted
time: 32ms
memory: 19704kb

input:

100000 50000 50000
1 2
1 53311
2 3
2 54896
3 4
3 65577
3 72775
3 92317
4 5
5 6
6 7
7 8
7 56026
8 9
8 59658
8 95562
9 10
9 59547
10 11
11 12
11 59625
11 82618
12 13
13 14
14 15
15 16
16 17
16 75599
16 80627
17 18
18 19
19 20
20 21
21 22
22 23
22 54774
22 69321
22 88301
23 24
23 52454
23 64331
23 9049...

output:

10462
29573 29575 29576 29577 29578 29582 29586 29587 29588 29589 29591 29593 29595 29596 29599 29601 29602 29603 29605 29607 29608 29609 29610 29611 29612 29615 29616 29617 29618 29620 29621 29622 29623 29624 29625 29626 29627 29628 29631 29634 29635 29637 29638 29640 29642 29643 29645 29646 29647 ...

result:

ok 2 lines

Test #48:

score: 29
Accepted
time: 29ms
memory: 19704kb

input:

100000 50000 50000
1 2
1 98739
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
11 63429
12 13
13 14
13 84602
13 93828
13 94431
14 15
15 16
15 51559
15 91204
15 96091
16 17
17 18
18 19
19 20
20 21
20 58296
21 22
21 68866
22 23
23 24
24 25
24 71090
25 26
26 27
27 28
28 29
29 30
29 93585
30 31
30 99639
31...

output:

5255
16354 16357 16358 16359 16361 16362 16363 16365 16366 16368 16369 16371 16373 16376 16377 16380 16381 16383 16384 16385 16387 16390 16391 16394 16397 16398 16399 16403 16405 16409 16410 16411 16413 16417 16419 16420 16422 16425 16426 16428 16429 16430 16432 16435 16437 16439 16441 16442 16445 1...

result:

ok 2 lines

Subtask #5:

score: 0
Wrong Answer

Dependency #4:

100%
Accepted

Test #49:

score: 16
Accepted
time: 34ms
memory: 19700kb

input:

100000 25100 25100
1 2
2 3
3 4
3 68643
4 5
5 6
5 70418
6 7
6 68653
7 8
8 9
8 89530
9 10
9 84034
9 90061
10 11
10 71209
11 12
11 76160
12 13
13 14
14 15
15 16
15 62077
16 17
17 18
17 60594
18 19
18 51933
19 20
19 69592
20 21
20 65868
21 22
22 23
23 24
23 88081
24 25
25 26
25 50544
25 63077
26 27
27 2...

output:

13534
33918 33922 33924 33925 33926 33927 33929 33931 33932 33933 33934 33935 33936 33938 33939 33940 33941 33944 33946 33947 33949 33951 33952 33954 33956 33958 33959 33960 33961 33962 33965 33967 33969 33971 33972 33974 33976 33979 33980 33981 33982 33983 33984 33986 33988 33989 33991 33992 33994 ...

result:

ok 2 lines

Test #50:

score: 16
Accepted
time: 35ms
memory: 19700kb

input:

100000 25100 25100
1 2
2 3
3 4
3 51084
4 5
5 6
5 65577
6 7
7 8
7 65820
8 9
9 10
9 51566
10 11
11 12
11 89596
12 13
13 14
14 15
14 88558
15 16
16 17
17 18
17 77957
18 19
18 60359
19 20
20 21
20 95036
21 22
22 23
22 77911
22 92900
23 24
23 85587
23 90371
24 25
25 26
25 53283
26 27
26 87836
27 28
27 50...

output:

14213
49644 49646 49648 49650 49651 49653 49655 49656 49657 49658 49660 49661 49662 49663 49665 49666 49667 49670 49672 49674 49676 49679 49680 49682 49683 49684 49685 49687 49689 49690 49691 49692 49693 49694 49695 49697 49698 49699 49700 49702 49705 49706 49709 49712 49713 49716 49718 49719 49721 ...

result:

ok 2 lines

Test #51:

score: 16
Accepted
time: 25ms
memory: 21260kb

input:

100000 600 600
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51...

output:

96322
2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529...

result:

ok 2 lines

Test #52:

score: 16
Accepted
time: 25ms
memory: 21136kb

input:

100000 600 600
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51...

output:

91388
3035 3036 3037 3038 3039 3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 3050 3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093...

result:

ok 2 lines

Test #53:

score: 0
Wrong Answer
time: 30ms
memory: 19124kb

input:

100000 200 200
1 2
1 3
1 5
1 13
1 18
1 19
1 23
1 28
1 34
1 46
1 73
1 76
1 79
1 81
1 93
1 98
1 130
1 132
1 149
1 165
1 174
1 182
1 198
1 215
1 219
1 221
1 251
1 252
1 255
1 256
1 287
1 294
1 310
1 311
1 313
1 314
1 324
1 334
1 356
1 357
1 358
1 377
1 379
1 381
1 384
1 386
1 407
1 415
1 426
1 428
1 44...

output:

9
1 2 9938 3 39869 49946 60004 9939 39870 

result:

wrong answer 2nd lines differ - expected: '1 2 3 9938 9939 39869 39870 49946 60004', found: '1 2 9938 3 39869 49946 60004 9939 39870 '

Subtask #6:

score: 0
Skipped

Dependency #1:

0%