//thatsramen
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define eb emplace_back
#define pb push_back
#define ft first
#define sd second
#define pi pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(...) dbg_out(__VA_ARGS__)
using ll = long long;
using ld = long double;
using namespace std;
using namespace __gnu_pbds;
//Constants
const ll INF = 5 * 1e18;
const int IINF = 2 * 1e9;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ld PI = 3.14159265359;
//Templates
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) {return os << '(' << p.first << ", " << p.second << ')';}
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) {os << '['; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << ']';}
void dbg_out() {cerr << endl;}
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << H << ' '; dbg_out(T...); }
template<typename T> void mins(T& x, T y) {x = min(x, y);}
template<typename T> void maxs(T& x, T y) {x = max(x, y);}
template<typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using omset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
//order_of_key(k): number of elements strictly less than k
//find_by_order(k): k-th element in the set
void setPrec() {cout << fixed << setprecision(15);}
void unsyncIO() {cin.tie(0)->sync_with_stdio(0);}
void setIn(string s) {freopen(s.c_str(), "r", stdin);}
void setOut(string s) {freopen(s.c_str(), "w", stdout);}
void setIO(string s = "") {
unsyncIO(); setPrec();
if(s.size()) setIn(s + ".in"), setOut(s + ".out");
}
// #define TEST_CASES
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<vector<pi>> e(n + 5);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
e[u].pb({v, i}); e[v].pb({u, i});
}
vector<int> par(n + 5), dep(n + 5, 0);
function<void(int, int)> dfs_init = [&](int f, int p) {
for (const auto &[to, id] : e[f]) {
if (to == p) continue;
dep[to] = dep[f] + 1;
par[to] = f;
dfs_init(to, f);
}
};
dfs_init(1, -1);
par[1] = 1;
vector<vector<int>> jump(n + 5, vector<int> (20));
for (int i = 1; i <= n; i++) {
jump[i][0] = par[i];
}
for (int i = 1; i < 20; i++) {
for (int j = 1; j <= n; j++) {
jump[j][i] = jump[jump[j][i - 1]][i - 1];
}
}
auto get = [&](int u, int v) -> int {
if (dep[u] < dep[v]) swap(u, v);
for (int i = 19; i >= 0; i--) {
int to = jump[u][i];
if (dep[to] >= dep[v]) {
u = to;
}
}
if (u == v) return u;
for (int i = 19; i >= 0; i--) {
if (jump[u][i] != jump[v][i]) {
u = jump[u][i];
v = jump[v][i];
}
}
return par[u];
};
vector<int> val(n + 5, 0);
vector<map<int, int>> comps(n + 5);
for (int i = 0; i < m; i++) {
int z; cin >> z;
vector<int> cur(z);
for (int j = 0; j < z; j++) {
cin >> cur[j];
}
for (int j = 0; j < z - 1; j++) {
int lca = get(cur[j], cur[j + 1]);
comps[cur[j]][i]++;
comps[cur[j + 1]][i]++;
comps[lca][i] -= 2;
}
}
vector<int> sz(n + 5), ans;
function<void(int, int)> dfs_size = [&](int f, int p) {
sz[f] = (int) comps[f].size();
for (const auto &[to, id] : e[f]) {
if (to == p) continue;
dfs_size(to, f);
sz[f] += sz[to];
}
};
dfs_size(1, -1);
auto merge = [&](int u, int v) {
for (const auto &[x, y] : comps[v]) {
comps[u][x] += y;
if (comps[u][x] == 0) {
comps[u].erase(x);
}
}
};
function<void(int, int)> dfs = [&](int f, int p) {
int big = -1, big_id = -1;
for (const auto &[to, id] : e[f]) {
if (to == p) continue;
if (big == -1 || sz[to] > sz[big])
big = to, big_id = id;
}
if (big != -1) {
dfs(big, f);
if ((int) comps[big].size() >= k)
ans.pb(big_id + 1);
swap(comps[big], comps[f]);
merge(f, big);
}
for (const auto &[to, id] : e[f]) {
if (to == p || to == big) continue;
dfs(to, f);
if ((int) comps[to].size() >= k)
ans.pb(id + 1);
merge(f, to);
}
//dbg(f, comps[f]);
};
dfs(1, -1);
cout << ans.size() << '\n';
sort(all(ans));
for (int x : ans) {
cout << x << ' ';
}
}
int main() {
setIO();
int tt = 1;
#ifdef TEST_CASES
cin >> tt;
#endif
while (tt--)
solve();
return 0;
}
Compilation message
railway.cpp: In function 'void setIn(std::string)':
railway.cpp:44:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | void setIn(string s) {freopen(s.c_str(), "r", stdin);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
railway.cpp: In function 'void setOut(std::string)':
railway.cpp:45:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | void setOut(string s) {freopen(s.c_str(), "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
8 ms |
2900 KB |
Output is correct |
3 |
Correct |
7 ms |
2900 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
8 ms |
3524 KB |
Output is correct |
7 |
Correct |
8 ms |
3028 KB |
Output is correct |
8 |
Correct |
7 ms |
3064 KB |
Output is correct |
9 |
Correct |
7 ms |
3148 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
8 ms |
2900 KB |
Output is correct |
3 |
Correct |
7 ms |
2900 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
8 ms |
3524 KB |
Output is correct |
7 |
Correct |
8 ms |
3028 KB |
Output is correct |
8 |
Correct |
7 ms |
3064 KB |
Output is correct |
9 |
Correct |
7 ms |
3148 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
86 ms |
9168 KB |
Output is correct |
16 |
Correct |
82 ms |
9220 KB |
Output is correct |
17 |
Correct |
91 ms |
9240 KB |
Output is correct |
18 |
Correct |
9 ms |
3656 KB |
Output is correct |
19 |
Correct |
7 ms |
3152 KB |
Output is correct |
20 |
Correct |
79 ms |
8148 KB |
Output is correct |
21 |
Correct |
69 ms |
8064 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
7 ms |
2900 KB |
Output is correct |
24 |
Correct |
7 ms |
2900 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
8 ms |
3540 KB |
Output is correct |
28 |
Correct |
7 ms |
3028 KB |
Output is correct |
29 |
Correct |
7 ms |
3036 KB |
Output is correct |
30 |
Correct |
7 ms |
3156 KB |
Output is correct |
31 |
Correct |
1 ms |
212 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
324 KB |
Output is correct |
35 |
Correct |
1 ms |
320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
236 ms |
43220 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
226 ms |
42920 KB |
Output is correct |
4 |
Correct |
196 ms |
42480 KB |
Output is correct |
5 |
Correct |
201 ms |
42308 KB |
Output is correct |
6 |
Correct |
189 ms |
44900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
167 ms |
39728 KB |
Output is correct |
2 |
Correct |
223 ms |
37300 KB |
Output is correct |
3 |
Correct |
247 ms |
42800 KB |
Output is correct |
4 |
Correct |
233 ms |
43596 KB |
Output is correct |
5 |
Correct |
246 ms |
43416 KB |
Output is correct |
6 |
Correct |
172 ms |
39976 KB |
Output is correct |
7 |
Correct |
167 ms |
39772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
167 ms |
39728 KB |
Output is correct |
2 |
Correct |
223 ms |
37300 KB |
Output is correct |
3 |
Correct |
247 ms |
42800 KB |
Output is correct |
4 |
Correct |
233 ms |
43596 KB |
Output is correct |
5 |
Correct |
246 ms |
43416 KB |
Output is correct |
6 |
Correct |
172 ms |
39976 KB |
Output is correct |
7 |
Correct |
167 ms |
39772 KB |
Output is correct |
8 |
Correct |
180 ms |
39220 KB |
Output is correct |
9 |
Correct |
193 ms |
39068 KB |
Output is correct |
10 |
Correct |
167 ms |
42180 KB |
Output is correct |
11 |
Correct |
164 ms |
42260 KB |
Output is correct |
12 |
Correct |
134 ms |
30764 KB |
Output is correct |
13 |
Correct |
136 ms |
30760 KB |
Output is correct |
14 |
Correct |
206 ms |
37640 KB |
Output is correct |
15 |
Correct |
206 ms |
37604 KB |
Output is correct |
16 |
Correct |
248 ms |
44864 KB |
Output is correct |
17 |
Correct |
244 ms |
44776 KB |
Output is correct |
18 |
Correct |
242 ms |
42868 KB |
Output is correct |
19 |
Correct |
224 ms |
38212 KB |
Output is correct |
20 |
Correct |
178 ms |
40224 KB |
Output is correct |
21 |
Correct |
176 ms |
40152 KB |
Output is correct |
22 |
Correct |
186 ms |
40328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
8 ms |
2900 KB |
Output is correct |
3 |
Correct |
7 ms |
2900 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
8 ms |
3524 KB |
Output is correct |
7 |
Correct |
8 ms |
3028 KB |
Output is correct |
8 |
Correct |
7 ms |
3064 KB |
Output is correct |
9 |
Correct |
7 ms |
3148 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
86 ms |
9168 KB |
Output is correct |
16 |
Correct |
82 ms |
9220 KB |
Output is correct |
17 |
Correct |
91 ms |
9240 KB |
Output is correct |
18 |
Correct |
9 ms |
3656 KB |
Output is correct |
19 |
Correct |
7 ms |
3152 KB |
Output is correct |
20 |
Correct |
79 ms |
8148 KB |
Output is correct |
21 |
Correct |
69 ms |
8064 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
7 ms |
2900 KB |
Output is correct |
24 |
Correct |
7 ms |
2900 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
8 ms |
3540 KB |
Output is correct |
28 |
Correct |
7 ms |
3028 KB |
Output is correct |
29 |
Correct |
7 ms |
3036 KB |
Output is correct |
30 |
Correct |
7 ms |
3156 KB |
Output is correct |
31 |
Correct |
1 ms |
212 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
324 KB |
Output is correct |
35 |
Correct |
1 ms |
320 KB |
Output is correct |
36 |
Correct |
236 ms |
43220 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
226 ms |
42920 KB |
Output is correct |
39 |
Correct |
196 ms |
42480 KB |
Output is correct |
40 |
Correct |
201 ms |
42308 KB |
Output is correct |
41 |
Correct |
189 ms |
44900 KB |
Output is correct |
42 |
Correct |
167 ms |
39728 KB |
Output is correct |
43 |
Correct |
223 ms |
37300 KB |
Output is correct |
44 |
Correct |
247 ms |
42800 KB |
Output is correct |
45 |
Correct |
233 ms |
43596 KB |
Output is correct |
46 |
Correct |
246 ms |
43416 KB |
Output is correct |
47 |
Correct |
172 ms |
39976 KB |
Output is correct |
48 |
Correct |
167 ms |
39772 KB |
Output is correct |
49 |
Correct |
180 ms |
39220 KB |
Output is correct |
50 |
Correct |
193 ms |
39068 KB |
Output is correct |
51 |
Correct |
167 ms |
42180 KB |
Output is correct |
52 |
Correct |
164 ms |
42260 KB |
Output is correct |
53 |
Correct |
134 ms |
30764 KB |
Output is correct |
54 |
Correct |
136 ms |
30760 KB |
Output is correct |
55 |
Correct |
206 ms |
37640 KB |
Output is correct |
56 |
Correct |
206 ms |
37604 KB |
Output is correct |
57 |
Correct |
248 ms |
44864 KB |
Output is correct |
58 |
Correct |
244 ms |
44776 KB |
Output is correct |
59 |
Correct |
242 ms |
42868 KB |
Output is correct |
60 |
Correct |
224 ms |
38212 KB |
Output is correct |
61 |
Correct |
178 ms |
40224 KB |
Output is correct |
62 |
Correct |
176 ms |
40152 KB |
Output is correct |
63 |
Correct |
186 ms |
40328 KB |
Output is correct |
64 |
Correct |
204 ms |
39072 KB |
Output is correct |
65 |
Correct |
283 ms |
49468 KB |
Output is correct |
66 |
Correct |
257 ms |
44948 KB |
Output is correct |
67 |
Correct |
228 ms |
41332 KB |
Output is correct |
68 |
Correct |
110 ms |
29392 KB |
Output is correct |
69 |
Correct |
113 ms |
29636 KB |
Output is correct |
70 |
Correct |
172 ms |
40224 KB |
Output is correct |
71 |
Correct |
194 ms |
39160 KB |
Output is correct |
72 |
Correct |
1 ms |
212 KB |
Output is correct |
73 |
Correct |
8 ms |
2900 KB |
Output is correct |
74 |
Correct |
8 ms |
2900 KB |
Output is correct |
75 |
Correct |
1 ms |
324 KB |
Output is correct |
76 |
Correct |
1 ms |
212 KB |
Output is correct |
77 |
Correct |
7 ms |
3540 KB |
Output is correct |
78 |
Correct |
7 ms |
3052 KB |
Output is correct |
79 |
Correct |
7 ms |
3028 KB |
Output is correct |
80 |
Correct |
7 ms |
3028 KB |
Output is correct |
81 |
Correct |
1 ms |
212 KB |
Output is correct |
82 |
Correct |
1 ms |
212 KB |
Output is correct |
83 |
Correct |
0 ms |
212 KB |
Output is correct |
84 |
Correct |
1 ms |
212 KB |
Output is correct |
85 |
Correct |
1 ms |
212 KB |
Output is correct |
86 |
Correct |
69 ms |
9136 KB |
Output is correct |
87 |
Correct |
66 ms |
9092 KB |
Output is correct |
88 |
Correct |
66 ms |
9324 KB |
Output is correct |
89 |
Correct |
8 ms |
3708 KB |
Output is correct |
90 |
Correct |
7 ms |
3156 KB |
Output is correct |
91 |
Correct |
79 ms |
8116 KB |
Output is correct |
92 |
Correct |
88 ms |
8140 KB |
Output is correct |
93 |
Correct |
1 ms |
328 KB |
Output is correct |
94 |
Correct |
215 ms |
43208 KB |
Output is correct |
95 |
Correct |
216 ms |
42888 KB |
Output is correct |
96 |
Correct |
193 ms |
42420 KB |
Output is correct |
97 |
Correct |
202 ms |
42472 KB |
Output is correct |
98 |
Correct |
186 ms |
44868 KB |
Output is correct |
99 |
Correct |
252 ms |
47212 KB |
Output is correct |
100 |
Correct |
251 ms |
44352 KB |
Output is correct |
101 |
Correct |
251 ms |
44964 KB |
Output is correct |
102 |
Correct |
204 ms |
38012 KB |
Output is correct |
103 |
Correct |
167 ms |
39852 KB |
Output is correct |
104 |
Correct |
163 ms |
40280 KB |
Output is correct |
105 |
Correct |
163 ms |
39872 KB |
Output is correct |
106 |
Correct |
195 ms |
39256 KB |
Output is correct |
107 |
Correct |
190 ms |
39100 KB |
Output is correct |
108 |
Correct |
187 ms |
42268 KB |
Output is correct |
109 |
Correct |
157 ms |
42240 KB |
Output is correct |
110 |
Correct |
133 ms |
30808 KB |
Output is correct |
111 |
Correct |
137 ms |
30884 KB |
Output is correct |
112 |
Correct |
204 ms |
37476 KB |
Output is correct |
113 |
Correct |
227 ms |
37928 KB |
Output is correct |