# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
447122 | 2021-07-24T16:07:48 Z | MOUF_MAHMALAT | Pastiri (COI20_pastiri) | C++11 | 607 ms | 73784 KB |
#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]; pll op[500009]; vector<vector<ll> >v; queue<pll>q; vector<ll>ans; bool b[500009]; void dfs(ll u,ll p) { h[u]=h[p]+1; for(auto z:v[u]) if(z!=p) dfs(z,u); } bool cmp(ll xo,ll yo) { return h[xo]>h[yo]; } void go(ll u,ll c) { b[u]=1; if(c==0) return; for(auto z:v[u]) if(!b[z]) go(z,c-1); } 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],a[i]}); dfs(1,0); while(!q.empty()) { x=q.front().first; y=q.front().second; q.pop(); op[y]=min(op[y], {h[x],x}); for(auto z:v[x]) { if(d[z]<d[x]+1) continue; d[z]=d[x]+1; q.push({z,y}); } } 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); go(op[a[i]].second,h[a[i]]-op[a[i]].first); } cout<<ans.size()<<endl; for(auto z:ans) cout<<z<<" "; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 213 ms | 65736 KB | Output is correct |
2 | Correct | 253 ms | 66116 KB | Output is correct |
3 | Correct | 250 ms | 66136 KB | Output is correct |
4 | Correct | 396 ms | 73784 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 716 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 460 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 607 ms | 43748 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |