Submission #1279301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279301		MisterReaper	Magic Tree (CEOI19_magictree)	C++20	71 / 100	178 ms	37472 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];

std::set<std::pair<int, i64>> ss[max_N];

void merge(std::set<std::pair<int, i64>>& lhs, std::set<std::pair<int, i64>>& rhs) {
    if (lhs.size() < rhs.size()) {
        std::swap(lhs, rhs);
    }
    for (auto[d, x] : rhs) {
        auto it = lhs.upper_bound({d, -1});
        if (it == lhs.end() || it->first != d) {
            lhs.emplace(d, x);
        } else {
            i64 nx = it->second + x;
            lhs.erase(it);
            lhs.emplace(d, nx);
        }
    }
}

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];
    }

    for (int i = N - 1; i >= 1; --i) {
        if (D[i] != 0) {
            i64 now = 0;
            auto it = ss[i].lower_bound({D[i], -1});
            if (it != ss[i].end() && it->first == D[i]) {
                now += it->second;
                W[i] += it->second;
                it = ss[i].erase(it);
            }
            while (true) {
                if (it == ss[i].end()) {
                    ss[i].emplace(D[i], W[i]);
                    break;
                }
                if (now + it->second >= W[i]) {
                    auto[dit, xit] = *it;
                    ss[i].erase(it);
                    ss[i].emplace(dit, now + xit - W[i]);
                    ss[i].emplace(D[i], W[i]);
                    break;
                } else {
                    now += it->second;
                    it = ss[i].erase(it);
                }
            }
        }
        debug(i, ss[i]);
        merge(ss[P[i]], ss[i]);
    }

    i64 ans = 0;
    for (auto[d, w] : ss[0]) {
        ans += w;
    }

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

    return 0;
}

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