Submission #1106768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106768		hengliao	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	43 ms	24352 KiB

catinatree

#include <bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;

const ll mxN=2e5+5;
const ll inf=1e18;

vll adj[mxN];
ll n, x;
ll p[mxN];
ll low[mxN];
ll d[mxN];
ll sum[mxN];

void dfs(ll cur, ll dep){
    d[cur]=dep;
    low[cur]=inf;
    sum[cur]=0;
    for(auto &chd:adj[cur]){
        dfs(chd, dep+1);
        if(low[chd]-dep+low[cur]-dep>=x){
            sum[cur]+=sum[chd];
            low[cur]=min(low[cur], low[chd]);
        }
        else{
            sum[cur]+=sum[chd]-1;
            low[cur]=max(low[cur], low[chd]);
        }
    }
    if(low[cur]-dep>=x){
        sum[cur]++;
        low[cur]=dep;
    }
}

void solve(){
	cin>>n>>x;
    for(ll i=1;i<n;i++){
        cin>>p[i];
        adj[p[i]].pb(i);
    }
    dfs(0, 0);
    cout<<sum[0]<<'\n';
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	solve();
	return 0;
}

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