Submission #1186691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186691		hikari1234	Cat in a tree (BOI17_catinatree)	C++20	0 / 100	103 ms	209432 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 3e5 + 5;
vector<int> tree[N];
deque<int> dp[N];
int d;

void dfs(int u) {
    dp[u].push_front(1);  // Base case: selecting the node itself
    for (int v : tree[u]) {
        dfs(v);

        // Shift child's DP because we are moving one level up
        dp[v].push_front(dp[v][0]);

        // Ensure dp[u] is the larger deque (small-to-large trick)
        if (dp[v].size() > dp[u].size()) swap(dp[u], dp[v]);

        // Merge dp[v] into dp[u]
        for (int i = 0; i < dp[v].size(); ++i) {
            int p = max(i, d - i);
            if (p < dp[u].size()) {
                dp[u][i] = max(dp[u][i], dp[u][i] + dp[v][p]);
                dp[u][i] = max(dp[u][i], dp[u][p] + dp[v][i]);
            }
        }

        // Maintain suffix max: dp[u][i] ≥ dp[u][i+1]
        for (int i = dp[v].size() - 2; i >= 0; --i) {
            dp[u][i] = max(dp[u][i], dp[u][i + 1]);
        }
    }
}

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

    int n;
    cin >> n >> d;

    for (int i = 2; i <= n; ++i) {
        int p;
        cin >> p;
        tree[p].push_back(i);
    }

    dfs(1);
    cout << dp[1][0] << '\n';
}

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