QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#930684 | #31. Railway | nhuang685# | 36 | 38ms | 21260kb | C++23 | 3.5kb | 2025-03-10 05:10:51 | 2025-03-10 05:10:53 |
Judging History
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%