Submission #1199217

#TimeUsernameProblemLanguageResultExecution timeMemory
1199217enzyRailway (BOI17_railway)C++20
100 / 100
243 ms41256 KiB
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; map<pair<int,int>,int>imp; set<pair<int,int>>s[maxn]; int minister[maxn], marc[maxn], tira[maxn], k; vector<int>v[maxn], resp; void merge(int pai, int filho){ int swp=0; if(s[filho].size()>s[pai].size()){ swap(filho,pai); swp++; } for(pair<int,int>p : s[filho]){ auto f=s[pai].lower_bound({p.first,0}); if(f==s[pai].end()||f->first!=p.first) s[pai].insert(p); else{ if(f->second+p.second==minister[p.first]) tira[pai]++; s[pai].insert({p.first,p.second+f->second}); s[pai].erase(f); } } if(swp){ swap(s[pai],s[filho]); swap(pai,filho); } s[filho].clear(); } void dfs(int u, int pai){ marc[u]++; for(int viz : v[u]){ if(viz==pai) continue; dfs(viz,u); merge(u,viz); tira[u]+=tira[viz]; } //cout << u << " " << s[u].size() << " " << tira[u] << endl; if(s[u].size()-tira[u]>=k){ resp.push_back(imp[{u,pai}]); } } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, m; cin >> n >> m >> k; for(int i=1;i<n;i++){ int a, b; cin >> a >> b; v[a].push_back(b); v[b].push_back(a); imp[{a,b}]=imp[{b,a}]=i; } for(int i=1;i<=m;i++){ int x; cin >> x; for(int j=1;j<=x;j++){ int a; cin >> a; s[a].insert({i,1}); } minister[i]=x; } dfs(1,0); sort(resp.begin(),resp.end()); cout << resp.size() << endl; for(int a : resp) cout << a << " "; cout << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...