Submission #1304360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304360		bearrbearr	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	247 ms	39240 KiB

catinatree

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")

const int maxn=2e5;
int n,d;
vector<int>adj[maxn+2];
int bin[maxn+2][19],dep[maxn+2];
vector<pair<int,int> >ord;

void dfs(int cur,int p){
    bin[cur][0]=p;
    dep[cur]=dep[p]+1;
    ord.push_back({dep[cur],cur});

    for(auto x : adj[cur]){
        if(x==p)continue;
        dfs(x,cur);
    }
}

int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    int slsh=dep[u]-dep[v];
    for(int q=18;q>=0;q--){
        if(slsh>=(1<<q)){
            u=bin[u][q]; slsh-=(1<<q);
        }
    }

    if(u==v)return u;
    for(int q=18;q>=0;q--){
        if(bin[u][q]!=bin[v][q]){
            u=bin[u][q]; v=bin[v][q];
        }
    }
    return bin[u][0];
}

int jrk(int u,int v){
    return dep[u]+dep[v]-2*dep[lca(u,v)];
}

int par[maxn+2],sub[maxn+2];
bool vis[maxn+2];

void build(int cur,int p){
    sub[cur]=1;
    for(auto x : adj[cur]){
        if(x==p || vis[x])continue;
        build(x,cur);
        sub[cur]+=sub[x];
    }
}

int centro(int cur,int par,int sz){
    for(auto x : adj[cur]){
        if(x==par || vis[x])continue;
        if(sub[x]>=sz/2)return centro(x,cur,sz);
    }
    return cur;
}

void solve(int cur,int prv){
    build(cur,0);
    int root=centro(cur,0,sub[cur]);
    vis[root]=true; par[root]=prv;

    for(auto x : adj[root]){
        if(vis[x])continue;
        solve(x,root);
    }
}

int mn[maxn+2];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>d;
    for(int q=1;q<=n;q++)mn[q]=1e9;

    for(int q=2;q<=n;q++){
        int pp; cin>>pp; pp++;
        adj[pp].push_back(q);
        adj[q].push_back(pp);
    }
    dfs(1,0); sort(ord.rbegin(),ord.rend());

    for(int q=1;q<19;q++){
        for(int w=1;w<=n;w++){
            bin[w][q]=bin[bin[w][q-1]][q-1];
        }
    }

    solve(1,0);
    int ans=0;

    for(auto [brp,node] : ord){
        bool ok=true;
        int cur=node;
        
        vector<int>hmm;
        while(cur!=0){
            int apa=jrk(cur,node);
            if(mn[cur]+apa<d){
                ok=false; break;
            }
            hmm.push_back(apa);
            cur=par[cur];
        }
        
        if(!ok)continue;
        ans++;

        cur=node;
        int cnt=0;
        while(cur!=0){
            int apa=hmm[cnt];
            mn[cur]=min(mn[cur],apa);
            cur=par[cur];
            cnt++;
        }
    }   
    cout<<ans<<endl;

}

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