Submission #862828

#	Time	Username	Problem	Language	Result	Execution time	Memory
862828		SanguineChameleon	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	274 ms	40836 KiB

catinatree

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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int inf = 1e9 + 20;
const int maxN = 2e5 + 20;
const int maxL = 20;
vector<int> adj[maxN];
bool done[maxN];
int dist[maxL][maxN];
int depth[maxN];
int par[maxN];
int sz[maxN];
int best[maxN];
pair<int, int> order[maxN];

void dfs_dist(int u, int p, int d) {
	for (auto v: adj[u]) {
		if (v != p && !done[v]) {
			dist[d][v] = dist[d][u] + 1;
			dfs_dist(v, u, d);
		}
	}
}

void dfs_size(int u, int p) {
	sz[u] = 1;
	for (auto v: adj[u]) {
		if (v != p && !done[v]) {
			dfs_size(v, u);
			sz[u] += sz[v];
		}
	}
}

int find_cen(int r, int u, int p) {
	for (auto v: adj[u]) {
		if (v != p && !done[v] && sz[v] * 2 > sz[r]) {
			return find_cen(r, v, u);
		}
	}
	return u;
}

void build(int u, int p, int d) {
	dfs_size(u, -1);
	u = find_cen(u, u, -1);
	par[u] = p;
	depth[u] = d;
	dist[d][u] = 0;
	dfs_dist(u, -1, d);
	done[u] = true;
	for (auto v: adj[u]) {
		if (!done[v]) {
			build(v, u, d + 1);
		}
	}
}

void just_do_it() {
	int N, D;
	cin >> N >> D;
	for (int v = 2; v <= N; v++) {
		int u;
		cin >> u;
		u++;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs_dist(1, -1, 0);
	for (int i = 1; i <= N; i++) {
		order[i] = {dist[0][i], i};
	}
	sort(order + 1, order + N + 1, greater<pair<int, int>>());
	build(1, -1, 0);
	for (int i = 1; i <= N; i++) {
		best[i] = inf;
	}
	int res = 0;
	for (int i = 1; i <= N; i++) {
		int u = order[i].second;
		int min_D = inf;
		for (int d = depth[u], p = u; d >= 0; d--, p = par[p]) {
			min_D = min(min_D, best[p] + dist[d][u]);
		}
		if (min_D >= D) {
			res++;
			for (int d = depth[u], p = u; d >= 0; d--, p = par[p]) {
				best[p] = min(best[p], dist[d][u]);
			}
		}
	}
	cout << res;
}

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