Submission #1177042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177042		xnqs	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	206 ms	66784 KiB

catinatree

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>

int gs, min_req;
std::vector<std::vector<int>> adj_list;
int depth[200005];
int tin[200005];
int tout[200005];
int rmq[19][400005];

int centroid_root = -1;
std::vector<std::vector<int>> adj_list_centroid;
int centroid_up[200005];
int centroid_dist[200005];

void read_data() {
	std::cin >> gs >> min_req;
	adj_list.resize(gs);
	
	for (int i = 1, tmp; i < gs; i++) {
		std::cin >> tmp;
		adj_list[tmp].emplace_back(i);
		adj_list[i].emplace_back(tmp);
	}
}

inline int get_highest_node(int a, int b) {
	return ((depth[a]<depth[b]) ? a : b);
}

void build_tree() {
	const std::function<void(int,int,int&)> dfs = [&](int k, int p, int& timer) {
		depth[k] = ((p==-1) ? 1 : depth[p]+1);
		tin[k] = tout[k] = ++timer;
		rmq[0][timer] = k;

		for (const auto& i : adj_list[k]) {
			if (i!=p) {
				dfs(i,k,timer);
				tout[k] = ++timer;
				rmq[0][timer] = k;
			}
		}
	};

	int timer = 0;
	dfs(0, -1, timer);
	for (int l = 1; l < 19; l++) {
		for (int i = 1; i+(1<<l)-1 <= 2*gs-1; i++) {
			rmq[l][i] = get_highest_node(rmq[l-1][i], rmq[l-1][i+(1<<(l-1))]);
		}
	}
}

int get_lca(int a, int b) {
	int l = tin[a];
	int r = tin[b];
	if (l>r) {
		std::swap(l,r);
	}

	int lvl = 31-__builtin_clz(r-l+1);
	return get_highest_node(rmq[lvl][l], rmq[lvl][r-(1<<lvl)+1]);
}

inline int get_dist(int a, int b) {
	return depth[a] + depth[b] - 2*depth[get_lca(a,b)];
}

void build_centroid_decomp_tree() {
	std::vector<int> sub_sz(gs, 0);
	std::vector<bool> used(gs, 0);

	const std::function<int(int,int)> dfs_sz = [&](int k, int p) {
		sub_sz[k] = 1;
		for (const auto& i : adj_list[k]) {
			if (i!=p&&!used[i]) {
				sub_sz[k] += dfs_sz(i,k);
			}
		}
		return sub_sz[k];
	};

	const std::function<int(int,int,int)> dfs_find_cen = [&](int k, int p, int sz) {
		for (const auto& i : adj_list[k]) {
			if (i!=p&&!used[i]&&sub_sz[i]>sz/2) {
				return dfs_find_cen(i,k,sz);
			}
		}
		return k;
	};

	const std::function<int(int,int)> dfs_decomp = [&](int k, int p) {
		int sz = dfs_sz(k,-1);
		int cen = dfs_find_cen(k,-1,sz);
		used[cen] = 1;

		for (const auto& i : adj_list[cen]) {
			if (!used[i]&&i!=p) {
				int child = dfs_decomp(i, cen);
				centroid_up[child] = cen;
				adj_list_centroid[cen].emplace_back(child);
				adj_list_centroid[child].emplace_back(cen);
			}
		}

		return cen;
	};

	adj_list_centroid.resize(gs);
	centroid_root = dfs_decomp(0, -1);
	centroid_up[centroid_root] = -1;
	std::fill(centroid_dist, centroid_dist+200005, 0x3f3f3f3f);
}

void centroid_tree_add(int node) {
	int tmp = node;
	while (tmp!=-1) {
		centroid_dist[tmp] = std::min(centroid_dist[tmp], get_dist(tmp, node));
		tmp = centroid_up[tmp];
	}
}

int centroid_tree_get_nearest_node(int node) {
	int tmp = node;
	int ret = 0x3f3f3f3f;
	while (tmp!=-1) {
		ret = std::min(ret, get_dist(node, tmp) + centroid_dist[tmp]);
		tmp = centroid_up[tmp];
	}
	return ret;
}

void solve() {
	std::priority_queue<std::pair<int,int>> pq;
	for (int i = 0; i < gs; i++) {
		pq.emplace(depth[i], i);
	}

	int ret=  0;
	while (!pq.empty()) {
		auto [d, k] = pq.top();
		pq.pop();

		if (centroid_tree_get_nearest_node(k) < min_req) {
			continue;
		}

		ret += 1;
		centroid_tree_add(k);
	}

	std::cout << ret << "\n";
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	read_data();
	build_tree();
	build_centroid_decomp_tree();
	solve();
}

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