Submission #1048600

#TimeUsernameProblemLanguageResultExecution timeMemory
1048600antonMagic Tree (CEOI19_magictree)C++17
34 / 100
2082 ms1048576 KiB
#include<bits/stdc++.h>

using namespace std;

#define int long long
int N, M, K;


struct Fruit{
    int pos = -1, t, w;
    Fruit(){};
    Fruit(int _pos, int _t, int _w){
        pos = _pos;
        t= _t;
        w =_w;
    }
};

vector<Fruit> fr;
vector<Fruit> vertex_fruit;
vector<int> anc;
vector<vector<int>> ch;

vector<int> merge(vector<int> lh, vector<int> rh){
    int lmax= 0, rmax = 0;
    vector<int> res(K+1);
    for(int i = 0; i<=K; i++){
        lmax = max(lmax, lh[i]);
        rmax = max(rmax, rh[i]);
        res[i] = rmax+lmax;
    }
    return res;
}
vector<int> dfs(int u, int anc){
    vector<int> res(K+1);
    for(auto e: ch[u]){
        vector<int> ch_res = dfs(e, u);
        res=  merge(res, ch_res);
    }

    if(vertex_fruit[u].pos != -1){
        int best= 0;
        for(int i = 0; i<=vertex_fruit[u].t; i++){
            best = max(best, res[i]);
        }

        res[vertex_fruit[u].t] = best+vertex_fruit[u].w;
    }

    /*cout<<"res "<<u<<endl;
    for(int i = 0; i<=K; i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;*/
    return res;
}

signed main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>N>>M>>K;

    vertex_fruit.resize(N, Fruit(-1, -1, -1));
    ch.resize(N);

    anc.resize(N);
    for(int  i= 1; i<N; i++){
        cin>>anc[i];
        anc[i]--;
        ch[anc[i]].push_back(i);
    }
    for(int i = 0; i<M; i++){
        int v, d, w;
        cin>>v>>d>>w;
        v--;
        fr.push_back(Fruit(v, d, w));
        vertex_fruit[v]= fr.back();
    }


    vector<int> RES = dfs(0, -1);
    int ans= 0;
    for(int i = 0; i<=K; i++){
        ans = max(ans, RES[i]);
    }
    cout<<ans<<endl;
}
#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...