Submission #1282731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282731		mlecio	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	184 ms	36716 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
const int maxN=2e5+1;
vector<int>Ver[maxN];
bool kil[maxN];
int n,d;
int sz[maxN],h[maxN],p[maxN],dp[20][maxN],va[maxN],dist[maxN];
int dfs_sz(int u,int v){
    sz[u]=1;
    for(auto &x:Ver[u]){
        if(!kil[x] && x!=v)
        sz[u]+=dfs_sz(x,u);
    }
    return sz[u];
}
void dist1(int u,int v){
    for(auto &x:Ver[u]){
        if(x!=v){
            dist[x]=dist[u]+1;
            dist1(x,u);
        }
    }
}
void napraw(int x){
    for(int i=x;i!=-1;i=p[i]){
        va[i]=min(va[i],dp[h[i]][x]);
    }
}
int get(int x){
    int wyn=1e9+697;
    for(int i=x;i!=-1;i=p[i]){
        wyn=min(wyn,dp[h[i]][x]+va[i]);
    }
    return wyn;
}
int cent(int u,int v,int nk){
    for(auto &x:Ver[u]){
        if(!kil[x]&&x!=v&&sz[x]*2>nk)
            return cent(x,u,nk);
    }
    return u;
}
void dfs(int poziom,int u,int v){
    for(auto &x:Ver[u]){
        if(!kil[x] && x!=v){
            dp[poziom][x]=dp[poziom][u]+1;
            dfs(poziom,x,u);
        }
    }
}
void centroid(int u,int poziom,int v){
    int r=cent(u,-1,dfs_sz(u,-1));
    kil[r]=1;
    h[r]=poziom;
    p[r]=v;
    va[r]=1e9;
    dp[poziom][r]=0;
    dfs(poziom,r,-1);
    for(auto &x:Ver[r]){
        if(!kil[x])
        centroid(x,poziom+1,r);
    }

}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>d;
    for(int i=1;i<n;i++){
        int x;
        cin>>x;
        Ver[x].push_back(i);
        Ver[i].push_back(x);
    }
    fill_n(p, maxN, -1);
    fill_n(va, maxN, 1000000000);
    centroid(0,0,-1);
    dist[0]=0;
    dist1(0,-1);
    vector<int>ans(n);
    iota(ans.begin(),ans.end(),0);
    sort(ans.begin(),ans.end(),[&](int a,int b){
        return dist[a]>dist[b];
    });
    int wyn=0;
    for(auto &x:ans){
        if(get(x)>=d){
            wyn++;
            napraw(x);
        }
    }
    cout<<wyn;
}

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