Submission #1129909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129909		vladilius	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	603 ms	95928 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, D; cin>>n>>D;
    vector<int> g[n + 1], p(n + 1);
    for (int i = 2; i <= n; i++){
        cin>>p[i]; p[i]++;
        g[p[i]].pb(i);
        g[i].pb(p[i]);
    }
    
    vector<bool> used(n + 1);
    vector<int> sz(n + 1);
    function<void(int, int)> fill_sz = [&](int v, int pr){
        sz[v] = 1;
        for (int i: g[v]){
            if (i == pr || used[i]) continue;
            fill_sz(i, v);
            sz[v] += sz[i];
        }
    };
    
    function<int(int, int, int&)> find = [&](int v, int pr, int& S){
        for (int i: g[v]){
            if (i == pr || used[i]) continue;
            if (2 * sz[i] >= S){
                return find(i, v, S);
            }
        }
        return v;
    };
    
    vector<pii> all[n + 1];
    vector<int> d(n + 1);
    function<void(int, int, int&)> fill = [&](int v, int pr, int& S){
        all[S].pb({d[v], v});
        for (int i: g[v]){
            if (i == pr || used[i]) continue;
            d[i] = d[v] + 1;
            fill(i, v, S);
        }
    };
    
    vector<int> P(n + 1);
    function<void(int, int)> arvid = [&](int v, int k){
        fill_sz(v, 0);
        v = find(v, 0, sz[v]);
        P[v] = k;
        used[v] = 1;
        
        d[v] = 0;
        fill(v, 0, v);
        
        sort(all[v].begin(), all[v].end());
        
        for (int i: g[v]){
            if (used[i]) continue;
            arvid(i, v);
        }
    };
    arvid(1, 0);
    
    const int lg = log2(n);
    vector<vector<int>> pw(n + 1, vector<int>(lg + 1));
    vector<int> tin(n + 1), tout(n + 1);
    int timer = 0;
    function<void(int, int)> dfs = [&](int v, int pr){
        tin[v] = ++timer;
        pw[v][0] = pr;
        for (int i = 1; i <= lg; i++){
            pw[v][i] = pw[pw[v][i - 1]][i - 1];
        }
        for (int i: g[v]){
            if (i == pr) continue;
            d[i] = d[v] + 1;
            dfs(i, v);
        }
        tout[v] = timer;
    };
    
    d[1] = 0; dfs(1, 1);
    
    set<pii> st;
    for (int i = 1; i <= n; i++){
        st.insert({d[i], i});
    }
    
    vector<bool> ban(n + 1);
    vector<int> ii(n + 1);
    
    auto rem = [&](int v){
        ban[v] = 1;
        st.erase({d[v], v});
    };
    
    auto check = [&](int x, int y){
        return (tin[x] <= tin[y] && tout[x] >= tout[y]);
    };
    
    auto lca = [&](int x, int y){
        if (check(x, y)) return x;
        if (check(y, x)) return y;
        for (int i = lg; i >= 0; i--){
            if (!check(pw[x][i], y)){
                x = pw[x][i];
            }
        }
        return pw[x][0];
    };
    
    auto dist = [&](int x, int y){
        return d[x] + d[y] - 2 * d[lca(x, y)];
    };
    
    int out = 0;
    while (!st.empty()){
        auto [x, y] = *prev(st.end());
        int v = y;
        while (v > 0){
            int d = dist(y, v);
            while (ii[v] < all[v].size()){
                auto [dd, y] = all[v][ii[v]];
                if (ban[y]){
                    ii[v]++;
                    continue;
                }
                if ((d + dd) < D){
                    rem(y);
                    ii[v]++;
                    continue;
                }
                break;
            }
            v = P[v];
        }
        
        out++;
    }
    
    cout<<out<<"\n";
}

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