Submission #544145

#TimeUsernameProblemLanguageResultExecution timeMemory
544145levladiatorPastiri (COI20_pastiri)C++14
18 / 100
625 ms74100 KiB
#include <bits/stdc++.h> #define pb push_back #define pf push_front #define ll long long #define ull unsigned long long #define pii pair<int,int> #define pll pair<ll,ll> #define EPSILON 0.000001 #define CH (*s-'a') using namespace std; const ll NMAX = 5e5 + 5, INF = 1e18, MOD = 1e9 + 7, MMAX = 1e2 + 5, inf = 1e9; ifstream fin("sufle.in"); ofstream fout("sufle.out"); int N,K; int sheep[NMAX],dep[NMAX],dist[NMAX],anc[NMAX]; bool vis[NMAX]; vector<int> adj[NMAX],ans; struct nod { int dep,node,anc; }; nod v[NMAX]; bool cmp(nod a,nod b) { return a.dep>b.dep; } void bfs() { queue<int> Q; for(int i=1;i<=N;i++) { if(sheep[i])Q.push(i); } while(!Q.empty()) { int node=Q.front(); Q.pop(); for(auto vec : adj[node]) { if(!sheep[vec]&&!dist[vec]) { dist[vec]=dist[node]+1; Q.push(vec); } } } } void dfs(int node,int prev,int last) { dep[node]=dep[prev]+1; if(sheep[node])anc[node]=last; if(dist[last]+dep[last]<dist[node]+dep[node]) { last=node; } for(auto son : adj[node]) { if(son==prev) continue; dfs(son,node,last); } } void mark(int node) { vis[node]=1; for(auto vec : adj[node]) { if(vis[vec]) continue; if(dist[vec]+1==dist[node]) { mark(vec); } } } int main() { cin.tie ( 0 )->sync_with_stdio ( 0 ); cin.tie ( NULL ); cout.tie ( NULL ); cin>>N>>K; for(int i=1;i<N;i++) { int a,b; cin>>a>>b; adj[a].pb(b); adj[b].pb(a); } for(int i=1;i<=K;i++) { int x; cin>>x; sheep[x]=1; v[i].node=x; v[i].dep=dep[x]; v[i].anc=anc[x]; } bfs(); dfs(1,0,1); int cnt=0; for(int i=1;i<=N;i++) { if(sheep[i]) { cnt++; v[cnt].node=i; v[cnt].dep=dep[i]; v[cnt].anc=anc[i]; } } sort(v+1,v+K+1,cmp); for(int i=1;i<=K;i++) { int node=v[i].node; if(!vis[node]) { ans.pb(anc[node]); mark(anc[node]); } } cout<<ans.size()<<'\n'; for(auto x : ans) { cout<<x<<' '; } 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...