Submission #1322312

#TimeUsernameProblemLanguageResultExecution timeMemory
1322312jahongirMagic Tree (CEOI19_magictree)C++20
100 / 100
90 ms31400 KiB
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(a) a.begin(),a.end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef unsigned long long ull;
typedef vector<int> vi;



const int mxn = 1e5+1;
vector<int> g[mxn];
int val[mxn][2], sub[mxn];
multiset<pii> st[mxn];

void solve(){
    int n,m,k; cin >> n >> m >> k;

    for(int i = 2; i <= n; i++){
        int p; cin >> p;
        g[p].emplace_back(i);
    }

    for(int i = 0; i < m; i++){
        int v,d,w; cin >> v >> d >> w;
        val[v][0] = d;
        val[v][1] = w;
    }

    for(int u = n; u; u--){
        sub[u] = 1;
        int mx = 0;
        for(auto v : g[u]){
            sub[u] += sub[v];
            if(sub[mx] < sub[v]) mx = v;
        }

        st[u].swap(st[mx]);

        for(auto v : g[u]) if(v!=mx){
            for(auto x : st[v])
                st[u].insert(x);
        }

        if(val[u][1]==0) continue;

        st[u].insert({val[u][0],val[u][1]});

        auto it = st[u].lower_bound(make_pair(val[u][0]+1,0));

        while(it != st[u].end() && val[u][1] > 0){
            if(it->second <= val[u][1]){
                val[u][1] -= it->second;
                it = st[u].erase(it);
            }else{
                auto v = *it;
                st[u].erase(it);
                st[u].insert({v.first,v.second-val[u][1]});
                val[u][1] = 0;
            }
        }
    }

    ll ans = 0;
    for(auto [v,x] : st[1])
        ans += x;
    cout << ans;    

}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--){solve();}
}
#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...