Submission #1258429

#TimeUsernameProblemLanguageResultExecution timeMemory
1258429nlsosadCat in a tree (BOI17_catinatree)C++20
100 / 100
119 ms23260 KiB
#include <bits/stdc++.h>
using namespace std;
int n, d;
vector<int> a[200001];
vector<bool> vst(200001, false);
int dist[200001];
int res = 0;
void dfs(int u){
	vst[u] = true;
	vector<int> luu;
	for (int v:a[u]){
		if(!vst[v]){
			dfs(v);
			luu.push_back(dist[v]);
		}
	}
	sort(luu.begin(), luu.end());
	bool check = false;
	reverse(luu.begin(), luu.end());
	int i = luu.size()-2;
	int j = i+1;
	while(i>=0 and luu[i]+luu[j]+2<d){
		i--;
		j--;
		luu.pop_back();
		res--;
	}
	if(luu.empty() or luu.back()+1>=d){
		check = true;
	}
	if(check){
		dist[u] = 0;
		res++;
	}else dist[u] = luu.back()+1;
}
int main(){
	cin >> n >> d;
	for (int i =1;i<n;++i){
		int x;
		cin >> x;
		a[x].push_back(i);
		a[i].push_back(x);
	}
	dfs(0);
	cout << res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...