Submission #162675

#	Time	Username	Problem	Language	Result	Execution time	Memory
162675		ruler	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	91 ms	15736 KiB

catinatree

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

#define sync ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
#define debug(x) cerr << #x << ": " << x << endl
#define debugP(p) cerr << #p << ": {" << p.first << ", " << p.second << '}' << endl
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e9, MOD = INF + 7;
 
/////////////////////////////////////////////////////////////////////
 
const int N = 2e5 + 5;

int n, d, DP[N], DIS[N];
vector<int> G[N];

void DFS(int v) {
	if (sz(G[v]) == 0) { DP[v] = 1, DIS[v] = 0; return; }
	DFS(G[v][0]);
	DP[v] = DP[G[v][0]], DIS[v] = DIS[G[v][0]] + 1;
	if (DIS[v] == d) DP[v]++, DIS[v] = 0;
	for (int i = 1; i < sz(G[v]); i++) {
		int u = G[v][i];
		DFS(u);
		if (DIS[v] + DIS[u] + 1 >= d) DP[v] += DP[u], DIS[v] = min(DIS[v], DIS[u] + 1);
		else DP[v] += DP[u] - 1, DIS[v] = max(DIS[v], DIS[u] + 1);
	}
}

int main() {
 
	sync;
	
	cin >> n >> d;
	for (int i = 1; i < n; i++) {
		int p; cin >> p;
		G[p].push_back(i);
	}
	DFS(0);
	cout << DP[0] << endl;


	return 0;
}

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