제출 #796398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
796398		SlavicG	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	76 ms	27496 KiB

catinatree

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

#define pb push_back
#define int int64_t
const int N = 2e5 + 5;
vector<int> adj[N];
int n, d, depth[N];

pair<int, int> dp[N];

void dfs(int u) {
	vector<pair<int, int>> c;
	for(int v: adj[u]) {
		depth[v] = depth[u] + 1;
		dfs(v);
		c.pb(dp[v]);
	}
	sort(c.rbegin(), c.rend());
	int can = -1, min_depth = INT_MAX, add = 0;
	for(auto x: c) {
		int dep = x.first, w = x.second;
		if(can <= dep) {
			add += w;
			min_depth = min(min_depth, dep);
			can = max(can, d + 2 * depth[u] - dep);
		} else {
			add += w - 1;
		}
	}
	if(can <= depth[u]) ++add, min_depth = depth[u];
	dp[u] = {min_depth, add};
}

void solve() {
	cin >> n >> d;
	for(int i = 1; i < n; ++i) {
		int x; cin >> x;
		adj[x].pb(i);
	}
	dfs(0);
	cout << dp[0].second << "\n";
}

int32_t main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		solve();
	}
}
/*
4 3
0
0
1

3 1000
0
0

g++ -Wall -lm -static -DEVAL -o p1 -O2 p1.cpp -std=c++14 
*/

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