제출 #643083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
643083		two_sides	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	364 ms	408900 KiB

catinatree

#include <bits/stdc++.h>

using namespace std;

template <class X, class Y>
bool cmax(X &a, const Y &b) {
    return a < b ? a = b, 1 : 0;
}

const int N = 2e5 + 5;
const int D = 500;

int dp[N][D], n, d, siz[N];
vector<int> adj[N];

void dfs1(int u) {
    dp[u][0] = 1;
    for (int v : adj[u]) {
        dfs1(v);
        for (int i = 0; i <= d; i++)
            cmax(dp[u][i], max(dp[v][max(i, d - i)] +
            dp[u][i], dp[v][i] + dp[u][max(i, d - i)]));
    }
    for (int i = d; i >= 0; i--)
        dp[u][i + 1] = dp[u][i];
    for (int i = d; i >= 0; i--)
        cmax(dp[u][i], dp[u][i + 1]);
}

void dfs2(int u) {
    dp[u][0] = d - 1; dp[u][1] = 0;
    for (int v : adj[u]) {
        dfs2(v); siz[u] += siz[v] + 1;
        for (int i = siz[u] / d + 1; i >= 0; i--)
            for (int j = min(i, siz[v] / d + 1); j >= 0; j--)
                if (dp[u][i - j] + dp[v][j] + 1 >= d)
                    cmax(dp[u][i], min(dp[u][i - j], dp[v][j] + 1));
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> d;
    for (int i = 1; i < n; i++) {
        int p; cin >> p; adj[p].push_back(i);
    }
    
    if (d + 1 < D) {
        dfs1(0); cout << dp[0][0];
    } else {
        memset(dp, 0xc0, sizeof dp); dfs2(0);
        for (int i = D - 1; i >= 0; i--)
            if (dp[0][i] >= 0) {
                cout << i; break;
            }
    }
}

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