Submission #976674

#	Time	Username	Problem	Language	Result	Execution time	Memory
976674		Halym2007	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	72 ms	24916 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define sz size()
const int N = 2e5 + 5;
pii dp[N];
vector <int> v[N];
int n, d;
void solve (int x) {
	dp[x] = {0, d};
	int val = 0;
	vector <int> q;
	for (int i : v[x]) {
		solve (i);
		val += dp[i].ff;
		q.pb (dp[i].ss + 1);
	}
	sort (q.begin(), q.end());
	for (int i = 0; i < (int)q.sz; ++i) {
		int j = lower_bound (q.begin(), q.end(), d - q[i]) - q.begin();
		if (i < j) j--;
		else {
			j = i;
		}
		dp[x] = max (dp[x], {val - j, q[i]});
	}
	if (dp[x].ss >= d) {
		dp[x].ff++;
		dp[x].ss = 0;
	}
}


int main () {
	cin >> n >> d;
	for (int i = 1; i < n; ++i) {
		int par;
		cin >> par;
		v[par].pb (i);
	}
	solve (0);
	cout << dp[0].ff;
}

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