#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
const int maxn = 1e5+10;
int n, m, k;
vector<pair<int,int>> g[maxn];
set<int> nodes[maxn];
const int LOG = 19;
int par[LOG+1][maxn];
int dep[maxn];
int lca(int u, int v) {
if (dep[u]<dep[v]) swap(u,v);
int dx = dep[u]-dep[v];
for (int j=0; j<LOG; j++) {
if (dx>>j&1) {
u = par[j][u];
}
}
if (u==v) return v;
for (int j=LOG-1; j>=0; j--) {
if (par[j][u] != par[j][v]) {
u = par[j][u];
v = par[j][v];
}
}
return par[0][u];
}
int tin[maxn];
int tout[maxn];
int cloc = 1;
void dfs(int at, int p) {
for (int j=1; j<LOG; j++) {
par[j][at] = par[j-1][par[j-1][at]];
}
tin[at] = cloc++;
for (auto ed: g[at]) {
int to = ed.second;
if (to == p) continue;
dep[to]=1+dep[at];
par[0][to] = at;
dfs(to, at);
}
tout[at] = cloc++;
}
vector<int> add[maxn], sub[maxn];
vector<int> ans;
set<int> dfs2(int at, int p, int edId=0) {
set<int> res;
for (auto ed: g[at]) {
int idx = ed.first;
int to = ed.second;
if (to==p) continue;
auto ret = dfs2(to, at, idx);
if (res.size() < ret.size()) {
swap(res, ret);
}
res.insert(ret.begin(), ret.end());
}
for (int x: add[at]) {
res.insert(x);
}
for (int x: sub[at]) {
res.erase(x);
}
if ((int)res.size() >= k && edId!=0) ans.push_back(edId);
return res;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>m>>k;
for (int i=1; i<n; i++) {
int u,v; cin>>u>>v;
g[u].push_back({i,v});
g[v].push_back({i,u});
}
for (int i=1; i<=m; i++) {
int t;
cin>>t;
while (t--) {
int x;
cin>>x;
nodes[i].insert(x);
}
}
dfs(1,0);
for (int i=1; i<=m; i++) {
int top = *nodes[i].begin();
for (int x: nodes[i]) {
add[x].push_back(i);
top = lca(top, x);
}
sub[top].push_back(i);
}
dfs2(1,0);
cout<<ans.size()<<endl;
sort(ans.begin(),ans.end());
for (int i: ans) cout<<i<<" ";
cout<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12140 KB |
Output is correct |
2 |
Correct |
16 ms |
13676 KB |
Output is correct |
3 |
Correct |
15 ms |
13676 KB |
Output is correct |
4 |
Correct |
9 ms |
12140 KB |
Output is correct |
5 |
Correct |
9 ms |
12140 KB |
Output is correct |
6 |
Correct |
16 ms |
14572 KB |
Output is correct |
7 |
Correct |
15 ms |
13804 KB |
Output is correct |
8 |
Correct |
17 ms |
13804 KB |
Output is correct |
9 |
Correct |
15 ms |
13804 KB |
Output is correct |
10 |
Correct |
8 ms |
12140 KB |
Output is correct |
11 |
Correct |
8 ms |
12140 KB |
Output is correct |
12 |
Correct |
8 ms |
12140 KB |
Output is correct |
13 |
Correct |
8 ms |
12140 KB |
Output is correct |
14 |
Correct |
9 ms |
12140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12140 KB |
Output is correct |
2 |
Correct |
16 ms |
13676 KB |
Output is correct |
3 |
Correct |
15 ms |
13676 KB |
Output is correct |
4 |
Correct |
9 ms |
12140 KB |
Output is correct |
5 |
Correct |
9 ms |
12140 KB |
Output is correct |
6 |
Correct |
16 ms |
14572 KB |
Output is correct |
7 |
Correct |
15 ms |
13804 KB |
Output is correct |
8 |
Correct |
17 ms |
13804 KB |
Output is correct |
9 |
Correct |
15 ms |
13804 KB |
Output is correct |
10 |
Correct |
8 ms |
12140 KB |
Output is correct |
11 |
Correct |
8 ms |
12140 KB |
Output is correct |
12 |
Correct |
8 ms |
12140 KB |
Output is correct |
13 |
Correct |
8 ms |
12140 KB |
Output is correct |
14 |
Correct |
9 ms |
12140 KB |
Output is correct |
15 |
Correct |
54 ms |
18284 KB |
Output is correct |
16 |
Correct |
54 ms |
18284 KB |
Output is correct |
17 |
Correct |
55 ms |
18284 KB |
Output is correct |
18 |
Correct |
17 ms |
14700 KB |
Output is correct |
19 |
Correct |
15 ms |
13932 KB |
Output is correct |
20 |
Correct |
61 ms |
19564 KB |
Output is correct |
21 |
Correct |
61 ms |
19564 KB |
Output is correct |
22 |
Correct |
8 ms |
12140 KB |
Output is correct |
23 |
Correct |
14 ms |
13676 KB |
Output is correct |
24 |
Correct |
15 ms |
13676 KB |
Output is correct |
25 |
Correct |
8 ms |
12140 KB |
Output is correct |
26 |
Correct |
8 ms |
12140 KB |
Output is correct |
27 |
Correct |
16 ms |
14572 KB |
Output is correct |
28 |
Correct |
15 ms |
13804 KB |
Output is correct |
29 |
Correct |
14 ms |
13824 KB |
Output is correct |
30 |
Correct |
16 ms |
13676 KB |
Output is correct |
31 |
Correct |
8 ms |
12140 KB |
Output is correct |
32 |
Correct |
8 ms |
12140 KB |
Output is correct |
33 |
Correct |
8 ms |
12140 KB |
Output is correct |
34 |
Correct |
9 ms |
12140 KB |
Output is correct |
35 |
Correct |
8 ms |
12140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
210 ms |
50864 KB |
Output is correct |
2 |
Correct |
8 ms |
12140 KB |
Output is correct |
3 |
Correct |
208 ms |
52456 KB |
Output is correct |
4 |
Correct |
196 ms |
51948 KB |
Output is correct |
5 |
Correct |
187 ms |
50916 KB |
Output is correct |
6 |
Correct |
164 ms |
53228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
144 ms |
40812 KB |
Output is correct |
2 |
Correct |
184 ms |
35056 KB |
Output is correct |
3 |
Correct |
206 ms |
36200 KB |
Output is correct |
4 |
Correct |
200 ms |
36584 KB |
Output is correct |
5 |
Correct |
204 ms |
35944 KB |
Output is correct |
6 |
Correct |
151 ms |
42908 KB |
Output is correct |
7 |
Correct |
145 ms |
42732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
144 ms |
40812 KB |
Output is correct |
2 |
Correct |
184 ms |
35056 KB |
Output is correct |
3 |
Correct |
206 ms |
36200 KB |
Output is correct |
4 |
Correct |
200 ms |
36584 KB |
Output is correct |
5 |
Correct |
204 ms |
35944 KB |
Output is correct |
6 |
Correct |
151 ms |
42908 KB |
Output is correct |
7 |
Correct |
145 ms |
42732 KB |
Output is correct |
8 |
Correct |
159 ms |
42476 KB |
Output is correct |
9 |
Correct |
155 ms |
42476 KB |
Output is correct |
10 |
Correct |
151 ms |
50532 KB |
Output is correct |
11 |
Correct |
154 ms |
50404 KB |
Output is correct |
12 |
Correct |
126 ms |
32748 KB |
Output is correct |
13 |
Correct |
127 ms |
32768 KB |
Output is correct |
14 |
Correct |
169 ms |
32620 KB |
Output is correct |
15 |
Correct |
169 ms |
32364 KB |
Output is correct |
16 |
Correct |
210 ms |
36584 KB |
Output is correct |
17 |
Correct |
203 ms |
36456 KB |
Output is correct |
18 |
Correct |
204 ms |
36604 KB |
Output is correct |
19 |
Correct |
179 ms |
34924 KB |
Output is correct |
20 |
Correct |
151 ms |
43116 KB |
Output is correct |
21 |
Correct |
152 ms |
43112 KB |
Output is correct |
22 |
Correct |
147 ms |
43116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12140 KB |
Output is correct |
2 |
Correct |
16 ms |
13676 KB |
Output is correct |
3 |
Correct |
15 ms |
13676 KB |
Output is correct |
4 |
Correct |
9 ms |
12140 KB |
Output is correct |
5 |
Correct |
9 ms |
12140 KB |
Output is correct |
6 |
Correct |
16 ms |
14572 KB |
Output is correct |
7 |
Correct |
15 ms |
13804 KB |
Output is correct |
8 |
Correct |
17 ms |
13804 KB |
Output is correct |
9 |
Correct |
15 ms |
13804 KB |
Output is correct |
10 |
Correct |
8 ms |
12140 KB |
Output is correct |
11 |
Correct |
8 ms |
12140 KB |
Output is correct |
12 |
Correct |
8 ms |
12140 KB |
Output is correct |
13 |
Correct |
8 ms |
12140 KB |
Output is correct |
14 |
Correct |
9 ms |
12140 KB |
Output is correct |
15 |
Correct |
54 ms |
18284 KB |
Output is correct |
16 |
Correct |
54 ms |
18284 KB |
Output is correct |
17 |
Correct |
55 ms |
18284 KB |
Output is correct |
18 |
Correct |
17 ms |
14700 KB |
Output is correct |
19 |
Correct |
15 ms |
13932 KB |
Output is correct |
20 |
Correct |
61 ms |
19564 KB |
Output is correct |
21 |
Correct |
61 ms |
19564 KB |
Output is correct |
22 |
Correct |
8 ms |
12140 KB |
Output is correct |
23 |
Correct |
14 ms |
13676 KB |
Output is correct |
24 |
Correct |
15 ms |
13676 KB |
Output is correct |
25 |
Correct |
8 ms |
12140 KB |
Output is correct |
26 |
Correct |
8 ms |
12140 KB |
Output is correct |
27 |
Correct |
16 ms |
14572 KB |
Output is correct |
28 |
Correct |
15 ms |
13804 KB |
Output is correct |
29 |
Correct |
14 ms |
13824 KB |
Output is correct |
30 |
Correct |
16 ms |
13676 KB |
Output is correct |
31 |
Correct |
8 ms |
12140 KB |
Output is correct |
32 |
Correct |
8 ms |
12140 KB |
Output is correct |
33 |
Correct |
8 ms |
12140 KB |
Output is correct |
34 |
Correct |
9 ms |
12140 KB |
Output is correct |
35 |
Correct |
8 ms |
12140 KB |
Output is correct |
36 |
Correct |
210 ms |
50864 KB |
Output is correct |
37 |
Correct |
8 ms |
12140 KB |
Output is correct |
38 |
Correct |
208 ms |
52456 KB |
Output is correct |
39 |
Correct |
196 ms |
51948 KB |
Output is correct |
40 |
Correct |
187 ms |
50916 KB |
Output is correct |
41 |
Correct |
164 ms |
53228 KB |
Output is correct |
42 |
Correct |
144 ms |
40812 KB |
Output is correct |
43 |
Correct |
184 ms |
35056 KB |
Output is correct |
44 |
Correct |
206 ms |
36200 KB |
Output is correct |
45 |
Correct |
200 ms |
36584 KB |
Output is correct |
46 |
Correct |
204 ms |
35944 KB |
Output is correct |
47 |
Correct |
151 ms |
42908 KB |
Output is correct |
48 |
Correct |
145 ms |
42732 KB |
Output is correct |
49 |
Correct |
159 ms |
42476 KB |
Output is correct |
50 |
Correct |
155 ms |
42476 KB |
Output is correct |
51 |
Correct |
151 ms |
50532 KB |
Output is correct |
52 |
Correct |
154 ms |
50404 KB |
Output is correct |
53 |
Correct |
126 ms |
32748 KB |
Output is correct |
54 |
Correct |
127 ms |
32768 KB |
Output is correct |
55 |
Correct |
169 ms |
32620 KB |
Output is correct |
56 |
Correct |
169 ms |
32364 KB |
Output is correct |
57 |
Correct |
210 ms |
36584 KB |
Output is correct |
58 |
Correct |
203 ms |
36456 KB |
Output is correct |
59 |
Correct |
204 ms |
36604 KB |
Output is correct |
60 |
Correct |
179 ms |
34924 KB |
Output is correct |
61 |
Correct |
151 ms |
43116 KB |
Output is correct |
62 |
Correct |
152 ms |
43112 KB |
Output is correct |
63 |
Correct |
147 ms |
43116 KB |
Output is correct |
64 |
Correct |
167 ms |
42988 KB |
Output is correct |
65 |
Correct |
281 ms |
35692 KB |
Output is correct |
66 |
Correct |
229 ms |
33900 KB |
Output is correct |
67 |
Correct |
195 ms |
33388 KB |
Output is correct |
68 |
Correct |
116 ms |
30188 KB |
Output is correct |
69 |
Correct |
122 ms |
30188 KB |
Output is correct |
70 |
Correct |
167 ms |
44012 KB |
Output is correct |
71 |
Correct |
161 ms |
42408 KB |
Output is correct |
72 |
Correct |
8 ms |
12140 KB |
Output is correct |
73 |
Correct |
14 ms |
13676 KB |
Output is correct |
74 |
Correct |
14 ms |
13676 KB |
Output is correct |
75 |
Correct |
8 ms |
12140 KB |
Output is correct |
76 |
Correct |
8 ms |
12140 KB |
Output is correct |
77 |
Correct |
15 ms |
14572 KB |
Output is correct |
78 |
Correct |
14 ms |
13804 KB |
Output is correct |
79 |
Correct |
14 ms |
13676 KB |
Output is correct |
80 |
Correct |
14 ms |
13804 KB |
Output is correct |
81 |
Correct |
8 ms |
12140 KB |
Output is correct |
82 |
Correct |
8 ms |
12140 KB |
Output is correct |
83 |
Correct |
8 ms |
12140 KB |
Output is correct |
84 |
Correct |
8 ms |
12140 KB |
Output is correct |
85 |
Correct |
8 ms |
12140 KB |
Output is correct |
86 |
Correct |
53 ms |
18308 KB |
Output is correct |
87 |
Correct |
53 ms |
18284 KB |
Output is correct |
88 |
Correct |
57 ms |
18504 KB |
Output is correct |
89 |
Correct |
16 ms |
14700 KB |
Output is correct |
90 |
Correct |
15 ms |
13876 KB |
Output is correct |
91 |
Correct |
60 ms |
19564 KB |
Output is correct |
92 |
Correct |
60 ms |
19564 KB |
Output is correct |
93 |
Correct |
8 ms |
12140 KB |
Output is correct |
94 |
Correct |
209 ms |
52708 KB |
Output is correct |
95 |
Correct |
199 ms |
52328 KB |
Output is correct |
96 |
Correct |
193 ms |
51820 KB |
Output is correct |
97 |
Correct |
186 ms |
50744 KB |
Output is correct |
98 |
Correct |
164 ms |
53228 KB |
Output is correct |
99 |
Correct |
218 ms |
36724 KB |
Output is correct |
100 |
Correct |
212 ms |
36840 KB |
Output is correct |
101 |
Correct |
213 ms |
36584 KB |
Output is correct |
102 |
Correct |
176 ms |
35180 KB |
Output is correct |
103 |
Correct |
146 ms |
42732 KB |
Output is correct |
104 |
Correct |
147 ms |
43120 KB |
Output is correct |
105 |
Correct |
144 ms |
42860 KB |
Output is correct |
106 |
Correct |
154 ms |
42604 KB |
Output is correct |
107 |
Correct |
150 ms |
42476 KB |
Output is correct |
108 |
Correct |
148 ms |
50404 KB |
Output is correct |
109 |
Correct |
148 ms |
50404 KB |
Output is correct |
110 |
Correct |
121 ms |
32748 KB |
Output is correct |
111 |
Correct |
120 ms |
32748 KB |
Output is correct |
112 |
Correct |
164 ms |
32236 KB |
Output is correct |
113 |
Correct |
163 ms |
32620 KB |
Output is correct |