Submission #1048610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048610		anton	Magic Tree (CEOI19_magictree)	C++17	0 / 100	2087 ms	1048576 KiB

magictree

#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);
    }

    vector<int> times;
    for(int i = 0; i<M; i++){
        int v, d, w;
        cin>>v>>d>>w;
        v--;
        times.push_back(d);
        fr.push_back(Fruit(v, d, w));
    }

    sort(times.begin(), times.end());

    for(Fruit& f: fr){
        f.t = lower_bound(times.begin(), times.end(), f.t)- times.begin();
        vertex_fruit[f.pos] = f;
    }
    K = min(K, N);


    vector<int> RES = dfs(0, -1);
    int ans= 0;
    for(int i = 0; i<=K; i++){
        ans = max(ans, RES[i]);
    }
    cout<<ans<<endl;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17