제출 #917644

#제출 시각아이디문제언어결과실행 시간메모리
917644dsyzCat in a tree (BOI17_catinatree)C++17
0 / 100
3 ms6748 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define MAXN (200005) ll N,D; vector<ll> v[MAXN]; ll depth[MAXN]; bool cannot[MAXN]; void dfs1(ll x,ll p){ for(auto u : v[x]){ if(u != p){ depth[u] = depth[x] + 1; dfs1(u,x); } } } void dfs2(ll x,ll p,ll distance){ if(distance >= D) return; if(cannot[x]) return; cannot[x] = true; for(auto u : v[x]){ if(u != p && !cannot[u] && distance + 1 < D){ dfs2(u,x,distance + 1); } } } int main() { ios_base::sync_with_stdio(false);cin.tie(0); cin>>N>>D; for(ll i = 1;i < N;i++){ ll p; cin>>p; //0-indexed v[p].push_back(i); v[i].push_back(p); } dfs1(0,-1); vector<pair<ll,ll> > sortbydepth; for(ll i = 0;i < N;i++){ sortbydepth.push_back({depth[i],i}); } sort(sortbydepth.begin(),sortbydepth.end(),greater<pair<ll,ll> >()); ll ans = 0; for(auto u : sortbydepth){ ll x = u.second; if(cannot[x]) continue; //node x is within dist D from a node selected so far so we can greedily prove that it is not optimal to delete the selected node (with greater depth) and replace it with node x (with lower depth) ans++; dfs2(x,-1,0); //marke the nodes within D distance as cannot be picked } cout<<ans<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...