Submission #954492

#	Time	Username	Problem	Language	Result	Execution time	Memory
954492		Skywk	Magic Tree (CEOI19_magictree)	C++17	100 / 100	102 ms	38484 KiB

magictree

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;
struct Tree{
    vector<int> adj[MAXN + 1];
    int ds[MAXN + 1], js[MAXN + 1];
    void insert(map<int, long long>* dp, int v){
        (*dp)[ds[v]] += js[v];
        auto ptr = dp->find(ds[v]);
        int j_left = js[v];
        while(j_left > 0 && next(ptr) != dp->end()){
            auto nxt_ptr = next(ptr);
            if(nxt_ptr->second > j_left){
                nxt_ptr->second -= j_left;
                break;
            }
            else{
                j_left -= nxt_ptr->second;
                dp->erase(nxt_ptr);
            }
        }
    }
    map<int, long long>* TreeDp(int v){
        auto curr_map = new map<int, long long>();
        for(auto u : adj[v]){
            auto new_map = TreeDp(u);
            if(new_map->size() > curr_map->size()) swap(curr_map, new_map);
            for(auto [key, value] : *new_map){
                (*curr_map)[key] += value;
            }
        }
        if(ds[v] > 0) insert(curr_map, v);
        return curr_map;
    }
};
Tree T;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int N, M, K;
    cin>> N>> M>> K;
    for(int i=2; i<=N; i++){
        int p; cin>> p;
        T.adj[p].push_back(i);
    }
    for(int i=0; i<M; i++){
        int v; cin>> v;
        cin>> T.ds[v]>> T.js[v];
    }

    auto dp = T.TreeDp(1);
    long long res = 0;
    for(auto [key, value] : *dp){
        res += value;
    }
    cout<< res;
    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