제출 #1177012

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177012		xnqs	Cat in a tree (BOI17_catinatree)	C++20	51 / 100	1095 ms	43920 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 up[18][200005];
int depth[200005];

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);
	}
}

void build_tree() {
	const std::function<void(int,int)> dfs = [&](int k, int p) {
		depth[k] = ((p==-1) ? 1 : depth[p]+1);
		up[0][k] = p;
		for (int i = 1; i < 18; i++) {
			up[i][k] = ((depth[k]-(1<<i)>0) ? up[i-1][up[i-1][k]] : -1);
		}

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

	dfs(0, -1);
}

int get_kth_ancestor(int node, int k) {
	while (k) {
		int l = 31-__builtin_clz(k);
		node = up[l][node];
		k ^= (1<<l);
	}
	return node;
}

int get_lca(int a, int b) {
	if (depth[a]>depth[b]) {
		std::swap(a,b);
	}

	b = get_kth_ancestor(b, depth[b]-depth[a]);
	for (int lvl = 17; a != b;) {
		while (lvl-1>=0&&up[lvl][a]==up[lvl][b]) {
			--lvl;
		}

		a = up[lvl][a];
		b = up[lvl][b];
	}

	return a;
}

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)> dfs_find_cen = [&](int k, int p) {
		for (const auto& i : adj_list[k]) {
			if (i!=p&&!used[i]&&sub_sz[i]>sub_sz[k]/2) {
				return dfs_find_cen(i,k);
			}
		}
		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);
		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: 0 / 49