제출 #1189962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1189962		MisterReaper	Cat in a tree (BOI17_catinatree)	C++20	0 / 100	72 ms	139676 KiB

catinatree

// File 1752.cpp created on 22.04.2025 at 10:44:08
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int max_N = int(2E5) + 5;

int N, D;
std::vector<int> adj[max_N];
std::deque<int> dp[max_N];

void dfs(int v) {
    for (auto& u : adj[v]) {
        dfs(u);
        if (dp[u].size() > dp[adj[v][0]].size()) {
            std::swap(u, adj[v][0]);
        }
    }
    if (adj[v].empty()) {
        dp[v].emplace_back(1);
        return;
    }
    std::swap(dp[v], dp[adj[v][0]]);
    dp[v].emplace_front(1);
    if (int(dp[v].size()) >= D + 1) {
        dp[v][0] = dp[v][D] + 1;
    }
    for (auto u : adj[v]) {
        if (u == adj[v][0]) {
            continue;
        }
        int m = int(dp[u].size());
        for (int i = m - 1; i >= 0; --i) {
            int T = i, H;
            int mx = dp[v][T];
            H = std::max(T, D - T - 1);
            if (int(dp[u].size()) > H) {
                mx = std::max(mx, dp[v][T] + dp[u][H]);
            } 
            H = std::max(T, D - T - 1);
            if (int(dp[v].size()) > H) {
                mx = std::max(mx, dp[v][H] + dp[u][T]);
            }
            dp[v][T] = mx;
        }
        for (int i = std::min(m - 1, int(dp[v].size()) - 2); i >= 0; --i) {
            dp[v][i] = std::max(dp[v][i], dp[v][i + 1]);
        }
    }
    debug(v, dp[v]);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> N >> D;
    for (int i = 1; i < N; ++i) {
        int X;
        std::cin >> X;
        adj[X].emplace_back(i);
    }

    dfs(0);

    auto dp0 = dp[0];
    std::cout << dp0[0] << '\n';

    return 0;
}

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