Submission #1279294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279294		MisterReaper	Magic Tree (CEOI19_magictree)	C++20	6 / 100	564 ms	1114112 KiB

magictree

// File magictree.cpp created on 14.10.2025 at 21:08:14
#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(1E5) + 5;

int N, M, K;
int P[max_N];
int D[max_N];
int W[max_N];

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

    std::cin >> N >> M >> K;

    for (int i = 1; i < N; ++i) {
        std::cin >> P[i];
        --P[i];
    }

    for (int i = 0; i < M; ++i) {
        int V;
        std::cin >> V;
        --V;
        std::cin >> D[V] >> W[V];
        --D[V];
    }

    std::vector<std::vector<i64>> f(N, std::vector<i64>(K));

    for (int v = N - 1; v >= 1; --v) {
        if (D[v] != -1) {
            f[v][D[v]] += W[v];
            for (int i = 1; i < K; ++i) {
                f[v][i] = std::max(f[v][i], f[v][i - 1]);
            }
        }
        debug(v, f[v]);
        for (int i = 0; i < K; ++i) {
            f[P[v]][i] += f[v][i];
        }
    }

    i64 ans = f[0][K - 1];

    std::cout << ans << '\n';

    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17