Submission #1266583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266583		vtnoo	Magic Tree (CEOI19_magictree)	C++20	100 / 100	139 ms	34412 KiB

magictree

#include <bits/stdc++.h>

using namespace std;

const int MAXN=100000;
vector<int> adj[MAXN];
map<long long, long long> dp[MAXN];
pair<int,int> fruit[MAXN];

void dfs(int u){
    for(auto v:adj[u]){
        dfs(v);
        if(dp[u].size()<dp[v].size()){
            swap(dp[u], dp[v]);
        }
        for(auto [key, value]:dp[v]){
            dp[u][key]+=value;
        }
    }
    auto [time, sum]=fruit[u];
    if(time!=0){
        dp[u][time]+=sum;
        while(true){
            auto it=dp[u].upper_bound(time);
            if(it==dp[u].end())break;
            if(it->second<=sum){
                sum-=it->second;
                dp[u].erase(it);
            }else{
                dp[u][it->first]-=sum;
                break;
            }
        }
    }
}

int main(){
    int n,m,k;cin>>n>>m>>k;
    for(int i=1;i<n;i++){
        int pi;cin>>pi;
        pi--;
        adj[pi].push_back(i);
    }
    for(int i=0;i<m;i++){
        int v,d,w;cin>>v>>d>>w;
        v--;
        fruit[v]={d,w};
    }
    dfs(0);
    long long ans=0;
    for(auto [time, value]:dp[0]){
        ans+=value;
    }
    cout<<ans<<endl;
}

• 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