Submission #1204513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204513		irmuun	Magic Tree (CEOI19_magictree)	C++20	100 / 100	102 ms	38896 KiB

magictree

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll N=1e5+5;

ll n,m,k;
vector<ll>g[N];
ll p[N],u[N],d[N],w[N];
vector<ll>day(N,0),pt(N,0);
map<ll,ll>dp[N];

void solve(ll i){
    for(ll j:g[i]){
        solve(j);
        if(dp[j].size()>dp[i].size()){
            swap(dp[i],dp[j]);
        }
        for(auto x:dp[j]){
            dp[i][x.ff]+=x.ss;
        }
    }
    if(day[i]>0){
        dp[i][day[i]]+=pt[i];
        while(true){
            auto it=dp[i].upper_bound(day[i]);
            if(it==dp[i].end()) break;
            ll x=(it->ff);
            if((it->ss)<=pt[i]){
                pt[i]-=(it->ss);
                dp[i].erase(it->ff);
            }
            else{
                dp[i][it->ff]-=pt[i];
                break;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m>>k;
    for(ll i=2;i<=n;i++){
        cin>>p[i];
        g[p[i]].pb(i);
    }
    for(ll i=0;i<m;i++){
        cin>>u[i]>>d[i]>>w[i];
        day[u[i]]=d[i];
        pt[u[i]]=w[i];
    }
    solve(1);
    ll ans=0;
    for(auto x:dp[1]){
        ans+=x.ss;
    }
    cout<<ans;
}

• 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