Submission #314682

#	Time	Username	Problem	Language	Result	Execution time	Memory
314682		sofapuden	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	234 ms	21956 KiB

catinatree

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> gra;
queue<int> Q;
vector<bool> vis;
int root = 0, n, d, ans = 0;

int dfs(int x, int p){
	vector<int> und;
	for(int i : gra[x]){
		if(i == p)continue;
		und.push_back(dfs(i,x));
	}
	if(!und.size()){ans++;return 1;}
	sort(und.rbegin(),und.rend());
	int cur = und[0];
	for(int i = 1; i < (int)und.size(); ++i){
		if(cur + und[i] < d)ans--;
		else cur = und[i];
	}
	if(cur >= d){
		cur-=d;
		ans++;
	}
	return cur+1;
}

int main(){
	cin >> n >> d;
	vis.resize(n,false);
	gra.resize(n);
	for(int i = 1; i < n; ++i){
		int a; cin >> a;
		gra[a].push_back(i);
		gra[i].push_back(a);
	}
	dfs(0,0);
	cout << ans << "\n";
}
		
	

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