#include "bits/stdc++.h"
#define fast ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define endl '\n'
#define int long long
#define f first
#define mp make_pair
#define s second
using namespace std;
int n, m, k;
int fa[100005][21], par[100005], dep[100005], arr[150005];
set <int> vals[100005], ans;
vector <int> g[100005], rem[100005], add[100005];
unordered_map<int, unordered_map<int,int> > edge;
void dfs(int x, int d, int p){
dep[x] = d;
par[x] = p;
for(int k : g[x]){
if(k != p) dfs(k, d + 1, x);
}
}
int LCA(int a, int b){
if(dep[a] > dep[b]) swap(a, b);
int d = dep[b] - dep[a];
for(int i = 0; i < 20; i++){
if(d & (1 << i)) b = fa[b][i];
}
if(a == b) return a;
for(int i = 20; i >= 0; i--){
if(fa[a][i] != fa[b][i]){
a = fa[a][i];
b = fa[b][i];
}
}
return par[a];
}
void solve(int node, int parent){
int big = node;
for(int i : g[node]){
if(i == parent) continue;
solve(i, node);
if(vals[i].size() > vals[big].size()) big = i;
if(vals[i].size() >= k) ans.insert(edge[node][i]);
}
swap(vals[node], vals[big]);
for(int i : g[node]){
if(i == parent) continue;
for(int x : vals[i]) vals[node].insert(x);
}
for(int i : add[node]) vals[node].insert(i);
for(int i : rem[node]) vals[node].erase(i);
}
signed main()
{
fast;
cin >> n >> m >> k;
for(int i = 0; i < n-1; i++){
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
edge[a][b] = edge[b][a] = i;
}
dfs(1, 1, -1);
par[1] = 1;
for(int i = 1; i <= n; i++) fa[i][0] = par[i];
for(int k = 0; k < 20; k++){
for(int i = 1; i <= n; i++){
fa[i][k+1] = fa[fa[i][k]][k];
}
}
for(int i = 0; i < m; i++){
int t; cin >> t;
int y = 0;
for(int j = 0; j < t; j++){
cin >> arr[j];
y = (j == 0 ? arr[j] : LCA(y, arr[j]));
}
rem[y].push_back(i);
for(int j = 0; j < t; j++) add[arr[j]].push_back(i);
}
solve(1, -1);
cout << ans.size() << endl;
for(int i : ans) cout << i + 1 << ' ';
cout << endl;
}
Compilation message
railway.cpp: In function 'void solve(long long int, long long int)':
railway.cpp:46:27: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
46 | if(vals[i].size() >= k) ans.insert(edge[node][i]);
| ~~~~~~~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
11 ms |
20132 KB |
Output is correct |
3 |
Correct |
11 ms |
20368 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
3 ms |
14940 KB |
Output is correct |
6 |
Correct |
12 ms |
21076 KB |
Output is correct |
7 |
Correct |
12 ms |
20316 KB |
Output is correct |
8 |
Correct |
11 ms |
20388 KB |
Output is correct |
9 |
Correct |
13 ms |
20312 KB |
Output is correct |
10 |
Correct |
3 ms |
14940 KB |
Output is correct |
11 |
Correct |
3 ms |
14996 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
14940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
11 ms |
20132 KB |
Output is correct |
3 |
Correct |
11 ms |
20368 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
3 ms |
14940 KB |
Output is correct |
6 |
Correct |
12 ms |
21076 KB |
Output is correct |
7 |
Correct |
12 ms |
20316 KB |
Output is correct |
8 |
Correct |
11 ms |
20388 KB |
Output is correct |
9 |
Correct |
13 ms |
20312 KB |
Output is correct |
10 |
Correct |
3 ms |
14940 KB |
Output is correct |
11 |
Correct |
3 ms |
14996 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
14940 KB |
Output is correct |
15 |
Correct |
33 ms |
24644 KB |
Output is correct |
16 |
Correct |
33 ms |
24912 KB |
Output is correct |
17 |
Correct |
39 ms |
25172 KB |
Output is correct |
18 |
Correct |
13 ms |
20896 KB |
Output is correct |
19 |
Correct |
12 ms |
20420 KB |
Output is correct |
20 |
Correct |
46 ms |
26960 KB |
Output is correct |
21 |
Correct |
44 ms |
26720 KB |
Output is correct |
22 |
Correct |
3 ms |
14940 KB |
Output is correct |
23 |
Correct |
11 ms |
20248 KB |
Output is correct |
24 |
Correct |
11 ms |
20060 KB |
Output is correct |
25 |
Correct |
3 ms |
14940 KB |
Output is correct |
26 |
Correct |
3 ms |
14940 KB |
Output is correct |
27 |
Correct |
13 ms |
20828 KB |
Output is correct |
28 |
Correct |
11 ms |
20316 KB |
Output is correct |
29 |
Correct |
10 ms |
20316 KB |
Output is correct |
30 |
Correct |
11 ms |
20328 KB |
Output is correct |
31 |
Correct |
3 ms |
14940 KB |
Output is correct |
32 |
Correct |
3 ms |
14940 KB |
Output is correct |
33 |
Correct |
4 ms |
15196 KB |
Output is correct |
34 |
Correct |
3 ms |
14936 KB |
Output is correct |
35 |
Correct |
3 ms |
14936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
182 ms |
83100 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
172 ms |
81852 KB |
Output is correct |
4 |
Correct |
166 ms |
79644 KB |
Output is correct |
5 |
Correct |
156 ms |
81880 KB |
Output is correct |
6 |
Correct |
168 ms |
82844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
183 ms |
74300 KB |
Output is correct |
2 |
Correct |
189 ms |
71360 KB |
Output is correct |
3 |
Correct |
203 ms |
76484 KB |
Output is correct |
4 |
Correct |
202 ms |
76576 KB |
Output is correct |
5 |
Correct |
252 ms |
77044 KB |
Output is correct |
6 |
Correct |
177 ms |
75004 KB |
Output is correct |
7 |
Correct |
183 ms |
74688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
183 ms |
74300 KB |
Output is correct |
2 |
Correct |
189 ms |
71360 KB |
Output is correct |
3 |
Correct |
203 ms |
76484 KB |
Output is correct |
4 |
Correct |
202 ms |
76576 KB |
Output is correct |
5 |
Correct |
252 ms |
77044 KB |
Output is correct |
6 |
Correct |
177 ms |
75004 KB |
Output is correct |
7 |
Correct |
183 ms |
74688 KB |
Output is correct |
8 |
Correct |
182 ms |
74484 KB |
Output is correct |
9 |
Correct |
183 ms |
74280 KB |
Output is correct |
10 |
Correct |
146 ms |
82220 KB |
Output is correct |
11 |
Correct |
147 ms |
81864 KB |
Output is correct |
12 |
Correct |
146 ms |
70672 KB |
Output is correct |
13 |
Correct |
147 ms |
70596 KB |
Output is correct |
14 |
Correct |
200 ms |
71772 KB |
Output is correct |
15 |
Correct |
189 ms |
71740 KB |
Output is correct |
16 |
Correct |
218 ms |
77880 KB |
Output is correct |
17 |
Correct |
218 ms |
78024 KB |
Output is correct |
18 |
Correct |
207 ms |
76044 KB |
Output is correct |
19 |
Correct |
197 ms |
71876 KB |
Output is correct |
20 |
Correct |
214 ms |
75588 KB |
Output is correct |
21 |
Correct |
188 ms |
76224 KB |
Output is correct |
22 |
Correct |
192 ms |
75960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
11 ms |
20132 KB |
Output is correct |
3 |
Correct |
11 ms |
20368 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
3 ms |
14940 KB |
Output is correct |
6 |
Correct |
12 ms |
21076 KB |
Output is correct |
7 |
Correct |
12 ms |
20316 KB |
Output is correct |
8 |
Correct |
11 ms |
20388 KB |
Output is correct |
9 |
Correct |
13 ms |
20312 KB |
Output is correct |
10 |
Correct |
3 ms |
14940 KB |
Output is correct |
11 |
Correct |
3 ms |
14996 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
14940 KB |
Output is correct |
15 |
Correct |
33 ms |
24644 KB |
Output is correct |
16 |
Correct |
33 ms |
24912 KB |
Output is correct |
17 |
Correct |
39 ms |
25172 KB |
Output is correct |
18 |
Correct |
13 ms |
20896 KB |
Output is correct |
19 |
Correct |
12 ms |
20420 KB |
Output is correct |
20 |
Correct |
46 ms |
26960 KB |
Output is correct |
21 |
Correct |
44 ms |
26720 KB |
Output is correct |
22 |
Correct |
3 ms |
14940 KB |
Output is correct |
23 |
Correct |
11 ms |
20248 KB |
Output is correct |
24 |
Correct |
11 ms |
20060 KB |
Output is correct |
25 |
Correct |
3 ms |
14940 KB |
Output is correct |
26 |
Correct |
3 ms |
14940 KB |
Output is correct |
27 |
Correct |
13 ms |
20828 KB |
Output is correct |
28 |
Correct |
11 ms |
20316 KB |
Output is correct |
29 |
Correct |
10 ms |
20316 KB |
Output is correct |
30 |
Correct |
11 ms |
20328 KB |
Output is correct |
31 |
Correct |
3 ms |
14940 KB |
Output is correct |
32 |
Correct |
3 ms |
14940 KB |
Output is correct |
33 |
Correct |
4 ms |
15196 KB |
Output is correct |
34 |
Correct |
3 ms |
14936 KB |
Output is correct |
35 |
Correct |
3 ms |
14936 KB |
Output is correct |
36 |
Correct |
182 ms |
83100 KB |
Output is correct |
37 |
Correct |
3 ms |
14940 KB |
Output is correct |
38 |
Correct |
172 ms |
81852 KB |
Output is correct |
39 |
Correct |
166 ms |
79644 KB |
Output is correct |
40 |
Correct |
156 ms |
81880 KB |
Output is correct |
41 |
Correct |
168 ms |
82844 KB |
Output is correct |
42 |
Correct |
183 ms |
74300 KB |
Output is correct |
43 |
Correct |
189 ms |
71360 KB |
Output is correct |
44 |
Correct |
203 ms |
76484 KB |
Output is correct |
45 |
Correct |
202 ms |
76576 KB |
Output is correct |
46 |
Correct |
252 ms |
77044 KB |
Output is correct |
47 |
Correct |
177 ms |
75004 KB |
Output is correct |
48 |
Correct |
183 ms |
74688 KB |
Output is correct |
49 |
Correct |
182 ms |
74484 KB |
Output is correct |
50 |
Correct |
183 ms |
74280 KB |
Output is correct |
51 |
Correct |
146 ms |
82220 KB |
Output is correct |
52 |
Correct |
147 ms |
81864 KB |
Output is correct |
53 |
Correct |
146 ms |
70672 KB |
Output is correct |
54 |
Correct |
147 ms |
70596 KB |
Output is correct |
55 |
Correct |
200 ms |
71772 KB |
Output is correct |
56 |
Correct |
189 ms |
71740 KB |
Output is correct |
57 |
Correct |
218 ms |
77880 KB |
Output is correct |
58 |
Correct |
218 ms |
78024 KB |
Output is correct |
59 |
Correct |
207 ms |
76044 KB |
Output is correct |
60 |
Correct |
197 ms |
71876 KB |
Output is correct |
61 |
Correct |
214 ms |
75588 KB |
Output is correct |
62 |
Correct |
188 ms |
76224 KB |
Output is correct |
63 |
Correct |
192 ms |
75960 KB |
Output is correct |
64 |
Correct |
191 ms |
75044 KB |
Output is correct |
65 |
Correct |
255 ms |
85064 KB |
Output is correct |
66 |
Correct |
235 ms |
80988 KB |
Output is correct |
67 |
Correct |
224 ms |
76228 KB |
Output is correct |
68 |
Correct |
126 ms |
68292 KB |
Output is correct |
69 |
Correct |
129 ms |
68432 KB |
Output is correct |
70 |
Correct |
225 ms |
77124 KB |
Output is correct |
71 |
Correct |
176 ms |
74180 KB |
Output is correct |
72 |
Correct |
3 ms |
14940 KB |
Output is correct |
73 |
Correct |
13 ms |
20060 KB |
Output is correct |
74 |
Correct |
11 ms |
20056 KB |
Output is correct |
75 |
Correct |
3 ms |
14940 KB |
Output is correct |
76 |
Correct |
3 ms |
14940 KB |
Output is correct |
77 |
Correct |
16 ms |
20892 KB |
Output is correct |
78 |
Correct |
12 ms |
20316 KB |
Output is correct |
79 |
Correct |
12 ms |
20316 KB |
Output is correct |
80 |
Correct |
12 ms |
20316 KB |
Output is correct |
81 |
Correct |
3 ms |
14936 KB |
Output is correct |
82 |
Correct |
3 ms |
14940 KB |
Output is correct |
83 |
Correct |
3 ms |
14940 KB |
Output is correct |
84 |
Correct |
3 ms |
14940 KB |
Output is correct |
85 |
Correct |
3 ms |
14996 KB |
Output is correct |
86 |
Correct |
33 ms |
24752 KB |
Output is correct |
87 |
Correct |
36 ms |
24964 KB |
Output is correct |
88 |
Correct |
35 ms |
25180 KB |
Output is correct |
89 |
Correct |
12 ms |
20828 KB |
Output is correct |
90 |
Correct |
12 ms |
20316 KB |
Output is correct |
91 |
Correct |
33 ms |
26944 KB |
Output is correct |
92 |
Correct |
33 ms |
26704 KB |
Output is correct |
93 |
Correct |
3 ms |
15192 KB |
Output is correct |
94 |
Correct |
185 ms |
83020 KB |
Output is correct |
95 |
Correct |
193 ms |
81796 KB |
Output is correct |
96 |
Correct |
143 ms |
79556 KB |
Output is correct |
97 |
Correct |
166 ms |
81864 KB |
Output is correct |
98 |
Correct |
168 ms |
82980 KB |
Output is correct |
99 |
Correct |
221 ms |
80332 KB |
Output is correct |
100 |
Correct |
216 ms |
77300 KB |
Output is correct |
101 |
Correct |
215 ms |
78020 KB |
Output is correct |
102 |
Correct |
192 ms |
71300 KB |
Output is correct |
103 |
Correct |
177 ms |
74696 KB |
Output is correct |
104 |
Correct |
189 ms |
76108 KB |
Output is correct |
105 |
Correct |
176 ms |
74436 KB |
Output is correct |
106 |
Correct |
199 ms |
75392 KB |
Output is correct |
107 |
Correct |
246 ms |
74752 KB |
Output is correct |
108 |
Correct |
146 ms |
82084 KB |
Output is correct |
109 |
Correct |
155 ms |
82244 KB |
Output is correct |
110 |
Correct |
149 ms |
70596 KB |
Output is correct |
111 |
Correct |
146 ms |
70576 KB |
Output is correct |
112 |
Correct |
195 ms |
71636 KB |
Output is correct |
113 |
Correct |
185 ms |
71616 KB |
Output is correct |