Submission #1222399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222399		asaf	Cat in a tree (BOI17_catinatree)	C++20	0 / 100	0 ms	320 KiB

catinatree

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, D;
vector<vector<int>> tree;
vector<vector<int>> dp;

void dfs(int node, int parent) {
    dp[node] = vector<int>(D + 2, 0);

    // First process all children
    for (int child : tree[node]) {
        if (child != parent)
            dfs(child, node);
    }

    // Case 1: not marking this node
    for (int d = 0; d < D; ++d) {
        int total = 0;
        for (int child : tree[node]) {
            if (child != parent) {
                total += dp[child][d + 1];
            }
        }
        dp[node][d] = total;
    }

    // Case 2: marking this node (only allowed if distance >= D)
    int total = 1;
    for (int child : tree[node]) {
        if (child != parent) {
            total += dp[child][1]; // if we mark this node, child must be at least distance 1
        }
    }
    dp[node][D] = max(dp[node][D], total);
}

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

    cin >> N >> D;
    tree.assign(N, vector<int>());

    for (int i = 1; i < N; ++i) {
        int x;
        cin >> x;
        tree[x].push_back(i);
        tree[i].push_back(x);
    }

    dp.assign(N, vector<int>());
    dfs(0, -1);

    // The answer is the best among all distances from the root
    cout << *max_element(dp[0].begin(), dp[0].end()) << '\n';
    return 0;
}

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