Submission #1236521

#TimeUsernameProblemLanguageResultExecution timeMemory
1236521kaltspielerhyMagic Tree (CEOI19_magictree)C++20
55 / 100
76 ms28228 KiB
#include <bits/stdc++.h>
using namespace std;


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

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

    for (int iFils : graphe[noeud]) {
        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;
        }
    }

    swap(nouvMap, derrMap);
}

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

    explore(1);

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

    cout << res << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...