Submission #1122165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122165		ezdp	Cat in a tree (BOI17_catinatree)	C++14	51 / 100	1062 ms	434780 KiB

catinatree

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

const int BLOCK = 333;
const int MAXN = 5e5;
const int MAXL = 20;

template<class T> using matrix = vector<vector<T>>;

int n, d, depths[MAXN + 5], block[MAXN + 5], first[MAXN + 5], last[MAXN + 5], sparse[MAXN + 5][MAXL], lg2[2 * MAXN + 5], T = 1, euler[2 * MAXN + 5], used[MAXN + 5];
priority_queue<pair<int, int>> pq; vector<int> vq;
matrix<int> G;

void dfs_depths(int u, int p, int d){
	depths[u] = d;
	euler[T] = u; last[u] = first[u] = T ++;
	for(auto v : G[u]){
		if(v == p) continue;
		dfs_depths(v, u, d + 1);
		euler[T] = u; last[u] = T ++;
	}
}

void init(){
	lg2[1] = 0;
	for(int i = 2; i <= T; i ++){
		lg2[i] = lg2[i / 2] + 1;
	}
	for(int i = 1; i < T; i ++){
		sparse[i][0] = euler[i];
	}
	for(int l = 1; l <= MAXL; l ++){
		for(int i = 1; i + (1 << l) - 1 <= T; i ++){
			int u = sparse[i][l - 1];
			int v = sparse[i + (1 << (l - 1))][l - 1];
			sparse[i][l] = (depths[u] < depths[v] ? u : v);
		}
	}
}

int get_lca(int u, int v){
	if(first[u] > first[v]) swap(u, v);
	u = first[u]; v = last[v];
	int j = lg2[v - u + 1];
	int a = sparse[u][j];
	int b = sparse[v - (1 << j) + 1][j];
	return (depths[a] > depths[b] ? b : a);
}

int get_dist(int u, int v){
	int c = get_lca(u, v);
	return depths[u] + depths[v] - 2 * depths[c];
}

void bfs(){
	for(int i = 0; i < n; i ++){
		used[i] = block[i] = 0;
	}
	queue<int> qq;
	for(auto x : vq){
		block[x] = d;
		qq.push(x);
	}
	while(!qq.empty()){
		auto u = qq.front(); qq.pop();
		if(!block[u]) continue;
		used[u] = true;
		for(auto v : G[u]){
			block[v] = max(block[v], block[u] - 1);
			if(!used[v]) qq.push(v);
		}
	}
}

int main(){
	cin >> n >> d;
	G.resize(n + 1);
	for(int i = 1; i < n; i ++){
		int p; cin >> p;
		G[p].push_back(i);
		G[i].push_back(p);
	}
	dfs_depths(0, 0, 0);
	init();
	for(int i = 0; i < n; i ++){
		pq.push({depths[i], i});
	}
	int ans = 0;
	queue<int> q;
	vector<int> cache;
	while(!pq.empty()){
		auto [_, u] = pq.top(); pq.pop();
		bool good = (block[u] ? false : true);
		for(auto x : cache){
			good &= (get_dist(u, x) >= d);
		}
		if(good){
			++ ans;
			cache.push_back(u);
		}
		if(cache.size() == BLOCK){
			for(auto x : cache) vq.push_back(x);
			cache.clear();
			bfs();
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

catinatree.cpp: In function 'int main()':
catinatree.cpp:92:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |   auto [_, u] = pq.top(); pq.pop();
      |        ^

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