제출 #1334892

#제출 시각아이디문제언어결과실행 시간메모리
1334892mitko7Magic Tree (CEOI19_magictree)C++20
100 / 100
99 ms36208 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#include <map>
#define endl '\n'

using namespace std;

int n,m,k;
int par[100067];
vector<long long> v[100067];
pair<long long,long long> p[100067];
map<long long, long long> s[100067];
void dfs(int a) {
    for(auto x : v[a]) {
        dfs(x);
    }
    for(auto x : v[a]) {
        if(s[a].size()<s[x].size()) s[a].swap(s[x]);
        for(auto y : s[x]) {
            s[a][y.first]+=y.second;
        }
    }
    if(p[a].first==0) return;
    s[a][p[a].first]+=p[a].second;
    long long pom = p[a].second;
    map<long long, long long>::iterator x = s[a].upper_bound(p[a].first);
    while(x!=s[a].end() && pom>0) {
        long long val = (*x).second;
        long long r = min(pom, val);
        x->second-=r;
        pom-=r;
        if(pom==0) break;
        s[a].erase(x);
        x = s[a].upper_bound(p[a].first);
    }
}
long long solve(int a) {
    long long ans = 0;
    for(auto x : s[a]) ans+=x.second;
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 2; i <= n; i++) {
        cin >> par[i];
        v[par[i]].push_back(i);
    }
    for(int i = 1; i <= m; i++) {
        long long a,d,w;
        cin >> a >> d >> w;
        p[a]={d,w};
    }
    dfs(1);
    
    cout<<solve(1);
}
#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...