Submission #1361293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361293		Blagojce	Magic Tree (CEOI19_magictree)	C++20	100 / 100	107 ms	36116 KiB

magictree

#include <iostream>
#include <map>
#include <vector>

using namespace std;

int n, m, k;

vector<int> g[100005];

int J[100005];
int D[100005];


map<int, long long> *dfs(int v){
    map<int, long long> *big = new map<int, long long>();
    
    for(auto u : g[v]){
        map<int,long long> *it = dfs(u);
        if(it->size() > big -> size()){
            swap(it, big);
        }
        for(auto el : *it){
            (*big)[el.first] += el.second;
        }
    }
    if(D[v] != -1){
        (*big)[D[v]] += J[v];
        long long rem = J[v];
        auto it = big -> find(D[v]);
        while(rem > 0){
            auto itnext = next(it);
            if(itnext == big -> end()) break;
            
            if(rem >= itnext->second){
                rem -= itnext->second;
                big -> erase(itnext);
            }
            else{
                itnext -> second -= rem;
                rem = 0;
            }
        }
    }
    return big;
}

int main(){
    cin >> n >> m >> k;
    
    for(int i = 1; i < n; i ++){
        int p;
        cin >> p;
        p --;
        g[p].push_back(i);
    }
    
    for(int i = 0; i < n; i ++){
        D[i] = J[i] = -1;
    }
    for(int i = 0; i < m; i ++){
        int v, j, d;
        cin >> v >> d >> j;
        v --;
        J[v] = j;
        D[v] = d;
    }
    auto res = dfs(0);
    long long ans = 0;
    for(auto el : *res){
        ans += el.second;
    }
    cout << ans << endl;
    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