Submission #1328911

#TimeUsernameProblemLanguageResultExecution timeMemory
1328911LudisseyMagic Tree (CEOI19_magictree)C++20
100 / 100
94 ms34876 KiB
#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long

vector<vector<int>> child;
vector<int> w,d;


map<int,int> dp(int x){
    vector<map<int,int>> v;
    for (auto u : child[x])
    {
        v.push_back(dp(u));
    }
    sort(all(v), [](map<int,int> &a, map<int,int> &b){ return sz(a)>sz(b); });
    for (int i = 1; i < sz(v); i++)
    {
        if(sz(v[i])==0) continue;
        for (auto u : v[i]){
            v[0][u.first]+=u.second;
        }
    }
    if(sz(v)>0){
        if(w[x]!=0){
            auto it=v[0].upper_bound(d[x]);
            v[0][d[x]]+=w[x];
            int _w=w[x];
            while(it!=v[0].end() && _w>0) {
                if(_w<v[0][(*it).first]) v[0][(*it).first]-=_w, _w=0;
                else{
                    auto it2=it;
                    it++;
                    _w-=v[0][(*it2).first];
                    v[0].erase(it2);
                }
            }
        }

    }else{
        v.resize(1);
        if(w[x]!=0) v[0][d[x]]=w[x];
    }
    /*cerr << x << ": ";
    for (auto u : v[0]) cerr << u.second << " ";
    cerr << "\n";*/ 
    return move(v[0]);
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,m,k; cin >> n >> m >> k;
    child.resize(n);
    w.resize(n,0);
    d.resize(n,0);
    for (int i = 1; i < n; i++)
    {
        int p; cin >> p;
        child[p-1].push_back(i);
    }
    for (int i = 0; i < n; i++) {
        int v; cin >> v;
        cin >> d[v-1] >> w[v-1];
    }
    map<int,int> mp=dp(0);
    int mx=0;
    int sm=0;
    for (auto u : mp) {
        sm+=u.second; 
        mx=max(u.second,sm); 
    }
    cout << mx << "\n";
    return 0;
}
#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...