Submission #1266979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266979		random_user29	Magic Tree (CEOI19_magictree)	C++20	100 / 100	88 ms	27976 KiB

magictree

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if defined(__GNUC__)
    // nothing special; careful with recursion depth on degenerate tree
#endif

    int n, m, k;
    if (!(cin >> n >> m >> k)) return 0;
    vector<vector<int>> children(n+1);
    for (int i = 2; i <= n; ++i) {
        int p; cin >> p;
        children[p].push_back(i);
    }

    // fruit info: at most one fruit per vertex by statement, but keep vector to be general
    vector<int> fruit_day(n+1, 0);
    vector<ll> fruit_w(n+1, 0);
    for (int i = 0; i < m; ++i) {
        int v, d; ll w; cin >> v >> d >> w;
        fruit_day[v] = d;
        fruit_w[v] = w;
    }

    // dp maps: dp[v] is map<day, value> as described
    vector<map<int,ll>*> dp(n+1, nullptr);

    // We'll do a recursive dfs (postorder). If your tree can be a single long chain of length 1e5,
    // recursion may stack-overflow in some environments. If that's an issue, convert to iterative.
    function<void(int)> dfs = [&](int u) {
        // create base map for u
        dp[u] = new map<int,ll>();

        // merge children
        for (int v : children[u]) {
            dfs(v);
            // small-to-large: ensure dp[u] is the larger
            if (dp[u]->size() < dp[v]->size()) swap(dp[u], dp[v]);
            // merge dp[v] into dp[u]
            for (auto &p : *dp[v]) {
                (*dp[u])[p.first] += p.second;
            }
            // free child's map
            delete dp[v];
            dp[v] = nullptr;
        }

        // if there's a fruit at u, add it (process possible single fruit)
        if (fruit_day[u] != 0) {
            int d = fruit_day[u];
            ll w = fruit_w[u];
            (*dp[u])[d] += w;

            // now apply the greedy "subtract from later days" step:
            ll r = w;
            auto it = dp[u]->upper_bound(d); // first day > d
            while (r > 0 && it != dp[u]->end()) {
                if (it->second <= r) {
                    r -= it->second;
                    auto toerase = it++;
                    dp[u]->erase(toerase);
                } else {
                    it->second -= r;
                    r = 0;
                    break;
                }
            }
        }
    };

    dfs(1);

    // answer is sum of values in dp[1]
    ll ans = 0;
    if (dp[1]) {
        for (auto &p : *dp[1]) ans += p.second;
    }
    cout << ans << '\n';

    // cleanup
    if (dp[1]) delete dp[1];
    return 0;
}

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