Submission #1258427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258427		nlsosad	Cat in a tree (BOI17_catinatree)	C++20	51 / 100	48 ms	11204 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
int n, d;
vector<int> a[200001];
vector<bool> vst(200001, false);
int dist[100001];
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;
}

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