Submission #132710

#	Time	Username	Problem	Language	Result	Execution time	Memory
132710		youngyojun	Cat in a tree (BOI17_catinatree)	C++11	100 / 100	207 ms	16280 KiB

catinatree

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

const int MAXN = 200055;

vector<int> G[MAXN];
int prt[MAXN], dep[MAXN];
int A[MAXN], O[MAXN];

int N, D, Ans;

void f(int i) {
	if(A[i] < 2) return;
	int l = A[i]-1;
	for(int v : G[i]) if(A[v] < l) {
		A[v] = l;
		f(v);
	}
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> D;
	for(int i = 1; i < N; i++) {
		cin >> prt[i];
		dep[i] = dep[prt[i]] + 1;
		G[prt[i]].eb(i);
		G[i].eb(prt[i]);
	}

	iota(O, O+N, 0); sort(O, O+N, [&](int a, int b) {
		return dep[a] > dep[b];
	});

	for(int oi = 0, i; oi < N; oi++) {
		i = O[oi];
		if(!A[i]) {
			Ans++;
			A[i] = D;
			f(i);
		}
	}

	cout << Ans << endl;
	return 0;
}

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