Submission #964050

#	Time	Username	Problem	Language	Result	Execution time	Memory
964050		ezzzay	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	93 ms	24764 KiB

catinatree

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=2e5+5;
vector<int>v[N];
int dp[N];
int dst[N];
bool vis[N];

int n,d;
void dfs(int a){
    vis[a]=1;
    int mx=1e9,cnt=0;
    for(auto b:v[a]){
        if(vis[b])continue;
        dfs(b);
        if(mx+dst[b]>=d){
            cnt+=dp[b];
            mx=min(mx,dst[b]);
        }
        else{
            cnt+=dp[b]-1;
            mx=max(mx,dst[b]);
        }
    }
    if(mx>=d){
        dst[a]=1;
        dp[a]=cnt+1;
    }
    else{
        dst[a]=mx+1;
        dp[a]=cnt;
    }
}
signed main(){
    cin>>n>>d;
    for(int i=1;i<n;i++){
        int a;
        cin>>a;
        v[a].pb(i);
        v[i].pb(a);
    }
    dfs(0);
    cout<<dp[0];
}

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