제출 #1361293

#제출 시각아이디문제언어결과실행 시간메모리
1361293BlagojceMagic Tree (CEOI19_magictree)C++20
100 / 100
107 ms36116 KiB

#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;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…