Submission #415298

#	Time	Username	Problem	Language	Result	Execution time	Memory
415298		Blagojce	Cat in a tree (BOI17_catinatree)	C++11	100 / 100	582 ms	54152 KiB

catinatree

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;

mt19937 _rand(time(NULL));
const int mxn = 2e5;

int n, d;

vector<int> g[mxn];

int sub[mxn];
bool deleted[mxn];

int cn;

int dep[mxn];
int sparse[mxn][19];

void dfs(int u, int p){
	sparse[u][0] = p;
	fr(i, 1, 19) sparse[u][i] = sparse[sparse[u][i-1]][i-1];
	for(auto e : g[u]){
		if(e == p) continue;
		dep[e] = dep[u] + 1;
		dfs(e, u);
	}
}

void dfs0(int u, int p){
	sub[u] = 1;
	for(auto e : g[u]){
		if(e == p || deleted[e]) continue;
		dfs0(e, u);
		sub[u] += sub[e];
	}
}

int dfs1(int u, int p){
	for(auto e : g[u]){
		if(e == p || deleted[e]) continue;
		if(sub[e] > cn /2) return dfs1(e, u);
	}
	return u;
}
int current_dep;

int pre[mxn][19];



void dfs2(int u, int p){
	for(auto e : g[u]){
		if(e == p || deleted[e]) continue;
		pre[e][current_dep] = pre[u][current_dep] + 1;
		dfs2(e, u);
	}
}


int link[mxn];

int cdep[mxn];

void decompose(int u, int p, int d){
	dfs0(u, u);
	cn = sub[u];
	int cen = dfs1(u, u);
	link[cen] = p;
	
	current_dep = d;
	cdep[cen] = d;
	pre[cen][d] = 0;
	dfs2(cen, cen);
	
	deleted[cen] = true;
	for(auto e : g[cen]){
		if(!deleted[e]){
			decompose(e, cen, d + 1);
		}
	}
}

int lca(int a, int b){
	int d = min(dep[a], dep[b]);
	for(int i = 18; i >= 0; i --){
		if(dep[a] - (1<<i) >= d){
			a = sparse[a][i];
		}
		if(dep[b] - (1<<i) >= d){
			b = sparse[b][i];
		}
	}
	if(a == b) return a;
	
	for(int i = 18; i >= 0; i--){
		if(sparse[a][i] != sparse[b][i]){
			a = sparse[a][i];
			b = sparse[b][i];
		}
	}
	return sparse[a][0];
}

int minw[mxn];


bool check(int u){
	int x = u;
	while(x != -1){
		//optimization : 
		int w = minw[x] + pre[u][cdep[x]];
		
		//slow version : 
		//int w = minw[x] + dep[x] + dep[u] - 2*dep[lca(x, u)];
		
		if(w < d) return false;
		
		x = link[x];
	}
	return true;
}
void update(int u){
	int x = u;
	while(x != -1){
		//optimization : 
		int w = pre[u][cdep[x]];
		
		
		//slow version : 
		//int w = dep[x] + dep[u] - 2*dep[lca(x, u)];
		
		minw[x] = min(minw[x], w);
		x = link[x];
	}
}

void solve(){
	cin >> n >> d;
	fr(i, 1, n){
		int x;
		cin >> x;
		g[i].pb(x);
		g[x].pb(i);
	}
	dfs(0, 0);
	decompose(0, -1, 0);
	vector<int> v;
	fr(i, 0, n) v.pb(i);
	sort(all(v), [](const int &i, const int &j){
		return dep[i] > dep[j];
	});
	fr(i, 0, n){
		minw[i] = 1e9;
	}
	int ans = 0;
	for(auto u : v){
		if(check(u)){
			update(u);
			++ans;
		}
	}
	cout<<ans<<endl;
}

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

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