Submission #1271719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271719		Davdav1232	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	427 ms	73080 KiB

catinatree

// Source: https://usaco.guide/general/io
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
 
int MAX_N=2e5+2;
int n, d;
vector<bool> vis_centroid(MAX_N, 0);
vvi G(MAX_N);
vi sz(MAX_N);
ll ans=0;
vi dep(MAX_N);
vvi anc(MAX_N, vi(20));
int t=0;
vi tin(MAX_N), tout(MAX_N);

void dfs1(int node, int p){
    t++;
    tin[node]=t;
    if(p==-1) dep[node]=0;
    else dep[node]=dep[p]+1;
    anc[node][0]=p;
    if(p!=-1){
        int r=0;
        while(anc[anc[node][r]][r]!=-1){
            anc[node][r+1]=anc[anc[node][r]][r];
            r++;
        }
        while(r<19){
            anc[node][r+1]=-1;
        }
    }
    for(int nei : G[node]){
        if(nei == p) continue;
        dfs1(nei, node);
    }
    t++;
    tout[node]=t;
}

bool is_anc(int u, int v){
    return (tin[u]<=tin[v] && tout[u]>=tout[v]);
}

int lca(int u, int v){
    if(is_anc(u, v)) return u;
    int r=20;
    while(r>=1){
        r--;
        if(anc[u][r]==-1 || is_anc(anc[u][r], v)) continue;
        u=anc[u][r];
    }
    return anc[u][0];
}
int distance(int u, int v){
    return dep[u]+dep[v]-2*dep[lca(u, v)];
}
 
int dfs(int node, int p=-1){
    sz[node]=1;
    for(int neighbor : G[node]){
        if(neighbor==p || vis_centroid[neighbor]) continue;
        sz[node]+=dfs(neighbor, node);
    }
    return sz[node];
}
int find_centroid(int root){
    dfs(root);
    int node=root;
    int p=-1;
    while(true){
        bool ok=0;
        for(int neighbor : G[node]){
            if(neighbor==p || vis_centroid[neighbor]) continue;
            if(2*sz[neighbor]>sz[root]){
                p=node;
                node=neighbor;
                ok=1;
                break;
            }
        }
        if(!ok) break;
    }
    return node;
}
vi par(MAX_N);
vi dist(MAX_N, 1e9);
int root;
vvi distances(MAX_N);

int centroid_decomposition(int node){
    int c=find_centroid(node);
    vis_centroid[c]=1;
    for(int neighbor: G[c]){
        //find the number of paths of length k that pass through c
        if(vis_centroid[neighbor]) continue;
        par[centroid_decomposition(neighbor)]=c;
    }
    return c;
}

void mark(int node){
    int u=node;
    int i=0;
    while(u!=-1){
        if(distances[node][i]+dist[u]<d) return;
        u=par[u];
        i++;
    }
    ans++;
    u=node;
    i=0;
    while(u!=-1){
        dist[u]=min(dist[u], distances[node][i]);
        u=par[u];
        i++;
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	cin>>n>>d;
	for(int i=1; i<n; i++){
        int a;
        cin>>a;
        int b=i;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for (int i=0; i<n; i++){
    for (int j=0; j<20; j++){
        anc[i][j] = -1;}}
    dfs1(0, -1);
    root=centroid_decomposition(0);
    par[root]=-1;
    
    vector<pair<int, int>> depths;
    for(int i=0; i<n; i++){
        depths.push_back({dep[i], i});
    }
    sort(depths.begin(), depths.end());
    for(int i=0; i<n; i++){
        int u=i;
        while(u!=-1){
            distances[i].push_back(distance(i, u));
            u=par[u];
        }
    }
    for(int i=n-1; i>=0; i--){
        mark(depths[i].second);
    }
    cout<<ans;
    return 0;
 
}

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