Submission #1189973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189973		MisterReaper	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	178 ms	170180 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];
std::vector<int> aux;

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(dp[v][0]);
    if (int(dp[v].size()) > D) {
        dp[v][0] = std::max(dp[v][0], dp[v][D] + 1);
    }
    debug(v, adj[v][0], dp[v]);
    for (auto u : adj[v]) {
        if (u == adj[v][0]) {
            continue;
        }
        int m = int(dp[u].size());
        aux.assign(m + 1, 0);
        for (int i = 0; i <= m; ++i) {
            int T = i, H;
            int mx = dp[v][T];
            H = std::max({0, T - 1, D - T - 1});
            if (int(dp[u].size()) > H) {
                debug("a", T, H, dp[v][T] + dp[u][H]);
                mx = std::max(mx, dp[v][T] + dp[u][H]);
            } 
            H = std::max({0, T, D - T});
            if (T - 1 >= 0 && int(dp[v].size()) > H) {
                debug("b", T, H, dp[v][H] + dp[u][T - 1]);
                mx = std::max(mx, dp[v][H] + dp[u][T - 1]);
            }
            debug(T, mx);
            aux[T] = mx;
        }
        for (int i = 0; i <= m; ++i) {
            dp[v][i] = std::max(dp[v][i], aux[i]);
        }
        for (int i = std::min(m, int(dp[v].size()) - 2); i >= 0; --i) {
            dp[v][i] = std::max(dp[v][i], dp[v][i + 1]);
        }
        debug(v, u, dp[v]);
    }
    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: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49