Submission #1254101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254101		kaiboy	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	51 ms	19272 KiB

catinatree

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int   N = 200000;
const int INF = 0x3f3f3f3f;

vector<int> ej[N];
int kk[N], dd[N], d_;

void dfs(int i) {
	int k = 0, d = 0, e = INF;
	for (int j : ej[i]) {
		dfs(j);
		k += kk[j];
		if (dd[j] + 1 < (d_ + 1) / 2)
			k--, d = max(d, dd[j] + 1);
		else
			e = min(e, dd[j] + 1);
	}
	if (d + e >= d_) {
		kk[i] = k + 1;
		dd[i] = d;
	} else {
		kk[i] = k;
		dd[i] = e;
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n >> d_;
	for (int i = 1; i < n; i++) {
		int p; cin >> p;
		ej[p].push_back(i);
	}
	dfs(0);
	cout << kk[0] << '\n';
	return 0;
}

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