Submission #924886

#	Time	Username	Problem	Language	Result	Execution time	Memory
924886		Jawad_Akbar_JJ	Cat in a tree (BOI17_catinatree)	C++17	0 / 100	5 ms	12892 KiB

catinatree

#include <iostream>
#include <vector>

using namespace std;
const int N = 2e5+10,lg = 20;
vector<int> nei[N],vec[N];
int par[N][lg];
int h[N],mn[N];
bool seen[N],marked[N];

void dfs(int u,int p = 0){
	par[u][0]=p;
	h[u] = h[p] + 1;

	vec[h[u]].push_back(u);

	for (int i=1;i<lg;i++)
		par[u][i] = par[par[u][i-1]][i-1];
	for (int i : nei[u])
		if (i!=p)
			dfs(i,u);
}

int move_up(int v,int d){
	for (int i=lg;i>=0;i--)
		if ((1<<i)&d)
			v = par[v][i];
	return v;
}

int LCA(int u,int v){
	if (h[u]>h[v])
		swap(u,v);
	if (h[v]>h[u])
		v = move_up(v,h[v]-h[u]);
	if (v==u)
		return v;
	for (int i=lg-1;i>=0;i--){
		if (par[u][i]!=par[v][i]){
			u = par[u][i];
			v = par[v][i];
		}
	}
	return par[v][0];
}

void MN(int u){
	// if (seen[u])
	// 	return mn[u];
	if (marked[u]){
		mn[u] = h[u];
		return;
	}
	mn[u] = 1e8;
	for (int i : nei[u]){
		MN(i);
		// seen[i] = true;
		mn[u] = min(mn[u],mn[i]);
	}
} 

signed  main(){
	int n,d;
	cin>>n>>d;

	for (int i=2;i<=n;i++){
		int p;
		cin>>p;
		nei[p+1].push_back(i);
	}
	dfs(1);
	int ans = 0;
	for (int i=n;i>=1;i--){
		int lst = 0;
		for (int v : vec[i]){
			MN(v);
			int k = mn[v];
			if (k - h[v] < d)
				continue;
			if (lst == 0){
				marked[v] = true;
				ans++;
				lst = v;
				continue;
			}
			int l = LCA(lst,v);
			if (h[v] + h[lst] - 2 * h[l] < d)
				continue;
			ans++;
			marked[v] = true;
			lst = v;
		}
	}
	cout<<ans<<endl;

}

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