Submission #1098811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098811		amunduzbaev	Cat in a tree (BOI17_catinatree)	C++17	51 / 100	1037 ms	14180 KiB

catinatree

#include "bits/stdc++.h"

using namespace std;

#define ar array
typedef long long ll;
//~ #define int ll

template<class T> bool umin(T& a, const T b) { if(b < a) { a = b; return true; } return false; }
template<class T> bool umax(T& a, const T b) { if(a < b) { a = b; return true; } return false; }

void solve(){
	int n, D; cin >> n >> D;
	
	vector<vector<int>> edges(n + 1);
	
	for(int i=2;i<=n;i++){
		int a; cin >> a;  a++;
		
		edges[a].push_back(i);
		edges[i].push_back(a);
	}
	
	vector<int> d(n + 1);
	function<void(int, int)> dfs = [&](int u, int p){
		for(auto x : edges[u]){
			if(x == p) continue;
			d[x] = d[u] + 1;
			dfs(x, u);
		}
	};
	
	dfs(1, 1);
	int a = 1;
	for(int i=1;i<=n;i++){
		if(d[i] > d[a]) a = i;
	}
	
	d[a] = 0;
	dfs(a, a);
	
	vector<int> p(n);
	iota(p.begin(), p.end(), 1);
	sort(p.begin(), p.end(), [&](int i, int j){
		return d[i] > d[j];
	});
	
	vector<int> vis(n + 1);
	int res = 0;
	
	for(auto x : p){
		function<void(int, int, int)> dfs = [&](int u, int p, int d_){
			if(d_ >= D) return;
			vis[u] = 1;
			for(auto x : edges[u]){
				if(x == p) continue;
				dfs(x, u, d_ + 1);
			}
		};
		
		if(!vis[x]){
			res++;
			dfs(x, x, 0);
		}
	}
	
	cout<<res<<"\n";
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int t = 1;
	
	//~ cin >> t;
	
	while(t--){
		solve();
	}
}

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