Submission #1129845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129845		vladilius	Cat in a tree (BOI17_catinatree)	C++20	11 / 100	1 ms	836 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 arr4 array<int, 4>
const int infm = -1e9;

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];
    for (int i = 2; i <= n; i++){
        int p; cin>>p; p++;
        g[p].pb(i);
    }
    
    const int S = 500;

    if (d <= S){
        vector<vector<int>> dp(n + 1, vector<int>(d));
        function<void(int)> dfs = [&](int v){
            for (int i: g[v]){
                dfs(i);
            }
            
            dp[v][0] = 1;
            for (int i: g[v]) dp[v][0] += dp[i][d - 1];
            for (int x = 1; x < d; x++){
                int sum = 0;
                for (int i: g[v]){
                    sum += dp[i][max(x - 1, d - x - 1)];
                }
                for (int i: g[v]){
                    dp[v][x] = max(dp[v][x], (sum - dp[i][max(x - 1, d - x - 1)]) + dp[i][x - 1]);
                }
            }
            for (int i = d - 2; i >= 0; i--){
                dp[v][i] = max(dp[v][i], dp[v][i + 1]);
            }
        };
        dfs(1);
        
        cout<<dp[1][0]<<"\n";
        return 0;
    }
    
    int k = ceil(1.0 * n / d) + 1;
    vector<vector<int>> dp(n + 1, vector<int>(k, infm));
    vector<int> f(n + 1);
    function<void(int)> dfs = [&](int v){
        for (int i: g[v]){
            dfs(i);
        }
        
        vector<arr4> all;
        for (int i: g[v]){
            for (int j = 0; j < k; j++){
                if (dp[i][j] == infm) continue;
                int x = dp[i][j], y = max(x, d - x - 2);
                all.pb({x, i, 0, j});
                all.pb({y, -i, x, j});
            }
        }
        
        auto cmp = [&](arr4 x, arr4 y){
            if (x[0] != y[0]) return x[0] > y[0];
            return x[1] > y[1];
        };
        
        sort(all.begin(), all.end(), cmp);
        
        int sum = 0;
        for (auto [x, y, t, vv]: all){
            if (y > 0){
                sum -= f[y];
                f[y] = vv;
                sum += f[y];
            }
            else {
                y = -y;
                int val = vv + sum - f[y];
                dp[v][val] = max(dp[v][val], t + 1);
            }
        }
        
        for (int i = k - 2; i >= 0; i--){
            dp[v][i] = max(dp[v][i], dp[v][i + 1]);
        }
        dp[v][1] = max(dp[v][1], 0);
        dp[v][0] = d;
        
        for (int i: g[v]) f[i] = 0;
    };
    dfs(1);
    
    for (int i = k - 1; i >= 0; i--){
        if (dp[1][i] != infm){
            cout<<i<<"\n";
            return 0;
        }
    }
}

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