이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<pair<int , int> > g[N];
set<pair<int , int> > st[N];
vector<int> ans;
int sz[N] , n , m , k;
void dfs(int v , int par , int num){
for(auto i : g[v]){
int u = i.first , w = i.second;
if(u == par) continue;
dfs(u , v , w);
if(st[v].size() < st[u].size())
swap(st[v] , st[u]);
for(auto &p : st[u]){
auto it = st[v].lower_bound({p.first , -1});
if(it == st[v].end()){
st[v].insert(p);
continue;
}
pair<int , int> pp = *it;
if(pp.first == p.first){
st[v].erase(pp);
if(p.second + pp.second != sz[p.first])
st[v].insert({p.first , p.second + pp.second});
}
else{
st[v].insert(p);
}
}
st[u].clear();
}
if((int)st[v].size() >= k)
ans.push_back(num);
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> k;
for(int i = 1 ; i <= n - 1 ; i++){
int u , v;
cin >> u >> v;
g[u].push_back({v , i});
g[v].push_back({u , i});
}
for(int i = 1 ; i <= m ; i++){
int s;
cin >> s;
sz[i] = s;
for(int j = 0 ; j < s ; j++){
int x;
cin >> x;
if(s == 1) continue;
st[x].insert({i , 1});
}
}
dfs(1 , 0 , 0);
cout << (int)ans.size() << '\n';
for(int i : ans)
cout << i << ' ';
cout << '\n';
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... |