Submission #917644

#	Time	Username	Problem	Language	Result	Execution time	Memory
917644		dsyz	Cat in a tree (BOI17_catinatree)	C++17	0 / 100	3 ms	6748 KiB

catinatree

#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';
}

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