Submission #1279679

#TimeUsernameProblemLanguageResultExecution timeMemory
1279679DanielPr8Magic Tree (CEOI19_magictree)C++20
100 / 100
115 ms39796 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;

#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()


void merge(multiset<pll>& a, multiset<pll>& b){
    if(a.size()<b.size())swap(a,b);
    for(auto [d,w]:b){
        a.insert({d,w});
    }
}
void pl(multiset<pll>& a, ll d, ll w){
    a.insert({d,w});
    while(w>0){
        auto it = a.upper_bound({d,1e18});
        if(it==a.end())break;
        w-=(*it).s;
        ll las = (*it).f;
        a.erase(it);
        if(w<0){
            a.insert({las, -w});
            w=0;
        }
    }
}
vvl g;
vll d, w;
vector<multiset<pll>> he;
ll k;
void dfs(ll cur){
    for(ll i:g[cur]){
        dfs(i);
        merge(he[cur], he[i]);
    }
    if(d[cur]!=-1)pl(he[cur], d[cur], w[cur]);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    ll n, m;
    cin >> n >> m >> k;
    g = vvl(n);
    he = vector<multiset<pll>>(n);
    d = w = vll(n, -1);
    for(ll p,i = 1; i < n; ++i){
        cin >> p;
        p--;
        g[p].pb(i);
    }
    for(ll a,b,c,i = 0; i < m; ++i){
        cin >> a >> b >> c;
        a--;
        d[a]=b;
        w[a]=c;
    }
    dfs(0);
    ll ans = 0;
    for(auto i:he[0])ans += i.s;
    cout << ans;
}
#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...