#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("Ofast")
#define F first
#define S second
#define MT make_tuple
#define MP make_pair
#define SZ(a) ((int)(a).size())
#define PB push_back
#define LEFT(i) (2*(i))
#define RIGHT(i) (2*(i)+1)
#define PAR(i) ((i)/2)
#define ALL(a) (a).begin(), (a).end()
#define END(s) {cout << s;return;}
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
std::vector<std::vector<ii> > e,p;
std::vector<std::vector<int> > d;
std::vector<ii> so;
ll n, m, k;
int lgn=0, cnt=0;
void rek(int a, int f){
p[a][0].F=f;
so[a].F=cnt++;
for(auto x: e[a])
if(x.F!=f)
rek(x.F, a);
so[a].S=cnt++;
}
bool ancof(int a, int x){
if(a==-1 || x==-1)
return false;
return so[a].F<=so[x].F && so[x].S<=so[a].S;
}
int upd(int lca, int b){
// fprintf(stderr, "%d %d\n", lca, b);
for(int k=lgn-1; !ancof(lca,b); ) {
while(k>0 && (p[lca][k].F==-1 || ancof(p[lca][k].F, b)))
k--;
p[lca][k].S++;
lca=p[lca][k].F;
}
return lca;
}
int lca(int lca, int b){
for(int k=lgn-1; !ancof(lca,b); ) {
while(k>0 && (p[lca][k].F==-1 || ancof(p[lca][k].F, b)))
k--;
lca=p[lca][k].F;
}
return lca;
}
int main(){
scanf("%lld %lld %lld", &n, &m, &k);
while ((1<<lgn)<n)
lgn++;
p.resize(n);
for(int i=0; i<n; i++)
p[i].resize(lgn,{-1,0});
e.resize(n);
d.resize(m);
so.resize(n);
// fprintf(stderr,"%ld\n", clock());
for(int i=0; i<n-1; i++){
int a, b; scanf("%d %d", &a, &b);
a--; b--;
e[a].PB({b,i+1});
e[b].PB({a,i+1});
}
for(int i=0; i<m; i++){
int s; scanf("%d", &s);
d[i].resize(s);
for(int j=0; j<s; j++){
scanf("%d", &d[i][j]);
d[i][j]--;
}
}
// fprintf(stderr,"%ld\n", clock());
rek(0,-1);
// fprintf(stderr,"%ld\n", clock());
for(int j=1; j<lgn; j++)
for(int i=0; i<n; i++)
if(p[i][j-1].F!=-1)
p[i][j].F=p[p[i][j-1].F][j-1].F;
// fprintf(stderr,"%ld\n", clock());
for(int i=0; i<m; i++){
sort(ALL(d[i]),[&](int a, int b){
return so[a].F<so[b].F;
});
int s=SZ(d[i]);
std::vector<int> st;
st.PB(d[i][0]);
for(int j=1; j<s; j++){
if(ancof(st.back(),d[i][j])){
upd(d[i][j],st.back());
if(SZ(st)>1 && ancof(st[SZ(st)-2],st.back()))
st.pop_back();
} else{
int a=st.back();
st.pop_back();
if(!st.empty() && !ancof(st.back(),d[i][j])){
a=st.back();
st.pop_back();
}
if(st.empty())
st.PB(upd(a,d[i][j]));
upd(d[i][j],a);
}
st.PB(d[i][j]);
}
}
for(int j=lgn-1; j>0; j--)
for(int i=0; i<n; i++)
if(p[i][j].F!=-1){
p[i][j-1].S+=p[i][j].S;
p[p[i][j-1].F][j-1].S+=p[i][j].S;
}
std::vector<int> out;
for(int i=1; i<n; i++){
if(p[i][0].S>=k)
for(auto x: e[i])
if(x.F==p[i][0].F){
out.PB(x.S);
break;
}
}
sort(ALL(out));
printf("%d\n", SZ(out));
for(int i: out)
printf("%d ", i);
printf("\n");
}
Compilation message
railway.cpp: In function 'int main()':
railway.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld", &n, &m, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:78:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
railway.cpp:84:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int s; scanf("%d", &s);
~~~~~^~~~~~~~~~
railway.cpp:87:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &d[i][j]);
~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
12 ms |
3840 KB |
Output is correct |
3 |
Correct |
12 ms |
3840 KB |
Output is correct |
4 |
Correct |
4 ms |
256 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
14 ms |
4224 KB |
Output is correct |
7 |
Correct |
13 ms |
3840 KB |
Output is correct |
8 |
Correct |
12 ms |
3840 KB |
Output is correct |
9 |
Correct |
12 ms |
3840 KB |
Output is correct |
10 |
Correct |
5 ms |
256 KB |
Output is correct |
11 |
Correct |
4 ms |
256 KB |
Output is correct |
12 |
Correct |
5 ms |
256 KB |
Output is correct |
13 |
Correct |
5 ms |
256 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
12 ms |
3840 KB |
Output is correct |
3 |
Correct |
12 ms |
3840 KB |
Output is correct |
4 |
Correct |
4 ms |
256 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
14 ms |
4224 KB |
Output is correct |
7 |
Correct |
13 ms |
3840 KB |
Output is correct |
8 |
Correct |
12 ms |
3840 KB |
Output is correct |
9 |
Correct |
12 ms |
3840 KB |
Output is correct |
10 |
Correct |
5 ms |
256 KB |
Output is correct |
11 |
Correct |
4 ms |
256 KB |
Output is correct |
12 |
Correct |
5 ms |
256 KB |
Output is correct |
13 |
Correct |
5 ms |
256 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
34 ms |
4304 KB |
Output is correct |
16 |
Correct |
33 ms |
4264 KB |
Output is correct |
17 |
Correct |
32 ms |
4224 KB |
Output is correct |
18 |
Correct |
16 ms |
4224 KB |
Output is correct |
19 |
Correct |
13 ms |
3968 KB |
Output is correct |
20 |
Correct |
33 ms |
4348 KB |
Output is correct |
21 |
Correct |
33 ms |
4352 KB |
Output is correct |
22 |
Correct |
4 ms |
256 KB |
Output is correct |
23 |
Correct |
12 ms |
3840 KB |
Output is correct |
24 |
Correct |
13 ms |
3840 KB |
Output is correct |
25 |
Correct |
5 ms |
256 KB |
Output is correct |
26 |
Correct |
4 ms |
256 KB |
Output is correct |
27 |
Correct |
14 ms |
4224 KB |
Output is correct |
28 |
Correct |
13 ms |
3840 KB |
Output is correct |
29 |
Correct |
11 ms |
3840 KB |
Output is correct |
30 |
Correct |
13 ms |
3968 KB |
Output is correct |
31 |
Correct |
5 ms |
256 KB |
Output is correct |
32 |
Correct |
5 ms |
256 KB |
Output is correct |
33 |
Correct |
5 ms |
256 KB |
Output is correct |
34 |
Correct |
5 ms |
256 KB |
Output is correct |
35 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
334 ms |
47856 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
266 ms |
47500 KB |
Output is correct |
4 |
Correct |
270 ms |
46968 KB |
Output is correct |
5 |
Correct |
374 ms |
45684 KB |
Output is correct |
6 |
Correct |
230 ms |
45940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
180 ms |
45044 KB |
Output is correct |
2 |
Correct |
184 ms |
43256 KB |
Output is correct |
3 |
Correct |
171 ms |
43000 KB |
Output is correct |
4 |
Correct |
164 ms |
43000 KB |
Output is correct |
5 |
Correct |
174 ms |
43000 KB |
Output is correct |
6 |
Correct |
186 ms |
45560 KB |
Output is correct |
7 |
Correct |
186 ms |
45432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
180 ms |
45044 KB |
Output is correct |
2 |
Correct |
184 ms |
43256 KB |
Output is correct |
3 |
Correct |
171 ms |
43000 KB |
Output is correct |
4 |
Correct |
164 ms |
43000 KB |
Output is correct |
5 |
Correct |
174 ms |
43000 KB |
Output is correct |
6 |
Correct |
186 ms |
45560 KB |
Output is correct |
7 |
Correct |
186 ms |
45432 KB |
Output is correct |
8 |
Correct |
227 ms |
44408 KB |
Output is correct |
9 |
Correct |
210 ms |
45688 KB |
Output is correct |
10 |
Correct |
236 ms |
47476 KB |
Output is correct |
11 |
Correct |
242 ms |
47348 KB |
Output is correct |
12 |
Correct |
150 ms |
41204 KB |
Output is correct |
13 |
Correct |
137 ms |
41204 KB |
Output is correct |
14 |
Correct |
155 ms |
42232 KB |
Output is correct |
15 |
Correct |
198 ms |
42236 KB |
Output is correct |
16 |
Correct |
184 ms |
44536 KB |
Output is correct |
17 |
Correct |
164 ms |
44408 KB |
Output is correct |
18 |
Correct |
188 ms |
44408 KB |
Output is correct |
19 |
Correct |
186 ms |
44664 KB |
Output is correct |
20 |
Correct |
189 ms |
47096 KB |
Output is correct |
21 |
Correct |
193 ms |
47244 KB |
Output is correct |
22 |
Correct |
188 ms |
47224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
12 ms |
3840 KB |
Output is correct |
3 |
Correct |
12 ms |
3840 KB |
Output is correct |
4 |
Correct |
4 ms |
256 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
14 ms |
4224 KB |
Output is correct |
7 |
Correct |
13 ms |
3840 KB |
Output is correct |
8 |
Correct |
12 ms |
3840 KB |
Output is correct |
9 |
Correct |
12 ms |
3840 KB |
Output is correct |
10 |
Correct |
5 ms |
256 KB |
Output is correct |
11 |
Correct |
4 ms |
256 KB |
Output is correct |
12 |
Correct |
5 ms |
256 KB |
Output is correct |
13 |
Correct |
5 ms |
256 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
34 ms |
4304 KB |
Output is correct |
16 |
Correct |
33 ms |
4264 KB |
Output is correct |
17 |
Correct |
32 ms |
4224 KB |
Output is correct |
18 |
Correct |
16 ms |
4224 KB |
Output is correct |
19 |
Correct |
13 ms |
3968 KB |
Output is correct |
20 |
Correct |
33 ms |
4348 KB |
Output is correct |
21 |
Correct |
33 ms |
4352 KB |
Output is correct |
22 |
Correct |
4 ms |
256 KB |
Output is correct |
23 |
Correct |
12 ms |
3840 KB |
Output is correct |
24 |
Correct |
13 ms |
3840 KB |
Output is correct |
25 |
Correct |
5 ms |
256 KB |
Output is correct |
26 |
Correct |
4 ms |
256 KB |
Output is correct |
27 |
Correct |
14 ms |
4224 KB |
Output is correct |
28 |
Correct |
13 ms |
3840 KB |
Output is correct |
29 |
Correct |
11 ms |
3840 KB |
Output is correct |
30 |
Correct |
13 ms |
3968 KB |
Output is correct |
31 |
Correct |
5 ms |
256 KB |
Output is correct |
32 |
Correct |
5 ms |
256 KB |
Output is correct |
33 |
Correct |
5 ms |
256 KB |
Output is correct |
34 |
Correct |
5 ms |
256 KB |
Output is correct |
35 |
Correct |
5 ms |
384 KB |
Output is correct |
36 |
Correct |
334 ms |
47856 KB |
Output is correct |
37 |
Correct |
5 ms |
384 KB |
Output is correct |
38 |
Correct |
266 ms |
47500 KB |
Output is correct |
39 |
Correct |
270 ms |
46968 KB |
Output is correct |
40 |
Correct |
374 ms |
45684 KB |
Output is correct |
41 |
Correct |
230 ms |
45940 KB |
Output is correct |
42 |
Correct |
180 ms |
45044 KB |
Output is correct |
43 |
Correct |
184 ms |
43256 KB |
Output is correct |
44 |
Correct |
171 ms |
43000 KB |
Output is correct |
45 |
Correct |
164 ms |
43000 KB |
Output is correct |
46 |
Correct |
174 ms |
43000 KB |
Output is correct |
47 |
Correct |
186 ms |
45560 KB |
Output is correct |
48 |
Correct |
186 ms |
45432 KB |
Output is correct |
49 |
Correct |
227 ms |
44408 KB |
Output is correct |
50 |
Correct |
210 ms |
45688 KB |
Output is correct |
51 |
Correct |
236 ms |
47476 KB |
Output is correct |
52 |
Correct |
242 ms |
47348 KB |
Output is correct |
53 |
Correct |
150 ms |
41204 KB |
Output is correct |
54 |
Correct |
137 ms |
41204 KB |
Output is correct |
55 |
Correct |
155 ms |
42232 KB |
Output is correct |
56 |
Correct |
198 ms |
42236 KB |
Output is correct |
57 |
Correct |
184 ms |
44536 KB |
Output is correct |
58 |
Correct |
164 ms |
44408 KB |
Output is correct |
59 |
Correct |
188 ms |
44408 KB |
Output is correct |
60 |
Correct |
186 ms |
44664 KB |
Output is correct |
61 |
Correct |
189 ms |
47096 KB |
Output is correct |
62 |
Correct |
193 ms |
47244 KB |
Output is correct |
63 |
Correct |
188 ms |
47224 KB |
Output is correct |
64 |
Correct |
247 ms |
47096 KB |
Output is correct |
65 |
Correct |
232 ms |
44408 KB |
Output is correct |
66 |
Correct |
193 ms |
42232 KB |
Output is correct |
67 |
Correct |
192 ms |
42232 KB |
Output is correct |
68 |
Correct |
160 ms |
41080 KB |
Output is correct |
69 |
Correct |
132 ms |
41208 KB |
Output is correct |
70 |
Correct |
214 ms |
47348 KB |
Output is correct |
71 |
Correct |
218 ms |
45688 KB |
Output is correct |
72 |
Correct |
5 ms |
384 KB |
Output is correct |
73 |
Correct |
14 ms |
3968 KB |
Output is correct |
74 |
Correct |
12 ms |
3968 KB |
Output is correct |
75 |
Correct |
5 ms |
384 KB |
Output is correct |
76 |
Correct |
5 ms |
256 KB |
Output is correct |
77 |
Correct |
14 ms |
4224 KB |
Output is correct |
78 |
Correct |
14 ms |
3968 KB |
Output is correct |
79 |
Correct |
11 ms |
3968 KB |
Output is correct |
80 |
Correct |
13 ms |
3968 KB |
Output is correct |
81 |
Correct |
5 ms |
256 KB |
Output is correct |
82 |
Correct |
5 ms |
256 KB |
Output is correct |
83 |
Correct |
5 ms |
384 KB |
Output is correct |
84 |
Correct |
5 ms |
256 KB |
Output is correct |
85 |
Correct |
5 ms |
384 KB |
Output is correct |
86 |
Correct |
32 ms |
4608 KB |
Output is correct |
87 |
Correct |
37 ms |
4728 KB |
Output is correct |
88 |
Correct |
33 ms |
4728 KB |
Output is correct |
89 |
Correct |
15 ms |
4352 KB |
Output is correct |
90 |
Correct |
13 ms |
3968 KB |
Output is correct |
91 |
Correct |
32 ms |
4852 KB |
Output is correct |
92 |
Correct |
33 ms |
4736 KB |
Output is correct |
93 |
Correct |
5 ms |
384 KB |
Output is correct |
94 |
Correct |
264 ms |
49720 KB |
Output is correct |
95 |
Correct |
259 ms |
49268 KB |
Output is correct |
96 |
Correct |
257 ms |
48760 KB |
Output is correct |
97 |
Correct |
332 ms |
47604 KB |
Output is correct |
98 |
Correct |
230 ms |
47860 KB |
Output is correct |
99 |
Correct |
171 ms |
44408 KB |
Output is correct |
100 |
Correct |
187 ms |
44536 KB |
Output is correct |
101 |
Correct |
170 ms |
44408 KB |
Output is correct |
102 |
Correct |
185 ms |
44664 KB |
Output is correct |
103 |
Correct |
183 ms |
46840 KB |
Output is correct |
104 |
Correct |
186 ms |
47220 KB |
Output is correct |
105 |
Correct |
202 ms |
46840 KB |
Output is correct |
106 |
Correct |
210 ms |
45944 KB |
Output is correct |
107 |
Correct |
222 ms |
45688 KB |
Output is correct |
108 |
Correct |
255 ms |
47348 KB |
Output is correct |
109 |
Correct |
257 ms |
47476 KB |
Output is correct |
110 |
Correct |
146 ms |
41460 KB |
Output is correct |
111 |
Correct |
144 ms |
41204 KB |
Output is correct |
112 |
Correct |
186 ms |
42232 KB |
Output is correct |
113 |
Correct |
156 ms |
42232 KB |
Output is correct |