Submission #440945

#	Time	Username	Problem	Language	Result	Execution time	Memory
440945		S2speed	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	131 ms	23472 KiB

catinatree

#include<bits/stdc++.h>

using namespace std;

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef pair<pll , bool> pllb;

const ll maxn = 2e5 + 16 , md = 1e9 + 7;

ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}
 
ll n , d , sq = 300;
ll par[maxn] , dis[maxn] , cl[maxn] , ds[maxn];
vector<pll> u;
bitset<maxn> far;
vector<ll> bfs , adj[maxn];

void BFS(ll r){
	ds[r] = 0;
	bfs.push_back(r);
	ll x = 0;
	while(x < sze(bfs)){
		ll v = bfs[x++];
		if(ds[v] == d - 1) break;
		for(auto i : adj[v]){
			if(ds[i] > ds[v] + 1){
				ds[i] = ds[v] + 1;
				bfs.push_back(i);
				far[i] = false;
			}
		}
	}
	bfs.clear();
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	memset(cl , 63 , sizeof(cl));
	par[0] = -1; dis[0] = 0;
	cin>>n>>d;
	u.push_back({0 , 0});
	for(ll i = 1 ; i < n ; i++){
		cin>>par[i];
		dis[i] = dis[par[i]] + 1;
		u.push_back({dis[i] , i});
	}
	sort(all(u) , greater<pll>());
	ll ans = 0 , lm = (d - 1) >> 1;
	if(d < sq){
		for(ll e = 0 ; e < n ; e++){
			ll i = u[e].second , v = i;
			bool ch = true;
			for(ll j = 0 ; j <= lm && v != -1 ; j++){
				ch &= (cl[v] + j >= d);
				v = par[v];
			}
			if(!ch) continue;
			ans++;
			v = par[i];
			for(ll j = 1 ; j < d && v != -1 ; j++){
				cl[v] = j;
				v = par[v];
			}
		}
		cout<<ans<<'\n';
		return 0;
	}
	far.set();
	memset(ds , 63 , sizeof(ds));
	for(ll i = 1 ; i < n ; i++){
		adj[i].push_back(par[i]);
		adj[par[i]].push_back(i);
	}
	for(ll e = 0 ; e < n ; e++){
		ll i = u[e].second;
		if(far[i]){
			ans++;
			BFS(i);
		}
	}
	cout<<ans<<'\n';
	return 0;
}

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