Submission #667747

#	Time	Username	Problem	Language	Result	Execution time	Memory
667747		dutinmeow	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	350 ms	35152 KiB

catinatree

#include <bits/stdc++.h>

namespace std {

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

} // namespace std

struct heavy_light_decomposition {
	std::vector<int> par, dep, hed, tin;

	heavy_light_decomposition(int R, std::vector<std::vector<int>> T) {
		int n = (int)T.size(), time = 0;
		par.resize(n), dep.resize(n);
		hed.resize(n), tin.resize(n);
		par[R] = -1, dep[R] = 0, hed[R] = R;

		std::y_combinator([&](auto self, int u) -> int {
			int sub = 1, mxs = 0;
			for (int &v : T[u]) {
				if (v == par[u])
					continue;
				par[v] = u;
				dep[v] = dep[u] + 1;
				int t = self(v);
				sub += t;
				if (mxs < t) {
					mxs = t;
					std::swap(T[u].front(), v);
				}
			}
			return sub;
		})(R);

		std::y_combinator([&](auto self, int u) -> void {
			tin[u] = time++;
			for (int v : T[u]) {
				if (v == par[u])
					continue;
				hed[v] = v == T[u].front() ? hed[u] : v;
				self(v);
			}
		})(R);
	}

	int lowest_common_ancestor(int u, int v) {
		for (; hed[u] != hed[v]; u = par[hed[u]])
			if (dep[hed[u]] < dep[hed[v]])
				std::swap(u, v);
		return dep[u] < dep[v] ? u : v;
	}

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

class centroid_decomposition {
	int n;
	std::vector<std::vector<int>> tree;
	std::vector<int> parent, weight;
	std::vector<bool> block;

	int initialize_weight(int u, int p) {
		weight[u] = 1;
		for (int v : tree[u]) {
			if (p == v || block[v])
				continue;
			weight[u] += initialize_weight(v, u);
		}
		return weight[u];
	}

	int find_centroid(int w, int u, int p) {
		for (int v : tree[u]) {
			if (p == v || block[v])
				continue;
			if (2 * weight[v] > w)
				return find_centroid(w, v, u);
		}
		return u;
	}

	void initialize_centroids(int c, int p) {
		int w = initialize_weight(c, -1);
		c = find_centroid(w, c, -1);
		parent[c] = p;
		block[c] = true;
		for (int v : tree[c]) {
			if (block[v])
				continue;
			initialize_centroids(v, c);
		}
	}

public:
	centroid_decomposition(const std::vector<std::vector<int>> &_tree) : n((int)_tree.size()), tree(_tree) {
		parent.resize(n);
		weight.resize(n);
		block.assign(n, false);
		initialize_centroids(0, -1);
	}

	int operator[](int i) { return parent[i]; }
};

int main() {
	using namespace std;

	int N, D;
	cin >> N >> D;
	vector<vector<int>> T(N);
	for (int i = 1; i < N; i++) {
		int p;
		cin >> p;
		T[i].push_back(p);
		T[p].push_back(i);
	}

	heavy_light_decomposition hld(0, T);
	centroid_decomposition cd(T);

	vector<int> ord(N);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&hld](int a, int b) {
		return hld.dep[a] > hld.dep[b];
	});

	vector<int> ans;
	vector<int> dis(N, (int)1e9);
	for (int s : ord) {
		int cur = (int)1e9;
		for (int t = s; t != -1; t = cd[t])
			cur = min(cur, dis[t] + hld.distance(s, t));
		if (cur >= D) {
			ans.push_back(s);
			for (int t = s; t != -1; t = cd[t]) {
				dis[t] = min(dis[t], hld.distance(s, t));
			}
		}
	}

	cout << ans.size() << '\n';
	// for (int u : ans)
	// 	cout << u + 1 << ' ';
	// cout << '\n';
}

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