Submission #758349

#	Time	Username	Problem	Language	Result	Execution time	Memory
758349		MetalPower	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	114 ms	21036 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define fi first
#define se second

const int MX = 2e5 + 10;
const int INF = 1e9 + 7;

int N, D, dep[MX]; vector<int> adj[MX];
pii dp[MX];

void dfs_dep(int u){
	for(int nxt : adj[u]){
		dep[nxt] = dep[u] + 1;
		dfs_dep(nxt);
	}
}

void dfs(int u){

	vector<pii> vec;
	for(int nxt : adj[u]){
		dfs(nxt);
		vec.push_back(dp[nxt]);
	}

	sort(vec.begin(), vec.end(), greater<pii>());
	int mx = dep[u], mxdep = INF, ans = 0;

	for(auto x : vec){
		if(mx <= x.fi){
			ans += x.se, mxdep = min(mxdep, x.fi);
			mx = max(mx, -x.fi + dep[u] + dep[u] + D);
		}else{
			ans += x.se - 1;
		}
	}

	if(mx <= dep[u]) ans++, mxdep = min(mxdep, dep[u]);
	dp[u] = {mxdep, ans};
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> D;
	for(int i = 1; i < N; i++){
		int p; cin >> p;
		adj[p].push_back(i);
	}

	dfs_dep(0);
	dfs(0);
	cout << dp[0].se << '\n';
}

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