QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#546877 | #31. Railway | thangthang | 36 | 85ms | 53024kb | C++20 | 4.0kb | 2024-09-04 15:17:43 | 2024-09-04 15:17:44 |
Judging History
answer
// author : thembululquaUwU
// 3.9.2024
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'
using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;
const int MaxN = 2e5;
const int mod = 1e9 + 7;
void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}
struct LCA{
vi st, ed, _lg, high, par, ans, a, b, labp;
vector <vi> euler, adj;
int cnt;
void dfs(int u, int pa){
++ cnt;
st[u] = cnt;
euler[cnt].pb(u);
for (int id : adj[u]){
int v = a[id] ^ b[id] ^ u;
if (v == pa) {
labp[u] = id;
continue;
}
high[v] = high[u] + 1;
dfs(v, u);
euler[++ cnt].pb(u);
}
ed[u] = cnt;
}
int check(int u, int v) {
return st[u] <= st[v] && ed[v] <= ed[u];
}
int min_by_time(int u, int v) {
return (st[u] < st[v] ? u : v);
}
void add(int u, int v){
a.pb(u);
b.pb(v);
adj[u].pb(a.size() - 1);
adj[v].pb(a.size() - 1);
}
LCA(int n){
st.resize(n + 3, 0);
par.resize(n + 3, 0);
labp.resize(n + 3, 0);
ans.resize(n + 3, 0);
ed.resize(n + 3, 0);
euler.resize(2 * n + 5);
adj.resize(n + 3);
_lg.resize(2 * n + 5);
high.resize(n + 3, 1);
for (int i = 0; i <= 2 * n; ++ i) _lg[i] = log2(i);
}
void init(int r){
cnt = 0;
dfs(r, 0);
for (int lg = 1; lg < 20; ++lg) {
for (int i = 1; i + (1 << lg) - 1 <= cnt; ++i)
euler[i].pb(min_by_time(euler[i][lg - 1], euler[i + (1 << lg - 1)][lg - 1]));
}
}
int get(int u, int v) {
int L = min(st[u], st[v]);
int R = max(ed[u], ed[v]);
int lg = _lg[R - L + 1];
return min_by_time(euler[L][lg], euler[R - (1 << lg) + 1][lg]);
}
int dist(int u, int v){
int lc = get(u, v);
return high[u] + high[v] - 2 * high[lc];
}
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fd(sr, x) (lower_bound(sr.begin(), sr.end(), x) - sr.begin())
#define uq(sr) (sr).erase(unique(all((sr))), (sr).end())
void process(vector <int> s){
int n = s.size();
for (int i = 1; i < n; ++ i) s.pb(get(s[i], s[i - 1]));
sort(all(s), [&](int u, int v){
return st[u] < st[v];
});
uq(s); vi st;
reverse(all(s));
for (int u : s){
while (st.size() && check(u, st.back())){
par[st.back()] = u;
ans[st.back()] ++;
ans[u] --;
st.pop_back();
}
st.push_back(u);
}
}
void last(int u, int pa){
for (int id : adj[u]){
int v = a[id] ^ b[id] ^ u;
if (v ^ pa) {
last(v, u);
ans[u] += ans[v];
}
}
}
};
void solve(){
int n, m, k; cin >> n >> m >> k;
LCA tree(n);
for (int i = 1, a, b; i < n; ++ i) cin >> a >> b, tree.add(a, b);
tree.init(1);
while (m --) {
int t; cin >> t;
vi s; while (t --){
int a; cin >> a; s.pb(a);
}
tree.process(s);
}
tree.last(1, 0); int ans = 0; vi used(n - 1, 0);
for (int i = 1; i <= n; ++ i) if (tree.ans[i] >= k) {++ ans; used[tree.labp[i]] = 1;}
cout << ans << '\n';
for (int i = 0; i < n - 1; ++ i) if (used[i]) cout << i + 1 << ' ';
}
int main(){
if (fopen("pqh.inp", "r")){
freopen("pqh.inp", "r", stdin);
freopen("pqh.out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1; // cin >> t;
while (t --) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 8
Accepted
time: 0ms
memory: 3892kb
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 7 8 9
result:
ok 2 lines
Test #2:
score: 8
Accepted
time: 7ms
memory: 6464kb
input:
10000 200 20 1 2 1 3 1 4 1 6 1 228 1 1392 1 1486 1 5068 1 6341 1 6847 2 8 2 10 2 23 2 25 2 34 2 56 2 103 2 341 2 1574 2 5024 2 9238 3 5 3 59 3 89 3 572 3 1539 4 12 4 183 4 2192 4 3944 4 8883 5 7 5 16 5 18 5 40 5 73 5 126 5 414 6 9 6 14 6 15 6 17 6 88 6 2577 7 45 7 63 7 68 7 292 7 484 7 1249 7 1522 7...
output:
76 1 2 4 11 12 14 15 22 32 33 34 39 45 56 62 63 74 81 103 117 122 132 139 156 161 213 228 234 263 267 273 291 307 323 375 472 567 663 688 733 936 1036 1125 1378 1635 1903 2124 2193 2363 3317 3318 3496 3539 3540 4231 4232 5044 5049 5524 5564 5749 5885 5886 6118 6157 6158 6775 7241 7242 7835 8416 8417...
result:
ok 2 lines
Test #3:
score: 0
Wrong Answer
time: 7ms
memory: 6520kb
input:
10000 200 55 1 2 1 4 1 14 1 58 1 366 2 3 2 7 2 40 2 166 2 201 2 399 2 1327 2 5058 3 6 3 11 3 16 3 25 3 34 3 104 3 156 3 1735 4 5 4 10 4 27 4 68 4 72 4 80 4 506 4 954 4 1802 4 3857 4 8289 5 35 5 555 5 1231 5 2177 5 4045 5 9735 6 9 6 13 6 18 6 21 6 114 6 121 6 139 6 203 6 345 6 411 6 1579 6 1915 6 697...
output:
57 1 2 6 7 8 14 15 18 23 40 53 67 79 83 84 92 99 108 132 195 224 236 254 283 290 354 491 654 658 668 691 777 782 798 995 1029 1153 1470 1488 1677 1744 2280 2287 2397 2399 2509 2579 2881 3144 3818 3837 3869 4356 5959 6384 6438 6713
result:
wrong answer 1st lines differ - expected: '23', found: '57'
Subtask #2:
score: 0
Wrong Answer
Test #15:
score: 0
Wrong Answer
time: 11ms
memory: 6568kb
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:
1597 1 2 3 4 5 9 10 12 13 18 19 20 21 29 30 31 32 33 36 37 38 39 40 41 42 43 48 49 50 51 56 57 58 59 60 61 65 66 67 68 71 72 73 74 75 76 80 81 82 83 85 86 89 91 92 93 94 95 97 98 99 101 102 103 105 106 107 109 110 111 112 117 118 119 120 122 123 131 132 135 137 138 139 140 142 145 150 151 152 153 15...
result:
wrong answer 1st lines differ - expected: '1430', found: '1597'
Subtask #3:
score: 7
Accepted
Test #36:
score: 7
Accepted
time: 80ms
memory: 53024kb
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: 0ms
memory: 3872kb
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: 80ms
memory: 52904kb
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: 71ms
memory: 52884kb
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: 76ms
memory: 52888kb
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: 65ms
memory: 52908kb
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: 63ms
memory: 47340kb
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: 85ms
memory: 42444kb
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: 79ms
memory: 41944kb
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: 83ms
memory: 41992kb
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: 79ms
memory: 42012kb
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: 79ms
memory: 47496kb
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: 60ms
memory: 47412kb
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: 0
Wrong Answer
time: 85ms
memory: 47472kb
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:
13569 33903 33906 33907 33910 33911 33913 33916 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 ...
result:
wrong answer 1st lines differ - expected: '13534', found: '13569'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%