Submission #447144

#TimeUsernameProblemLanguageResultExecution timeMemory
447144MOUF_MAHMALATPastiri (COI20_pastiri)C++14
0 / 100
1122 ms524292 KiB
#include<bits/stdc++.h> #define all(s) s.begin(),s.end() using namespace std; typedef int ll; typedef pair<ll,ll>pll; ll n,x,y,k,d[500009],a[500009],h[500009],c; pll op[500009]; vector<vector<ll> >v; queue<ll>q; vector<ll>ans; bool b[500009]; bool cmp(ll xo,ll yo) { return h[xo]>h[yo]; } struct node { ll f,s,t; }; queue<node>dq; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); scanf("%d%d",&n,&k); v.resize(n+1); for(ll i=1; i<n; i++) { scanf("%d%d",&x,&y); v[x].push_back(y); v[y].push_back(x); } for(ll i=1; i<=n; i++) d[i]=1e9,op[i]= {1e9,1e9}; for(ll i=1; i<=k; i++) scanf("%d",&a[i]),d[a[i]]=0,q.push(a[i]); h[1]=1; q.push(1); while(!q.empty()) { x=q.front(); q.pop(); for(auto z:v[x]) { if(h[z]) h[x]=h[z]+1; else q.push(z); } } while(!q.empty()) { x=q.front(); q.pop(); for(auto z:v[x]) { if(d[z]<=d[x]+1) continue; d[z]=d[x]+1; q.push(z); } } dq.push({1,0,1}); while(!dq.empty()) { x=dq.front().f; ll p=dq.front().s; ll id=dq.front().t; dq.pop(); if(d[x]==0) op[x]= {h[id],id}; for(auto z:v[x]) { if(z==p) continue; if(d[x]==d[z]+1) dq.push({z,x,id}); else dq.push({z,x,z}); } } sort(a+1,a+k+1,cmp); for(ll i=1; i<=k; i++) { if(b[a[i]]) continue; ans.push_back(op[a[i]].second); dq.push({op[a[i]].second,h[a[i]]-op[a[i]].first,0}); while(!dq.empty()) { x=dq.front().f; c=dq.front().s; ll p=dq.front().t; dq.pop(); b[x]=1; if(c==0) continue; for(auto z:v[x]) if(z!=p) dq.push({z,c-1,x}); } } cout<<ans.size()<<endl; for(auto z:ans) cout<<z<<" "; return 0; }

Compilation message (stderr)

pastiri.cpp: In function 'int main()':
pastiri.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
pastiri.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~
pastiri.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d",&a[i]),d[a[i]]=0,q.push(a[i]);
      |         ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...