Submission #1180384

#TimeUsernameProblemLanguageResultExecution timeMemory
1180384LudisseyMagic Tree (CEOI19_magictree)C++20
0 / 100
2096 ms18572 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;

vector<int> hu;
vector<int> mu;

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){
        auto it=v[0].upper_bound(d[x]);
        if(it!=v[0].end()) {
            v[0][(*it).first]-=w[x];
        }
        v[0][d[x]]+=w[x];
    }else{
        v.resize(1);
        v[0][d[x]]=w[x];
    }
    return 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);
    hu.resize(k,false);
    mu.resize(k,false);
    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;
    for (auto u : mp) mx+=u.second;
    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...