Submission #917665

#	Time	Username	Problem	Language	Result	Execution time	Memory
917665		dsyz	Cat in a tree (BOI17_catinatree)	C++17	51 / 100	1049 ms	18892 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (200005)
ll N,D;
vector<ll> v[MAXN];
bool cannot[MAXN];
vector<pair<ll,ll> > sortbydepth;
void dfs1(ll x,ll p,ll level){
	sortbydepth.push_back({level,x});
	for(auto u : v[x]){
		if(u != p){
			dfs1(u,x,level + 1);
		}	
	}
}
void dfs2(ll x,ll p,ll distance){
	cannot[x] = true;
	for(auto u : v[x]){
		if(u != p && 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;
		v[p].push_back(i);
		v[i].push_back(p);
	}
	dfs1(0,-1,-1);
	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); //mark the nodes within D distance as cannot be picked
	}
	cout<<ans<<'\n';
}

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 0 / 49