#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
const int mxN = 1e5;
int n,k;
vector<pii> adj[mxN];
int bj[mxN][20];
int first[mxN];
int pidx[mxN];
int ssize[mxN];
int res[mxN];
int cnt = 0;
void dfs(int node, int p){
bj[node][0] = p;
for (int i = 1; i < 20; i++){
if (bj[node][i-1] == -1){
break;
}
bj[node][i] = bj[bj[node][i-1]][i-1];
}
first[node] = cnt;
cnt++;
ssize[node] = 1;
// cout << node << " -" << p << '\n';
for (pii next : adj[node]){
if (next.f != p){
dfs(next.f,node);
ssize[node] += ssize[next.f];
} else {
pidx[node] = next.s;
}
}
}
bool contain(int a, int b){
if (first[a] <= first[b] && ssize[a] + first[a] > first[b]){
return true;
}
return false;
}
int glca(int a, int b){
if (a == -1){
return b;
}
while (!contain(a,b)){
for (int i = 1; i < 20; i++){
if (bj[a][i] == -1 || contain(bj[a][i],b)){
a = bj[a][i-1];
break;
}
}
}
return a;
}
bool segtree[4*mxN+1];
void upd(int t, bool v, int l = 0, int r = n-1, int idx = 0){
if (l > t || r < t){
return;
}
if (l == r){
segtree[idx] = v;
return;
}
int m = (l+r)/2;
upd(t,v,l,m,2*idx+1);
upd(t,v,m+1,r,2*idx+2);
segtree[idx] = (segtree[2*idx+1] || segtree[2*idx+2]);
}
bool query(int tl, int tr, int l = 0, int r = n-1, int idx = 0){
if (l > tr || r < tl){
return false;
}
if (l >= tl & r <= tr){
return segtree[idx];
}
int m = (l+r)/2;
return query(tl,tr,l,m,2*idx+1) || query(tl,tr,m+1,r,2*idx+2);
}
void addon(int a){
int next;
// cout << a << " : ";
while (!query(first[a],first[a]+ssize[a]-1)){
for (int i = 1; i < 20; i++){
next = bj[a][i];
if (next == -1 || query(first[next],first[next]+ssize[next]-1)){
a = bj[a][i-1];
break;
}
}
// cout << a << " ";
}
// cout << a << '\n';
res[a] -= 1;
}
vector<int> tot;
void solve(int node, int p){
for (pii next : adj[node]){
if (next.f != p){
solve(next.f,node);
res[node] += res[next.f];
}
}
if (res[node] >= k){
tot.pb(pidx[node]+1);
}
// cout << res[node] << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int m;
cin >> n >> m >> k;
int a,b;
for (int i =0; i < n-1; i++){
cin >> a >> b;
a -= 1;
b -= 1;
adj[a].pb({b,i});
adj[b].pb({a,i});
}
memset(res,0,sizeof(res));
memset(segtree,0,sizeof(segtree));
for (int i =0; i < mxN; i++) for (int j =0; j <20; j++) bj[i][j]=-1;
dfs(0,-1);
pidx[0] = -1;
int si,lca;
/* for (int i =0; i < n; i++) cout << first[i] << " ";
cout << '\n';
for (int i =0; i < n; i++) cout << ssize[i] << " ";
cout << '\n';*/
vector<int> all;
for (int i = 0; i < m; i++){
cin >> si;
lca = -1;
all.clear();
for (int j = 0; j < si; j++){
cin >> a;
a -= 1;
all.pb(a);
lca = glca(lca,a);
}
// cout << all[0] << '\n';
upd(first[all[0]],true);
res[all[0]]++;
res[lca]--;
for (int j = 1; j < all.size(); j++){
addon(all[j]);
res[all[j]]++;
upd(first[all[j]],true);
}
for (int j = 0; j < all.size(); j++){
upd(first[all[j]],false);
}
/* for (int j =0; j < n; j++){
cout << res[j] << " ";
}
cout << '\n';*/
}
solve(0,-1);
sort(tot.begin(),tot.end());
cout << (int) tot.size() << "\n";
for (int i : tot){
cout << i << " ";
}
cout << '\n';
return 0;
}
Compilation message
railway.cpp: In function 'bool query(int, int, int, int, int)':
railway.cpp:84:11: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
84 | if (l >= tl & r <= tr){
| ~~^~~~~
railway.cpp: In function 'int main()':
railway.cpp:165:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
165 | for (int j = 1; j < all.size(); j++){
| ~~^~~~~~~~~~~~
railway.cpp:170:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
170 | for (int j = 0; j < all.size(); j++){
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12376 KB |
Output is correct |
2 |
Correct |
7 ms |
12892 KB |
Output is correct |
3 |
Correct |
7 ms |
12936 KB |
Output is correct |
4 |
Correct |
3 ms |
12380 KB |
Output is correct |
5 |
Correct |
3 ms |
12380 KB |
Output is correct |
6 |
Correct |
11 ms |
13440 KB |
Output is correct |
7 |
Correct |
7 ms |
13112 KB |
Output is correct |
8 |
Correct |
5 ms |
12888 KB |
Output is correct |
9 |
Correct |
6 ms |
12884 KB |
Output is correct |
10 |
Correct |
2 ms |
12380 KB |
Output is correct |
11 |
Correct |
4 ms |
12400 KB |
Output is correct |
12 |
Correct |
3 ms |
12492 KB |
Output is correct |
13 |
Correct |
3 ms |
12380 KB |
Output is correct |
14 |
Correct |
3 ms |
12380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12376 KB |
Output is correct |
2 |
Correct |
7 ms |
12892 KB |
Output is correct |
3 |
Correct |
7 ms |
12936 KB |
Output is correct |
4 |
Correct |
3 ms |
12380 KB |
Output is correct |
5 |
Correct |
3 ms |
12380 KB |
Output is correct |
6 |
Correct |
11 ms |
13440 KB |
Output is correct |
7 |
Correct |
7 ms |
13112 KB |
Output is correct |
8 |
Correct |
5 ms |
12888 KB |
Output is correct |
9 |
Correct |
6 ms |
12884 KB |
Output is correct |
10 |
Correct |
2 ms |
12380 KB |
Output is correct |
11 |
Correct |
4 ms |
12400 KB |
Output is correct |
12 |
Correct |
3 ms |
12492 KB |
Output is correct |
13 |
Correct |
3 ms |
12380 KB |
Output is correct |
14 |
Correct |
3 ms |
12380 KB |
Output is correct |
15 |
Correct |
71 ms |
13408 KB |
Output is correct |
16 |
Correct |
65 ms |
13396 KB |
Output is correct |
17 |
Correct |
74 ms |
13412 KB |
Output is correct |
18 |
Correct |
14 ms |
13392 KB |
Output is correct |
19 |
Correct |
11 ms |
13148 KB |
Output is correct |
20 |
Correct |
52 ms |
13508 KB |
Output is correct |
21 |
Correct |
54 ms |
13404 KB |
Output is correct |
22 |
Correct |
2 ms |
12380 KB |
Output is correct |
23 |
Correct |
9 ms |
13148 KB |
Output is correct |
24 |
Correct |
6 ms |
12892 KB |
Output is correct |
25 |
Correct |
3 ms |
12380 KB |
Output is correct |
26 |
Correct |
3 ms |
12380 KB |
Output is correct |
27 |
Correct |
10 ms |
13404 KB |
Output is correct |
28 |
Correct |
8 ms |
13148 KB |
Output is correct |
29 |
Correct |
5 ms |
12892 KB |
Output is correct |
30 |
Correct |
6 ms |
12892 KB |
Output is correct |
31 |
Correct |
3 ms |
12632 KB |
Output is correct |
32 |
Correct |
2 ms |
12380 KB |
Output is correct |
33 |
Correct |
3 ms |
12464 KB |
Output is correct |
34 |
Correct |
3 ms |
12576 KB |
Output is correct |
35 |
Correct |
3 ms |
12380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
540 ms |
25916 KB |
Output is correct |
2 |
Correct |
3 ms |
12380 KB |
Output is correct |
3 |
Correct |
511 ms |
27444 KB |
Output is correct |
4 |
Correct |
515 ms |
26780 KB |
Output is correct |
5 |
Correct |
653 ms |
27564 KB |
Output is correct |
6 |
Correct |
358 ms |
28104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
527 ms |
20844 KB |
Output is correct |
2 |
Correct |
215 ms |
18516 KB |
Output is correct |
3 |
Correct |
119 ms |
18020 KB |
Output is correct |
4 |
Correct |
141 ms |
18004 KB |
Output is correct |
5 |
Correct |
133 ms |
17964 KB |
Output is correct |
6 |
Correct |
475 ms |
22644 KB |
Output is correct |
7 |
Correct |
539 ms |
22840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
527 ms |
20844 KB |
Output is correct |
2 |
Correct |
215 ms |
18516 KB |
Output is correct |
3 |
Correct |
119 ms |
18020 KB |
Output is correct |
4 |
Correct |
141 ms |
18004 KB |
Output is correct |
5 |
Correct |
133 ms |
17964 KB |
Output is correct |
6 |
Correct |
475 ms |
22644 KB |
Output is correct |
7 |
Correct |
539 ms |
22840 KB |
Output is correct |
8 |
Correct |
419 ms |
22608 KB |
Output is correct |
9 |
Correct |
424 ms |
22628 KB |
Output is correct |
10 |
Correct |
391 ms |
27852 KB |
Output is correct |
11 |
Correct |
410 ms |
27652 KB |
Output is correct |
12 |
Correct |
84 ms |
17748 KB |
Output is correct |
13 |
Correct |
87 ms |
17664 KB |
Output is correct |
14 |
Correct |
183 ms |
17964 KB |
Output is correct |
15 |
Correct |
148 ms |
17844 KB |
Output is correct |
16 |
Correct |
117 ms |
18004 KB |
Output is correct |
17 |
Correct |
149 ms |
18344 KB |
Output is correct |
18 |
Correct |
114 ms |
18088 KB |
Output is correct |
19 |
Correct |
205 ms |
18516 KB |
Output is correct |
20 |
Correct |
538 ms |
22916 KB |
Output is correct |
21 |
Correct |
630 ms |
23252 KB |
Output is correct |
22 |
Correct |
578 ms |
22888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12376 KB |
Output is correct |
2 |
Correct |
7 ms |
12892 KB |
Output is correct |
3 |
Correct |
7 ms |
12936 KB |
Output is correct |
4 |
Correct |
3 ms |
12380 KB |
Output is correct |
5 |
Correct |
3 ms |
12380 KB |
Output is correct |
6 |
Correct |
11 ms |
13440 KB |
Output is correct |
7 |
Correct |
7 ms |
13112 KB |
Output is correct |
8 |
Correct |
5 ms |
12888 KB |
Output is correct |
9 |
Correct |
6 ms |
12884 KB |
Output is correct |
10 |
Correct |
2 ms |
12380 KB |
Output is correct |
11 |
Correct |
4 ms |
12400 KB |
Output is correct |
12 |
Correct |
3 ms |
12492 KB |
Output is correct |
13 |
Correct |
3 ms |
12380 KB |
Output is correct |
14 |
Correct |
3 ms |
12380 KB |
Output is correct |
15 |
Correct |
71 ms |
13408 KB |
Output is correct |
16 |
Correct |
65 ms |
13396 KB |
Output is correct |
17 |
Correct |
74 ms |
13412 KB |
Output is correct |
18 |
Correct |
14 ms |
13392 KB |
Output is correct |
19 |
Correct |
11 ms |
13148 KB |
Output is correct |
20 |
Correct |
52 ms |
13508 KB |
Output is correct |
21 |
Correct |
54 ms |
13404 KB |
Output is correct |
22 |
Correct |
2 ms |
12380 KB |
Output is correct |
23 |
Correct |
9 ms |
13148 KB |
Output is correct |
24 |
Correct |
6 ms |
12892 KB |
Output is correct |
25 |
Correct |
3 ms |
12380 KB |
Output is correct |
26 |
Correct |
3 ms |
12380 KB |
Output is correct |
27 |
Correct |
10 ms |
13404 KB |
Output is correct |
28 |
Correct |
8 ms |
13148 KB |
Output is correct |
29 |
Correct |
5 ms |
12892 KB |
Output is correct |
30 |
Correct |
6 ms |
12892 KB |
Output is correct |
31 |
Correct |
3 ms |
12632 KB |
Output is correct |
32 |
Correct |
2 ms |
12380 KB |
Output is correct |
33 |
Correct |
3 ms |
12464 KB |
Output is correct |
34 |
Correct |
3 ms |
12576 KB |
Output is correct |
35 |
Correct |
3 ms |
12380 KB |
Output is correct |
36 |
Correct |
540 ms |
25916 KB |
Output is correct |
37 |
Correct |
3 ms |
12380 KB |
Output is correct |
38 |
Correct |
511 ms |
27444 KB |
Output is correct |
39 |
Correct |
515 ms |
26780 KB |
Output is correct |
40 |
Correct |
653 ms |
27564 KB |
Output is correct |
41 |
Correct |
358 ms |
28104 KB |
Output is correct |
42 |
Correct |
527 ms |
20844 KB |
Output is correct |
43 |
Correct |
215 ms |
18516 KB |
Output is correct |
44 |
Correct |
119 ms |
18020 KB |
Output is correct |
45 |
Correct |
141 ms |
18004 KB |
Output is correct |
46 |
Correct |
133 ms |
17964 KB |
Output is correct |
47 |
Correct |
475 ms |
22644 KB |
Output is correct |
48 |
Correct |
539 ms |
22840 KB |
Output is correct |
49 |
Correct |
419 ms |
22608 KB |
Output is correct |
50 |
Correct |
424 ms |
22628 KB |
Output is correct |
51 |
Correct |
391 ms |
27852 KB |
Output is correct |
52 |
Correct |
410 ms |
27652 KB |
Output is correct |
53 |
Correct |
84 ms |
17748 KB |
Output is correct |
54 |
Correct |
87 ms |
17664 KB |
Output is correct |
55 |
Correct |
183 ms |
17964 KB |
Output is correct |
56 |
Correct |
148 ms |
17844 KB |
Output is correct |
57 |
Correct |
117 ms |
18004 KB |
Output is correct |
58 |
Correct |
149 ms |
18344 KB |
Output is correct |
59 |
Correct |
114 ms |
18088 KB |
Output is correct |
60 |
Correct |
205 ms |
18516 KB |
Output is correct |
61 |
Correct |
538 ms |
22916 KB |
Output is correct |
62 |
Correct |
630 ms |
23252 KB |
Output is correct |
63 |
Correct |
578 ms |
22888 KB |
Output is correct |
64 |
Correct |
457 ms |
22884 KB |
Output is correct |
65 |
Correct |
158 ms |
18004 KB |
Output is correct |
66 |
Correct |
223 ms |
17848 KB |
Output is correct |
67 |
Correct |
159 ms |
18000 KB |
Output is correct |
68 |
Correct |
70 ms |
17808 KB |
Output is correct |
69 |
Correct |
71 ms |
17748 KB |
Output is correct |
70 |
Correct |
517 ms |
23296 KB |
Output is correct |
71 |
Correct |
417 ms |
22628 KB |
Output is correct |
72 |
Correct |
3 ms |
12380 KB |
Output is correct |
73 |
Correct |
6 ms |
12892 KB |
Output is correct |
74 |
Correct |
7 ms |
12892 KB |
Output is correct |
75 |
Correct |
3 ms |
12380 KB |
Output is correct |
76 |
Correct |
3 ms |
12376 KB |
Output is correct |
77 |
Correct |
11 ms |
13404 KB |
Output is correct |
78 |
Correct |
7 ms |
13100 KB |
Output is correct |
79 |
Correct |
5 ms |
13144 KB |
Output is correct |
80 |
Correct |
6 ms |
12892 KB |
Output is correct |
81 |
Correct |
3 ms |
12376 KB |
Output is correct |
82 |
Correct |
3 ms |
12380 KB |
Output is correct |
83 |
Correct |
3 ms |
12376 KB |
Output is correct |
84 |
Correct |
3 ms |
12380 KB |
Output is correct |
85 |
Correct |
2 ms |
12596 KB |
Output is correct |
86 |
Correct |
65 ms |
13396 KB |
Output is correct |
87 |
Correct |
66 ms |
13408 KB |
Output is correct |
88 |
Correct |
71 ms |
13396 KB |
Output is correct |
89 |
Correct |
14 ms |
13380 KB |
Output is correct |
90 |
Correct |
9 ms |
13148 KB |
Output is correct |
91 |
Correct |
52 ms |
13372 KB |
Output is correct |
92 |
Correct |
53 ms |
13396 KB |
Output is correct |
93 |
Correct |
3 ms |
12376 KB |
Output is correct |
94 |
Correct |
517 ms |
27684 KB |
Output is correct |
95 |
Correct |
503 ms |
27316 KB |
Output is correct |
96 |
Correct |
521 ms |
26860 KB |
Output is correct |
97 |
Correct |
648 ms |
27568 KB |
Output is correct |
98 |
Correct |
349 ms |
28104 KB |
Output is correct |
99 |
Correct |
126 ms |
18004 KB |
Output is correct |
100 |
Correct |
128 ms |
18000 KB |
Output is correct |
101 |
Correct |
129 ms |
17964 KB |
Output is correct |
102 |
Correct |
259 ms |
18580 KB |
Output is correct |
103 |
Correct |
503 ms |
22928 KB |
Output is correct |
104 |
Correct |
486 ms |
23132 KB |
Output is correct |
105 |
Correct |
461 ms |
22500 KB |
Output is correct |
106 |
Correct |
473 ms |
22868 KB |
Output is correct |
107 |
Correct |
425 ms |
22604 KB |
Output is correct |
108 |
Correct |
397 ms |
27824 KB |
Output is correct |
109 |
Correct |
414 ms |
27652 KB |
Output is correct |
110 |
Correct |
87 ms |
17672 KB |
Output is correct |
111 |
Correct |
104 ms |
18100 KB |
Output is correct |
112 |
Correct |
151 ms |
18000 KB |
Output is correct |
113 |
Correct |
161 ms |
17836 KB |
Output is correct |