#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cerr<<vars<<" = ";
string delim="";
(...,(cerr<<delim<<values,delim=", "));
cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif
#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mxN=1e5+5,mxL=20; //make sure this is right
const int mod=1e9+7;
vector<pii> graph[mxN];
vector<int> vt[mxN];
int sum[mxN],st[mxN],en[mxN],up[mxN][mxL],cur,ht[mxN];
vector<int> ans;
void dfs(int at,int p){
up[at][0]=~p?p:at;
for(int i=1;i<mxL;i++)
up[at][i]=up[up[at][i-1]][i-1];
st[at]=++cur;
for(auto &[i,e]:graph[at]){
if(i==p)
continue;
ht[i]=ht[at]+1;
dfs(i,at);
}
en[at]=++cur;
}
int jump(int a,int k){
for(int i=0;i<mxL;i++){
if(k&(1<<i))
a=up[a][i];
}
return a;
}
int lca(int a,int b){
if(ht[a]>ht[b])
swap(a,b);
b=jump(b,ht[b]-ht[a]);
if(a==b)
return a;
for(int i=19;i>=0;i--){
if(up[a][i]!=up[b][i]){
a=up[a][i];
b=up[b][i];
}
}
return up[a][0];
}
bool is_anc(int a,int b){return st[a]<=st[b] && en[a]>=en[b];}
void solve(int at,int p){
for(int &i:vt[at])
solve(i,at);
if(~p)
sum[at]++;
sum[at]-=sz(vt[at]);
}
void build(vector<int> &a){
sort(a.begin(),a.end(),[&](auto x,auto y){return st[x]<st[y];});
int k=sz(a);
for(int i=0;i<k-1;i++)
a.pb(lca(a[i],a[i+1]));
sort(a.begin(),a.end(),[&](auto x,auto y){return st[x]<st[y];});
a.resize(unique(a.begin(),a.end())-a.begin());
for(int &i:a)
vt[i].clear();
stack<int> stk; stk.push(a[0]);
for(int i=1;i<sz(a);i++){
while(sz(stk)>1 && !is_anc(stk.top(),a[i])){
int p=stk.top(); stk.pop();
vt[stk.top()].pb(p);
}
stk.push(a[i]);
}
while(sz(stk)>1){
int p=stk.top(); stk.pop();
vt[stk.top()].pb(p);
}
solve(stk.top(),-1);
}
void ps(int at,int p,int k){
for(auto &[i,e]:graph[at]){
if(i==p)
continue;
ps(i,at,k);
if(sum[i]>=k)
ans.pb(e);
sum[at]+=sum[i];
}
deb(at,sum[at]);
}
int main(){
cin.sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n,m,k; cin>>n>>m>>k;
for(int i=1;i<n;i++){
int a,b; cin>>a>>b;
graph[a].pb({b,i});
graph[b].pb({a,i});
}
dfs(1,-1);
for(int i=0;i<m;i++){
int s; cin>>s;
vector<int> a;
for(int j=0;j<s;j++){
int x; cin>>x;
a.pb(x);
}
build(a);
}
ps(1,-1,k);
cout<<sz(ans)<<"\n";
sort(ans.begin(),ans.end());
for(int i=0;i<sz(ans);i++)
cout<<ans[i]<<" \n"[i==sz(ans)-1];
}
Compilation message
railway.cpp: In function 'void dfs(int, int)':
railway.cpp:42:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
42 | for(auto &[i,e]:graph[at]){
| ^
railway.cpp: In function 'void ps(int, int, int)':
railway.cpp:109:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
109 | for(auto &[i,e]:graph[at]){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
9 ms |
6348 KB |
Output is correct |
3 |
Correct |
9 ms |
6440 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
9 ms |
6952 KB |
Output is correct |
7 |
Correct |
9 ms |
6568 KB |
Output is correct |
8 |
Correct |
8 ms |
6476 KB |
Output is correct |
9 |
Correct |
8 ms |
6476 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
4 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
3 ms |
4956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
9 ms |
6348 KB |
Output is correct |
3 |
Correct |
9 ms |
6440 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
9 ms |
6952 KB |
Output is correct |
7 |
Correct |
9 ms |
6568 KB |
Output is correct |
8 |
Correct |
8 ms |
6476 KB |
Output is correct |
9 |
Correct |
8 ms |
6476 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
4 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
3 ms |
4956 KB |
Output is correct |
15 |
Correct |
39 ms |
6904 KB |
Output is correct |
16 |
Correct |
39 ms |
6884 KB |
Output is correct |
17 |
Correct |
40 ms |
7000 KB |
Output is correct |
18 |
Correct |
10 ms |
6860 KB |
Output is correct |
19 |
Correct |
9 ms |
6476 KB |
Output is correct |
20 |
Correct |
32 ms |
6892 KB |
Output is correct |
21 |
Correct |
34 ms |
6888 KB |
Output is correct |
22 |
Correct |
3 ms |
4940 KB |
Output is correct |
23 |
Correct |
9 ms |
6396 KB |
Output is correct |
24 |
Correct |
9 ms |
6436 KB |
Output is correct |
25 |
Correct |
3 ms |
5020 KB |
Output is correct |
26 |
Correct |
3 ms |
5020 KB |
Output is correct |
27 |
Correct |
10 ms |
6860 KB |
Output is correct |
28 |
Correct |
9 ms |
6476 KB |
Output is correct |
29 |
Correct |
8 ms |
6436 KB |
Output is correct |
30 |
Correct |
10 ms |
6476 KB |
Output is correct |
31 |
Correct |
3 ms |
4940 KB |
Output is correct |
32 |
Correct |
3 ms |
4940 KB |
Output is correct |
33 |
Correct |
3 ms |
4940 KB |
Output is correct |
34 |
Correct |
3 ms |
4940 KB |
Output is correct |
35 |
Correct |
3 ms |
5028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
127 ms |
27324 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
123 ms |
28828 KB |
Output is correct |
4 |
Correct |
124 ms |
28240 KB |
Output is correct |
5 |
Correct |
146 ms |
29884 KB |
Output is correct |
6 |
Correct |
125 ms |
29672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
97 ms |
21836 KB |
Output is correct |
2 |
Correct |
112 ms |
20216 KB |
Output is correct |
3 |
Correct |
122 ms |
19904 KB |
Output is correct |
4 |
Correct |
117 ms |
19900 KB |
Output is correct |
5 |
Correct |
117 ms |
19880 KB |
Output is correct |
6 |
Correct |
96 ms |
23924 KB |
Output is correct |
7 |
Correct |
102 ms |
23712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
97 ms |
21836 KB |
Output is correct |
2 |
Correct |
112 ms |
20216 KB |
Output is correct |
3 |
Correct |
122 ms |
19904 KB |
Output is correct |
4 |
Correct |
117 ms |
19900 KB |
Output is correct |
5 |
Correct |
117 ms |
19880 KB |
Output is correct |
6 |
Correct |
96 ms |
23924 KB |
Output is correct |
7 |
Correct |
102 ms |
23712 KB |
Output is correct |
8 |
Correct |
120 ms |
24692 KB |
Output is correct |
9 |
Correct |
120 ms |
24668 KB |
Output is correct |
10 |
Correct |
127 ms |
30012 KB |
Output is correct |
11 |
Correct |
126 ms |
29972 KB |
Output is correct |
12 |
Correct |
91 ms |
19648 KB |
Output is correct |
13 |
Correct |
90 ms |
19652 KB |
Output is correct |
14 |
Correct |
112 ms |
19776 KB |
Output is correct |
15 |
Correct |
112 ms |
19788 KB |
Output is correct |
16 |
Correct |
115 ms |
19908 KB |
Output is correct |
17 |
Correct |
117 ms |
19924 KB |
Output is correct |
18 |
Correct |
113 ms |
19904 KB |
Output is correct |
19 |
Correct |
108 ms |
20228 KB |
Output is correct |
20 |
Correct |
101 ms |
24052 KB |
Output is correct |
21 |
Correct |
104 ms |
24128 KB |
Output is correct |
22 |
Correct |
98 ms |
24096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
9 ms |
6348 KB |
Output is correct |
3 |
Correct |
9 ms |
6440 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
9 ms |
6952 KB |
Output is correct |
7 |
Correct |
9 ms |
6568 KB |
Output is correct |
8 |
Correct |
8 ms |
6476 KB |
Output is correct |
9 |
Correct |
8 ms |
6476 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
4 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
3 ms |
4956 KB |
Output is correct |
15 |
Correct |
39 ms |
6904 KB |
Output is correct |
16 |
Correct |
39 ms |
6884 KB |
Output is correct |
17 |
Correct |
40 ms |
7000 KB |
Output is correct |
18 |
Correct |
10 ms |
6860 KB |
Output is correct |
19 |
Correct |
9 ms |
6476 KB |
Output is correct |
20 |
Correct |
32 ms |
6892 KB |
Output is correct |
21 |
Correct |
34 ms |
6888 KB |
Output is correct |
22 |
Correct |
3 ms |
4940 KB |
Output is correct |
23 |
Correct |
9 ms |
6396 KB |
Output is correct |
24 |
Correct |
9 ms |
6436 KB |
Output is correct |
25 |
Correct |
3 ms |
5020 KB |
Output is correct |
26 |
Correct |
3 ms |
5020 KB |
Output is correct |
27 |
Correct |
10 ms |
6860 KB |
Output is correct |
28 |
Correct |
9 ms |
6476 KB |
Output is correct |
29 |
Correct |
8 ms |
6436 KB |
Output is correct |
30 |
Correct |
10 ms |
6476 KB |
Output is correct |
31 |
Correct |
3 ms |
4940 KB |
Output is correct |
32 |
Correct |
3 ms |
4940 KB |
Output is correct |
33 |
Correct |
3 ms |
4940 KB |
Output is correct |
34 |
Correct |
3 ms |
4940 KB |
Output is correct |
35 |
Correct |
3 ms |
5028 KB |
Output is correct |
36 |
Correct |
127 ms |
27324 KB |
Output is correct |
37 |
Correct |
3 ms |
4940 KB |
Output is correct |
38 |
Correct |
123 ms |
28828 KB |
Output is correct |
39 |
Correct |
124 ms |
28240 KB |
Output is correct |
40 |
Correct |
146 ms |
29884 KB |
Output is correct |
41 |
Correct |
125 ms |
29672 KB |
Output is correct |
42 |
Correct |
97 ms |
21836 KB |
Output is correct |
43 |
Correct |
112 ms |
20216 KB |
Output is correct |
44 |
Correct |
122 ms |
19904 KB |
Output is correct |
45 |
Correct |
117 ms |
19900 KB |
Output is correct |
46 |
Correct |
117 ms |
19880 KB |
Output is correct |
47 |
Correct |
96 ms |
23924 KB |
Output is correct |
48 |
Correct |
102 ms |
23712 KB |
Output is correct |
49 |
Correct |
120 ms |
24692 KB |
Output is correct |
50 |
Correct |
120 ms |
24668 KB |
Output is correct |
51 |
Correct |
127 ms |
30012 KB |
Output is correct |
52 |
Correct |
126 ms |
29972 KB |
Output is correct |
53 |
Correct |
91 ms |
19648 KB |
Output is correct |
54 |
Correct |
90 ms |
19652 KB |
Output is correct |
55 |
Correct |
112 ms |
19776 KB |
Output is correct |
56 |
Correct |
112 ms |
19788 KB |
Output is correct |
57 |
Correct |
115 ms |
19908 KB |
Output is correct |
58 |
Correct |
117 ms |
19924 KB |
Output is correct |
59 |
Correct |
113 ms |
19904 KB |
Output is correct |
60 |
Correct |
108 ms |
20228 KB |
Output is correct |
61 |
Correct |
101 ms |
24052 KB |
Output is correct |
62 |
Correct |
104 ms |
24128 KB |
Output is correct |
63 |
Correct |
98 ms |
24096 KB |
Output is correct |
64 |
Correct |
108 ms |
24440 KB |
Output is correct |
65 |
Correct |
124 ms |
19916 KB |
Output is correct |
66 |
Correct |
143 ms |
19816 KB |
Output is correct |
67 |
Correct |
134 ms |
19940 KB |
Output is correct |
68 |
Correct |
84 ms |
19620 KB |
Output is correct |
69 |
Correct |
87 ms |
19524 KB |
Output is correct |
70 |
Correct |
113 ms |
24616 KB |
Output is correct |
71 |
Correct |
146 ms |
24520 KB |
Output is correct |
72 |
Correct |
3 ms |
4940 KB |
Output is correct |
73 |
Correct |
9 ms |
6440 KB |
Output is correct |
74 |
Correct |
9 ms |
6348 KB |
Output is correct |
75 |
Correct |
3 ms |
5016 KB |
Output is correct |
76 |
Correct |
3 ms |
4940 KB |
Output is correct |
77 |
Correct |
9 ms |
6952 KB |
Output is correct |
78 |
Correct |
9 ms |
6476 KB |
Output is correct |
79 |
Correct |
8 ms |
6348 KB |
Output is correct |
80 |
Correct |
8 ms |
6476 KB |
Output is correct |
81 |
Correct |
3 ms |
4940 KB |
Output is correct |
82 |
Correct |
3 ms |
4940 KB |
Output is correct |
83 |
Correct |
3 ms |
4940 KB |
Output is correct |
84 |
Correct |
3 ms |
4940 KB |
Output is correct |
85 |
Correct |
3 ms |
5016 KB |
Output is correct |
86 |
Correct |
39 ms |
6936 KB |
Output is correct |
87 |
Correct |
42 ms |
7020 KB |
Output is correct |
88 |
Correct |
39 ms |
7028 KB |
Output is correct |
89 |
Correct |
9 ms |
6908 KB |
Output is correct |
90 |
Correct |
9 ms |
6564 KB |
Output is correct |
91 |
Correct |
31 ms |
6988 KB |
Output is correct |
92 |
Correct |
35 ms |
6892 KB |
Output is correct |
93 |
Correct |
3 ms |
5024 KB |
Output is correct |
94 |
Correct |
126 ms |
29184 KB |
Output is correct |
95 |
Correct |
126 ms |
28784 KB |
Output is correct |
96 |
Correct |
117 ms |
28200 KB |
Output is correct |
97 |
Correct |
142 ms |
29864 KB |
Output is correct |
98 |
Correct |
122 ms |
29656 KB |
Output is correct |
99 |
Correct |
114 ms |
19908 KB |
Output is correct |
100 |
Correct |
118 ms |
19996 KB |
Output is correct |
101 |
Correct |
111 ms |
19916 KB |
Output is correct |
102 |
Correct |
106 ms |
20220 KB |
Output is correct |
103 |
Correct |
94 ms |
23764 KB |
Output is correct |
104 |
Correct |
107 ms |
24128 KB |
Output is correct |
105 |
Correct |
94 ms |
23800 KB |
Output is correct |
106 |
Correct |
131 ms |
24832 KB |
Output is correct |
107 |
Correct |
121 ms |
24668 KB |
Output is correct |
108 |
Correct |
132 ms |
29884 KB |
Output is correct |
109 |
Correct |
123 ms |
29880 KB |
Output is correct |
110 |
Correct |
90 ms |
19652 KB |
Output is correct |
111 |
Correct |
93 ms |
19660 KB |
Output is correct |
112 |
Correct |
112 ms |
19780 KB |
Output is correct |
113 |
Correct |
123 ms |
19828 KB |
Output is correct |