제출 #1328846

#제출 시각아이디문제언어결과실행 시간메모리
1328846LudisseyMagic Tree (CEOI19_magictree)C++20
31 / 100
2096 ms38796 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;
        auto itu=v[i].end(); 
        int mn=1e12;
        while(itu!=v[i].begin()){
            itu--;
            pair<int,int> u=*itu;
            int mx=0;
            for (auto k : v[0]){
                if(k.first>=mn) break;
                if(k.first<=u.first){
                    mx=max(mx, k.second);
                }else{
                    v[0][k.first]+=u.second;
                }
            }
            v[0][u.first]=mx+u.second;
            mn=u.first;
        } 
    }
    if(sz(v)>0){
        if(w[x]==0) return v[0];
        auto it=v[0].upper_bound(d[x]);
        if(it!=v[0].begin()) {
            it--;
            v[0][d[x]]=(*it).second;
        }
        v[0][d[x]]+=w[x];
        for (auto k : v[0]){
            if(k.first>d[x]) v[0][k.first]=max(v[0][k.first],v[0][d[x]]);
        }

    }else{
        v.resize(1);
        if(w[x]==0) return v[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;
    for (auto u : mp) { 
        mx=max(u.second,mx); 
    }
    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...