제출 #1199422

#제출 시각아이디문제언어결과실행 시간메모리
1199422enzyRailway (BOI17_railway)C++20
100 / 100
108 ms38592 KiB
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; vector<int>v[maxn], resp; int pre[maxn], pos[maxn], k, tmp, dp[maxn][20], pai[maxn], qtd[maxn], prof[maxn]; map<pair<int,int>,int>imp; void dfs(int u){ tmp++; pre[u]=tmp; for(int viz : v[u]){ if(pre[viz]) continue; prof[viz]=prof[u]+1; pai[viz]=u; dfs(viz); } pos[u]=tmp; } int lca(int a, int b){ if(prof[a]<prof[b]) swap(a,b); int d=prof[a]-prof[b]; for(int k=0;k<20;k++) if(d&(1<<k)) a=dp[a][k]; if(a==b) return a; for(int k=19;k>=0;k--){ int na=dp[a][k], nb=dp[b][k]; if(na!=nb){ a=na; b=nb; } } return pai[a]; } void calc(int u, int pai){ for(int viz : v[u]){ if(viz==pai) continue; calc(viz,u); qtd[u]+=qtd[viz]; } if(qtd[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; k*=2; for(int i=1;i<n;i++){ int a, b; cin >> a >> b; imp[{a,b}]=imp[{b,a}]=i; v[a].push_back(b); v[b].push_back(a); } dfs(1); pai[1]=1; for(int i=1;i<=n;i++) dp[i][0]=pai[i]; for(int k=1;k<20;k++) for(int i=1;i<=n;i++) dp[i][k]=dp[dp[i][k-1]][k-1]; for(int i=1;i<=m;i++){ vector<pair<int,int>>aux; int x; cin >> x; for(int j=1;j<=x;j++){ int a; cin >> a; aux.push_back({pre[a],a}); } sort(aux.begin(),aux.end()); int last=aux.back().second; for(auto p : aux){ qtd[last]++; qtd[p.second]++; qtd[lca(last,p.second)]-=2; last=p.second; } } calc(1,1); sort(resp.begin(),resp.end()); cout << resp.size() << endl; for(int a : resp) cout << a << " "; return 0; }
#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...