이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ve vector
typedef long long ll;
int s;
ve<bool> C;
ve<int> E, U;
ve<ve<pair<int, int>>> G;
void edge(int u, int p) {
int v;
for (pair<int, int> e : G[u]) {
v = e.first;
if (v != p) {
E[v] = e.second;
edge(v, u);
}
}
}
int dfs(int u, int p) {
int t, v;
t = 0;
for (pair<int, int> e : G[u]) {
v = e.first;
if (v != p) {
t += dfs(v, u);
}
}
if (C[u]) t++;
if (t > 0 && t != s) U[u]++;
return t;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, k, a, b, ans;
ve<int> S;
cin >> n >> m >> k;
G = ve<ve<pair<int, int>>>(n);
E = ve<int>(n);
U = ve<int>(n);
for (int i = 0; i < n - 1; i++) {
cin >> a >> b;
a--;
b--;
G[a].push_back({b, i});
G[b].push_back({a, i});
}
edge(0, -1);
for (int i = 0; i < m; i++) {
cin >> s;
C = ve<bool>(n);
for (int j = 0; j < s; j++) {
cin >> a;
a--;
C[a] = true;
}
dfs(0, -1);
}
ans = 0;
for (int i = 1; i < n; i++) {
if (U[i] >= k) {
ans++;
S.push_back(E[i]);
}
}
sort(S.begin(), S.end());
cout << ans << endl;
for (int i = 0; i < ans; i++) {
cout << S[i] + 1 << " ";
}
cout << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |