Submission #347199

#	Time	Username	Problem	Language	Result	Execution time	Memory
347199		soroush	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	500 ms	26476 KiB

catinatree

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn = 2e5 + 100;
const ll mod = 1e9+7;
const ld PI = acos((ld)-1);

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n , d;
vector < int > adj[maxn];
int h[maxn] , srt[maxn];
int par[maxn] , l[maxn] , r[maxn] , tim = 0;

int seg[maxn * 4];
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)

int near[maxn];
int ord[maxn];

const int inf = 1e9;

void dfs(int v , int p = 0){
	par[v] = p;
	l[v] = tim + 1;
	tim = tim + 1;
	ord[tim] = v;
	for(int u : adj[v])if(u!=p)
		h[u] = h[v] + 1 , dfs(u , v);
	r[v] = tim;
}

bool comp(int i , int j){
	return(h[i] > h[j]);
}

void build(int v = 1 , int l = 1 , int r = maxn){
	if(r - l == 1){
		seg[v] = inf;
		return;
	}
	build(lc , l , mid);
	build(rc , mid , r);
	seg[v] = min(seg[lc] , seg[rc]);
}

void update(int L , int R , int x , int v = 1 , int l = 1 , int r = maxn){
	if(R <= l or r <= L)
		return;
	if(L <= l and r <= R){
		seg[v] = min(seg[v] , x);
		return;
	}
	update(L , R , x , lc , l , mid);
	update(L , R , x , rc , mid , r);
}

int query(int x , int v = 1 , int l = 1 , int r = maxn){
	int ans = seg[v];
	for(; r - l > 1;){
		if(x < mid)
			v = lc , r = mid;
		else
			v = rc , l = mid;
		ans = min(ans , seg[v]);
	}
	return(ans);
}

int32_t main(){
    migmig;
	cin >> n >> d;
	for(int i = 2 ; i <= n ; i ++){
		int x;
		cin >> x;
		adj[x + 1].pb(i);
		adj[i].pb(x+1);
	}
	dfs(1);
	h[0] = -1;
	for(int i = 1 ; i <= n ; i ++)	
		srt[i] = i , near[i] = inf;
	build();
	sort(srt + 1 , srt + n + 1 , comp);
	int ans = 0;
	for(int i = 1 ; i <= n ; i ++){
		int v = srt[i];
		if(l[v] > n or l[v] < 1)continue;
		if(query(l[v]) + h[v] < d)continue;
		ans++;
		int p = v;
		for( ; v ; ){
			near[v] = min(near[v] , h[p]);
			update(l[v] , r[v] + 1 , near[v] - 2*h[v]);
			v = par[v];
		}
	}
	cout << ans;
    return(0);
}

Compilation message (stderr)

catinatree.cpp:1: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    1 | #pragma comment(linker, "/stack:200000000")
      |

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