Submission #941977

#	Time	Username	Problem	Language	Result	Execution time	Memory
941977		andrei_c1	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	188 ms	50508 KiB

catinatree

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

const int kN = 2e5;
const int kLog = 20;
const int kInf = 1e9;

int dep[kN], tin[kN];
vector<int> adj[kN], rmq[kLog];

void dfs(int u, int p = -1) {
	tin[u] = rmq[0].size();
	rmq[0].emplace_back(u);
	for(const auto &v: adj[u]) if(v != p) {
		dep[v] = dep[u] + 1;
		dfs(v, u);
		rmq[0].emplace_back(u);
	}
}

int minNode(int u, int v) {
	if(dep[u] < dep[v]) return u;
	return v;
}

int lca(int u, int v) {
	int l = tin[u], r = tin[v];
	if(l > r) swap(l, r);
	int lg = __lg(r - l + 1);
	return minNode(rmq[lg][l], rmq[lg][r - (1 << lg) + 1]);
}

int dist(int u, int v) {
	return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

void minSelf(int &x, int y) {
	if(y < x) {
		x = y;
	}
}

int sz[kN];
bitset<kN> rem;

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

int findCentroid(int u, int desired, int p = -1) {
	for(const auto &v: adj[u]) if(!rem[v] && v != p && sz[v] > desired) {
		return findCentroid(v, desired, u);
	}
	return u;
}

int up[kN], best[kN];

void buildTree(int u, int p = -1) {
	findSizes(u);
	int c = findCentroid(u, sz[u] >> 1);
	rem[c] = true;
	up[c] = p;
	for(const auto &v: adj[c]) if(!rem[v]) {
		buildTree(v, c);
	}
}

int findClosest(int u) {
	int res = kInf, v = u;
	while(v != -1) {
		minSelf(res, best[v] + dist(u, v));
		v = up[v];
	}
	return res;
}

void updateClosest(int u) {
	int v = u;
	while(v != -1) {
		minSelf(best[v], dist(u, v));
		v = up[v];
	}
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, d;
	cin >> n >> d;
	for(int i = 1; i < n; i++) {
		int x;
		cin >> x;
		adj[x].emplace_back(i);
		adj[i].emplace_back(x);
	}
	rmq[0].reserve(n << 1);
	dfs(0);
	for(int i = 1; (1 << i) < n << 1; i++) {
		for(int j = 0; j + (1 << i) - 1 < 2 * n - 1; j++) {
			rmq[i].emplace_back(minNode(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]));
		}
	}
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&] (int u, int v) {
		return dep[u] > dep[v];
	});
	fill(best, best + n, kInf);
	fill(up, up + n, -1);
	buildTree(0);
	int ans = 0;
	for(const auto &u: ord) {
		int closest = findClosest(u);
		if(closest >= d) {
			ans++;
			updateClosest(u);
		}
	}
	cout << ans;
	return 0;
}

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