Submission #1129865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129865		vladilius	Cat in a tree (BOI17_catinatree)	C++20	0 / 100	0 ms	320 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
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);
    }
    
    int k = ceil(1.0 * n / d);
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, infm));
    function<void(int)> dfs = [&](int v){
        for (int i: g[v]){
            dfs(i);
        }
        
        int sm = 1;
        for (int i: g[v]){
            for (int j = k; j >= 0; j--){
                if (dp[i][j] >= (d - 1)){
                    sm += j;
                    break;
                }
            }
            for (int j = 0; j <= k; j++){
                if (dp[i][j] == infm) continue;
                int x = dp[i][j], y = max(x, d - x - 2), sum = j;
                for (int t: g[v]){
                    if (t == i) continue;
                    for (int p = k; p >= 0; p--){
                        if (dp[t][p] >= y){
                            sum += p;
                            break;
                        }
                    }
                }
                dp[v][sum] = max(dp[v][sum], x + 1);
            }
        }
        dp[v][sm] = max(dp[v][sm], 0);
        dp[v][0] = 1e9;
    };
    dfs(1);
    
    for (int j = k; j >= 0; j--){
        if (dp[1][j] != infm){
            cout<<j<<"\n";
            return 0;
        }
    }
}

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