# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
439668 |
2021-06-30T13:50:13 Z |
Ya_Ali |
Railway (BOI17_railway) |
C++17 |
|
165 ms |
34208 KB |
/* ** *** In the name of God *** ** */
// Only Haider is Amir al-Momenin
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 10, lg = 17;
const ll mod = 1e9 + 7;
#define endl '\n'
ll tin [maxn], tout [maxn], anc [maxn][lg], H [maxn], khar_and_mother [maxn], tala [maxn], T, n, m, k;
vector <pair<ll, ll>> g [maxn];
vector <ll> A, ali;
void DFS (const ll &v = 1, const ll &pr = 1) {
tin[v] = ++T;
H[v] = H[pr] + 1;
anc[v][0] = pr;
for (ll i = 1; i < lg; i++) anc[v][i] = anc[anc[v][i - 1]][i - 1];
for (auto &u : g[v]) if (u.first != pr) DFS(u.first, v);
tout[v] = T;
}
inline ll up (ll v, const ll &d) { for (ll i = lg; i--;) if (d >> i & 1) v = anc[v][i]; return v; }
inline ll lca (ll v, ll u) {
if (H[v] > H[u]) swap(v, u);
u = up(u, H[u] - H[v]);
if (v == u) return v;
for (ll i = lg; i--;) if (anc[v][i] ^ anc[u][i]) v = anc[v][i], u = anc[u][i];
return anc[v][0];
}
void add (ll s) {
sort(A.begin(), A.end(), [&](const ll &v, const ll &u) { return tin[v] < tin[u]; });
for (ll i = 1; i < s; i++) A.push_back(lca(A[i - 1], A[i]));
sort(A.begin(), A.end(), [&](const ll &v, const ll &u) { return tin[v] < tin[u]; });
A.resize(unique(A.begin(), A.end()) - A.begin());
ali.clear();
for (auto &v : A) {
while (!ali.empty() && !(tin[ali.back()] <= tin[v] && tout[v] <= tout[ali.back()])) ali.pop_back();
if (!ali.empty()) khar_and_mother[v] = ali.back();
else khar_and_mother[v] = -1;
ali.push_back(v);
}
for (auto &v : A) if (khar_and_mother[v] != -1) tala[v]++, tala[khar_and_mother[v]]--;
}
ll what_the_fuck (const ll &v = 1, const ll &ep = 0) {
for (auto &u : g[v]) if (u.first != anc[v][0]) tala[v] += what_the_fuck(u.first, u.second);
if (ep && tala[v] >= k) A.push_back(ep);
return tala[v];
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>> n >> m >> k;
for (ll i = 1, v, u; i < n; i++) cin>> v >> u, g[v].push_back({u, i}), g[u].push_back({v, i});
DFS();
for (ll s; m--;) {
cin >> s;
A.resize(s);
for (auto &x : A) cin >> x;
add(s);
}
A.clear();
what_the_fuck();
sort(A.begin(), A.end());
cout<< A.size() << endl;
for (auto i : A) cout<< i << ' ';
return 0;
}
/*
_ _ _ _ _ _ _ _ _ _ _ _
/ / \ / / | / / |
/``````\ \ |`````| | |`````| |
/ \ \ | | | | | |
/ \ \ | | | | | |
/ /\ \ \ | | | | | |
/ / /\ \ \ | | | | | |
/ / / \ \ \ | | | | | |
/ / /_ _ \ \ \ | | | | | |
/ /_ _ _ _ \ \ \ | | | | | |
/ \ \ | | |_ _ _ _ | | |
/ _ _ _ _ _ _ _ \ \ | | / /| | | |
/ / / \ \ \ | |/_ _ _ _ / | | | |
/ / / \ \ / | | / | | /
/_ _ _/_/ \_ _ _\/ |_ _ _ _ _ _ _ _|/ |_ _ _|/
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
9 ms |
4940 KB |
Output is correct |
3 |
Correct |
9 ms |
4940 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
9 ms |
5452 KB |
Output is correct |
7 |
Correct |
9 ms |
5068 KB |
Output is correct |
8 |
Correct |
8 ms |
4992 KB |
Output is correct |
9 |
Correct |
8 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
2636 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
9 ms |
4940 KB |
Output is correct |
3 |
Correct |
9 ms |
4940 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
9 ms |
5452 KB |
Output is correct |
7 |
Correct |
9 ms |
5068 KB |
Output is correct |
8 |
Correct |
8 ms |
4992 KB |
Output is correct |
9 |
Correct |
8 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
2636 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
35 ms |
5304 KB |
Output is correct |
16 |
Correct |
37 ms |
5548 KB |
Output is correct |
17 |
Correct |
36 ms |
5516 KB |
Output is correct |
18 |
Correct |
9 ms |
5340 KB |
Output is correct |
19 |
Correct |
8 ms |
4996 KB |
Output is correct |
20 |
Correct |
31 ms |
5436 KB |
Output is correct |
21 |
Correct |
36 ms |
5512 KB |
Output is correct |
22 |
Correct |
2 ms |
2636 KB |
Output is correct |
23 |
Correct |
8 ms |
4988 KB |
Output is correct |
24 |
Correct |
8 ms |
4940 KB |
Output is correct |
25 |
Correct |
2 ms |
2636 KB |
Output is correct |
26 |
Correct |
2 ms |
2636 KB |
Output is correct |
27 |
Correct |
10 ms |
5392 KB |
Output is correct |
28 |
Correct |
9 ms |
5068 KB |
Output is correct |
29 |
Correct |
8 ms |
4992 KB |
Output is correct |
30 |
Correct |
8 ms |
4940 KB |
Output is correct |
31 |
Correct |
2 ms |
2636 KB |
Output is correct |
32 |
Correct |
2 ms |
2636 KB |
Output is correct |
33 |
Correct |
2 ms |
2636 KB |
Output is correct |
34 |
Correct |
2 ms |
2636 KB |
Output is correct |
35 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
139 ms |
33848 KB |
Output is correct |
2 |
Correct |
2 ms |
2712 KB |
Output is correct |
3 |
Correct |
146 ms |
33348 KB |
Output is correct |
4 |
Correct |
127 ms |
32580 KB |
Output is correct |
5 |
Correct |
161 ms |
33992 KB |
Output is correct |
6 |
Correct |
136 ms |
34208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
109 ms |
29524 KB |
Output is correct |
2 |
Correct |
135 ms |
27072 KB |
Output is correct |
3 |
Correct |
136 ms |
26692 KB |
Output is correct |
4 |
Correct |
143 ms |
26820 KB |
Output is correct |
5 |
Correct |
132 ms |
26764 KB |
Output is correct |
6 |
Correct |
108 ms |
29828 KB |
Output is correct |
7 |
Correct |
107 ms |
29552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
109 ms |
29524 KB |
Output is correct |
2 |
Correct |
135 ms |
27072 KB |
Output is correct |
3 |
Correct |
136 ms |
26692 KB |
Output is correct |
4 |
Correct |
143 ms |
26820 KB |
Output is correct |
5 |
Correct |
132 ms |
26764 KB |
Output is correct |
6 |
Correct |
108 ms |
29828 KB |
Output is correct |
7 |
Correct |
107 ms |
29552 KB |
Output is correct |
8 |
Correct |
149 ms |
30112 KB |
Output is correct |
9 |
Correct |
147 ms |
30144 KB |
Output is correct |
10 |
Correct |
132 ms |
34016 KB |
Output is correct |
11 |
Correct |
139 ms |
33892 KB |
Output is correct |
12 |
Correct |
120 ms |
25920 KB |
Output is correct |
13 |
Correct |
119 ms |
26036 KB |
Output is correct |
14 |
Correct |
144 ms |
26684 KB |
Output is correct |
15 |
Correct |
159 ms |
26616 KB |
Output is correct |
16 |
Correct |
143 ms |
26792 KB |
Output is correct |
17 |
Correct |
135 ms |
26744 KB |
Output is correct |
18 |
Correct |
133 ms |
26692 KB |
Output is correct |
19 |
Correct |
123 ms |
26972 KB |
Output is correct |
20 |
Correct |
107 ms |
30060 KB |
Output is correct |
21 |
Correct |
112 ms |
30016 KB |
Output is correct |
22 |
Correct |
107 ms |
29968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
9 ms |
4940 KB |
Output is correct |
3 |
Correct |
9 ms |
4940 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
9 ms |
5452 KB |
Output is correct |
7 |
Correct |
9 ms |
5068 KB |
Output is correct |
8 |
Correct |
8 ms |
4992 KB |
Output is correct |
9 |
Correct |
8 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
2636 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
35 ms |
5304 KB |
Output is correct |
16 |
Correct |
37 ms |
5548 KB |
Output is correct |
17 |
Correct |
36 ms |
5516 KB |
Output is correct |
18 |
Correct |
9 ms |
5340 KB |
Output is correct |
19 |
Correct |
8 ms |
4996 KB |
Output is correct |
20 |
Correct |
31 ms |
5436 KB |
Output is correct |
21 |
Correct |
36 ms |
5512 KB |
Output is correct |
22 |
Correct |
2 ms |
2636 KB |
Output is correct |
23 |
Correct |
8 ms |
4988 KB |
Output is correct |
24 |
Correct |
8 ms |
4940 KB |
Output is correct |
25 |
Correct |
2 ms |
2636 KB |
Output is correct |
26 |
Correct |
2 ms |
2636 KB |
Output is correct |
27 |
Correct |
10 ms |
5392 KB |
Output is correct |
28 |
Correct |
9 ms |
5068 KB |
Output is correct |
29 |
Correct |
8 ms |
4992 KB |
Output is correct |
30 |
Correct |
8 ms |
4940 KB |
Output is correct |
31 |
Correct |
2 ms |
2636 KB |
Output is correct |
32 |
Correct |
2 ms |
2636 KB |
Output is correct |
33 |
Correct |
2 ms |
2636 KB |
Output is correct |
34 |
Correct |
2 ms |
2636 KB |
Output is correct |
35 |
Correct |
2 ms |
2636 KB |
Output is correct |
36 |
Correct |
139 ms |
33848 KB |
Output is correct |
37 |
Correct |
2 ms |
2712 KB |
Output is correct |
38 |
Correct |
146 ms |
33348 KB |
Output is correct |
39 |
Correct |
127 ms |
32580 KB |
Output is correct |
40 |
Correct |
161 ms |
33992 KB |
Output is correct |
41 |
Correct |
136 ms |
34208 KB |
Output is correct |
42 |
Correct |
109 ms |
29524 KB |
Output is correct |
43 |
Correct |
135 ms |
27072 KB |
Output is correct |
44 |
Correct |
136 ms |
26692 KB |
Output is correct |
45 |
Correct |
143 ms |
26820 KB |
Output is correct |
46 |
Correct |
132 ms |
26764 KB |
Output is correct |
47 |
Correct |
108 ms |
29828 KB |
Output is correct |
48 |
Correct |
107 ms |
29552 KB |
Output is correct |
49 |
Correct |
149 ms |
30112 KB |
Output is correct |
50 |
Correct |
147 ms |
30144 KB |
Output is correct |
51 |
Correct |
132 ms |
34016 KB |
Output is correct |
52 |
Correct |
139 ms |
33892 KB |
Output is correct |
53 |
Correct |
120 ms |
25920 KB |
Output is correct |
54 |
Correct |
119 ms |
26036 KB |
Output is correct |
55 |
Correct |
144 ms |
26684 KB |
Output is correct |
56 |
Correct |
159 ms |
26616 KB |
Output is correct |
57 |
Correct |
143 ms |
26792 KB |
Output is correct |
58 |
Correct |
135 ms |
26744 KB |
Output is correct |
59 |
Correct |
133 ms |
26692 KB |
Output is correct |
60 |
Correct |
123 ms |
26972 KB |
Output is correct |
61 |
Correct |
107 ms |
30060 KB |
Output is correct |
62 |
Correct |
112 ms |
30016 KB |
Output is correct |
63 |
Correct |
107 ms |
29968 KB |
Output is correct |
64 |
Correct |
141 ms |
30224 KB |
Output is correct |
65 |
Correct |
154 ms |
26692 KB |
Output is correct |
66 |
Correct |
165 ms |
26692 KB |
Output is correct |
67 |
Correct |
161 ms |
26656 KB |
Output is correct |
68 |
Correct |
110 ms |
25836 KB |
Output is correct |
69 |
Correct |
102 ms |
25800 KB |
Output is correct |
70 |
Correct |
132 ms |
30644 KB |
Output is correct |
71 |
Correct |
134 ms |
29852 KB |
Output is correct |
72 |
Correct |
3 ms |
2636 KB |
Output is correct |
73 |
Correct |
8 ms |
4940 KB |
Output is correct |
74 |
Correct |
9 ms |
4996 KB |
Output is correct |
75 |
Correct |
3 ms |
2636 KB |
Output is correct |
76 |
Correct |
2 ms |
2636 KB |
Output is correct |
77 |
Correct |
9 ms |
5452 KB |
Output is correct |
78 |
Correct |
9 ms |
5068 KB |
Output is correct |
79 |
Correct |
7 ms |
4864 KB |
Output is correct |
80 |
Correct |
9 ms |
4940 KB |
Output is correct |
81 |
Correct |
2 ms |
2636 KB |
Output is correct |
82 |
Correct |
2 ms |
2636 KB |
Output is correct |
83 |
Correct |
2 ms |
2636 KB |
Output is correct |
84 |
Correct |
2 ms |
2636 KB |
Output is correct |
85 |
Correct |
2 ms |
2636 KB |
Output is correct |
86 |
Correct |
34 ms |
5368 KB |
Output is correct |
87 |
Correct |
35 ms |
5444 KB |
Output is correct |
88 |
Correct |
38 ms |
5428 KB |
Output is correct |
89 |
Correct |
9 ms |
5324 KB |
Output is correct |
90 |
Correct |
9 ms |
5048 KB |
Output is correct |
91 |
Correct |
32 ms |
5592 KB |
Output is correct |
92 |
Correct |
35 ms |
5436 KB |
Output is correct |
93 |
Correct |
2 ms |
2636 KB |
Output is correct |
94 |
Correct |
139 ms |
33892 KB |
Output is correct |
95 |
Correct |
136 ms |
33392 KB |
Output is correct |
96 |
Correct |
139 ms |
32620 KB |
Output is correct |
97 |
Correct |
148 ms |
33976 KB |
Output is correct |
98 |
Correct |
138 ms |
34204 KB |
Output is correct |
99 |
Correct |
140 ms |
26944 KB |
Output is correct |
100 |
Correct |
128 ms |
26688 KB |
Output is correct |
101 |
Correct |
128 ms |
26792 KB |
Output is correct |
102 |
Correct |
143 ms |
27152 KB |
Output is correct |
103 |
Correct |
111 ms |
29612 KB |
Output is correct |
104 |
Correct |
115 ms |
30088 KB |
Output is correct |
105 |
Correct |
104 ms |
29576 KB |
Output is correct |
106 |
Correct |
135 ms |
30260 KB |
Output is correct |
107 |
Correct |
142 ms |
30108 KB |
Output is correct |
108 |
Correct |
155 ms |
34008 KB |
Output is correct |
109 |
Correct |
148 ms |
33996 KB |
Output is correct |
110 |
Correct |
113 ms |
25920 KB |
Output is correct |
111 |
Correct |
123 ms |
26040 KB |
Output is correct |
112 |
Correct |
135 ms |
26692 KB |
Output is correct |
113 |
Correct |
137 ms |
26668 KB |
Output is correct |