Submission #446847

#TimeUsernameProblemLanguageResultExecution timeMemory
446847MOUF_MAHMALATPastiri (COI20_pastiri)C++14
0 / 100
605 ms56904 KiB
#include<bits/stdc++.h> #define all(s) s.begin(),s.end() using namespace std; typedef int ll; ll n,k,x,y,c[500009],d[500009]; vector<vector<ll> >v; queue<ll>q; bool b[500009],is; vector<ll>ans; struct node { ll cnt,dis,id; } a[500009]; bool cmp(const node&x,const node&y) { if(x.cnt==y.cnt) return x.dis>y.dis; return x.cnt>y.cnt; } void dfs(ll o) { if(d[o]==0) is=1; b[o]=1; for(auto z:v[o]) { if(b[z]||d[o]!=d[z]+1) continue; dfs(z); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>k; v.resize(n+1); for(ll i=1; i<n; i++) { cin>>x>>y; v[x].push_back(y); v[y].push_back(x); } for(ll i=1; i<=n; i++) d[i]=1e9; while(k--) { cin>>x; d[x]=0; c[x]=1; q.push(x); } while(!q.empty()) { x=q.front(); q.pop(); for(auto z:v[x]) { if(d[z]<d[x]+1) continue; c[z]+=c[x]; if(d[z]>d[x]+1) { d[z]=d[x]+1; q.push(z); } } } for(ll i=1; i<=n; i++) a[i]= {c[i],d[i],i}; sort(a+1,a+n+1,cmp); for(ll i=1; i<=n; i++) { if(b[a[i].id]) continue; is=0; dfs(a[i].id); if(is) ans.push_back(a[i].id); } cout<<ans.size()<<endl; for(auto z:ans) cout<<z<<" "; 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...