Submission #1236542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236542		kaltspielerhy	Magic Tree (CEOI19_magictree)	C++20	100 / 100	86 ms	31556 KiB

magictree

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

int N, M, K;
vector<vector<int>> graphe;
vector<pair<int, int>> fruits;

map<int, int> explore(int noeud) {
    map<int, int> nouvMap;

    for (int iFils : graphe[noeud]) {
        map<int, int> derrMap = explore(iFils);
        if (derrMap.size() > nouvMap.size()) swap(derrMap, nouvMap);
        for (auto [a, b] : derrMap) {
            if (nouvMap.find(a) == nouvMap.end())
                nouvMap[a] = b;
            else
                nouvMap[a] += b;
        }
        // for (auto [a, b] : nouvMap) cout << a << ' ' << b << '\n';
    }

    if (fruits[noeud] != (pair<int,int>){-1, -1}) {
        auto it = nouvMap.upper_bound(fruits[noeud].first);
        int nbFruits = fruits[noeud].second;
        while (it != nouvMap.end() && nbFruits >= it->second) {
            nbFruits -= it->second;
            // cerr << it->first << '\n';
            it = nouvMap.erase(it);
        }
        if (it != nouvMap.end()) {
            nouvMap[it->first] -= nbFruits;
        }
        if (nouvMap.find(fruits[noeud].first) == nouvMap.end()) {
            nouvMap[fruits[noeud].first] = fruits[noeud].second;
        }
        else {
            nouvMap[fruits[noeud].first] += fruits[noeud].second;
        }
    }

    return nouvMap;
}

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

    cin >> N >> M >> K;
    graphe.resize(N+1);
    fruits.resize(N+1, {-1, -1});
    for (int iNoeud = 2; iNoeud <= N; iNoeud++) {
        int parent;
        cin >> parent;
        graphe[parent].push_back(iNoeud);
    }
    for (int iFruit = 1; iFruit <= M; iFruit++) {
        int noeud, jour, jus;
        cin >> noeud >> jour >> jus;
        fruits[noeud] = {jour, jus};
    }

    int res = 0;
    for (auto [a, b] : explore(1)) {
        // cout << a << ' ' << b << '\n';
        res += b;
    }

    cout << res << '\n';
}

• 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