Submission #1115903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115903		BuzzyBeez	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	48 ms	19272 KiB

catinatree

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

vector<int> adj[200000];
pair<int, int> dp[200000];
int D;

void DFS(int u) {
	vector<int> Q;
	for (int v : adj[u]) {
		DFS(v); dp[u].first += dp[v].first;
		Q.push_back(dp[v].second + 1);
	}
	sort(Q.begin(), Q.end(), greater<>());
	if (Q.empty()) dp[u] = {1, 0};
	else if (Q.size() == 1) {
		if (Q[0] >= D) ++dp[u].first, dp[u].second = 0;
		else dp[u].second = Q[0];
	}
	else {
		while (Q.size() > 1 && Q[Q.size() - 1] + Q[Q.size() - 2] < D) --dp[u].first, Q.pop_back();
		dp[u].second = Q.back();
		if (dp[u].second >= D) ++dp[u].first, dp[u].second = 0;
	}
	// cout << u << ' ' << dp[u].first << ' ' << dp[u].second << '\n';
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, u, v; cin >> n >> D;
	for (u = 1; u < n; ++u) cin >> v, adj[v].push_back(u);
	DFS(0); cout << dp[0].first;
}

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