#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
int n, m, k, markCount[100050];
vvii adj;
vii edges;
bitset<100050> visited, isDest;
bool dfs(int u) {
if (visited[u]) return 0;
visited[u] = 1;
bool takeEdges = isDest[u];
for (ii edge : adj[u]) {
int v = edge.fi;
int edgeInd = edge.se;
if (!visited[v]) {
if (dfs(v)) {
takeEdges = 1;
markCount[edgeInd]++;
}
}
}
return takeEdges;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
adj.assign(n + 20, vii());
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
edges.push_back({a, b});
adj[a].push_back({b, i});
adj[b].push_back({a, i});
}
for (int j = 0; j < m; j++) {
int s, start;
cin >> s >> start;
isDest.reset();
for (int i = 0; i < s - 1; i++) {
int tmp; cin >> tmp;
isDest[tmp] = 1;
}
visited.reset();
dfs(start);
}
vi ans;
for (int i = 0; i < n - 1; i++) {
if (markCount[i] >= k) ans.push_back(i);
}
cout << (int)ans.size() << '\n';
for (int i = 0; i < (int)ans.size(); i++) {
if (i) cout << ' ';
cout << ans[i] + 1;
}
cout << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
61 ms |
1356 KB |
Output is correct |
3 |
Correct |
61 ms |
1400 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
88 ms |
1708 KB |
Output is correct |
7 |
Correct |
31 ms |
1456 KB |
Output is correct |
8 |
Correct |
105 ms |
1352 KB |
Output is correct |
9 |
Correct |
131 ms |
1352 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
324 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
61 ms |
1356 KB |
Output is correct |
3 |
Correct |
61 ms |
1400 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
88 ms |
1708 KB |
Output is correct |
7 |
Correct |
31 ms |
1456 KB |
Output is correct |
8 |
Correct |
105 ms |
1352 KB |
Output is correct |
9 |
Correct |
131 ms |
1352 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
324 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
425 ms |
1860 KB |
Output is correct |
16 |
Correct |
431 ms |
1780 KB |
Output is correct |
17 |
Correct |
429 ms |
1884 KB |
Output is correct |
18 |
Correct |
367 ms |
1696 KB |
Output is correct |
19 |
Correct |
253 ms |
1468 KB |
Output is correct |
20 |
Correct |
119 ms |
1836 KB |
Output is correct |
21 |
Correct |
98 ms |
1752 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
58 ms |
1356 KB |
Output is correct |
24 |
Correct |
58 ms |
1356 KB |
Output is correct |
25 |
Correct |
0 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
328 KB |
Output is correct |
27 |
Correct |
85 ms |
1696 KB |
Output is correct |
28 |
Correct |
31 ms |
1360 KB |
Output is correct |
29 |
Correct |
105 ms |
1352 KB |
Output is correct |
30 |
Correct |
129 ms |
1412 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1087 ms |
17004 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1081 ms |
14136 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1081 ms |
14136 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
61 ms |
1356 KB |
Output is correct |
3 |
Correct |
61 ms |
1400 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
88 ms |
1708 KB |
Output is correct |
7 |
Correct |
31 ms |
1456 KB |
Output is correct |
8 |
Correct |
105 ms |
1352 KB |
Output is correct |
9 |
Correct |
131 ms |
1352 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
324 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
425 ms |
1860 KB |
Output is correct |
16 |
Correct |
431 ms |
1780 KB |
Output is correct |
17 |
Correct |
429 ms |
1884 KB |
Output is correct |
18 |
Correct |
367 ms |
1696 KB |
Output is correct |
19 |
Correct |
253 ms |
1468 KB |
Output is correct |
20 |
Correct |
119 ms |
1836 KB |
Output is correct |
21 |
Correct |
98 ms |
1752 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
58 ms |
1356 KB |
Output is correct |
24 |
Correct |
58 ms |
1356 KB |
Output is correct |
25 |
Correct |
0 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
328 KB |
Output is correct |
27 |
Correct |
85 ms |
1696 KB |
Output is correct |
28 |
Correct |
31 ms |
1360 KB |
Output is correct |
29 |
Correct |
105 ms |
1352 KB |
Output is correct |
30 |
Correct |
129 ms |
1412 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
324 KB |
Output is correct |
36 |
Execution timed out |
1087 ms |
17004 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |