Submission #924890

#	Time	Username	Problem	Language	Result	Execution time	Memory
924890		Jawad_Akbar_JJ	Cat in a tree (BOI17_catinatree)	C++17	0 / 100	3 ms	12888 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];
}
 

signed  main(){
	int n,d;
	cin>>n>>d;
	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;
		// cout<<i<<" : ";
		for (int v : vec[i]){
			// cout<<v<<" ";
			mn[v] = 1e8;
			for (int j : nei[v])
				mn[v] = min(mn[v],mn[j]);
			int k = mn[v];
			if (k - h[v] < d)
				continue;
			if (lst == 0){
				ans++;
				lst = v;
				mn[v] = h[v];
				continue;
			}
			int l = LCA(lst,v);
			if (h[v] + h[lst] - 2 * h[l] < d)
				continue;
			ans++;
			lst = v;
			mn[v] = h[v];
		}
		// cout<<endl;
	}
	cout<<ans<<endl;

}
// 24
// 1 1 1 2 2 4 4 4 5 6 6 8 8 9 12 12 12 12 13 13 14 15 15

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