Submission #1048627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048627		anton	Magic Tree (CEOI19_magictree)	C++17	13 / 100	2017 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<vector<int>> fruit_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: fruit_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+1<<endl;
    for(int i = 0; i<=K; i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;*/
    return res;
}

void dfs2(int u, int fruit_anc){
    if(vertex_fruit[u].pos != -1){
        fruit_ch[fruit_anc].push_back(u);
        fruit_anc = u;
    }
    for(auto e: ch[u]){
        dfs2(e, fruit_anc);
    }
}

int find_pos(vector<int> &v, int e){
    int cur =0;
    for(int step = (1<<20); step>=1; step/=2){
        if(cur + step<v.size()){
            if(v[cur+step]<=e){
                cur+=step;
            }
        }
    }
    return cur;
}

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);
    fruit_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 = find_pos(times, f.t);
        vertex_fruit[f.pos] = f;
    }
    K = min(K, M);

    dfs2(0, 0);


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

Compilation message (stderr)

magictree.cpp: In function 'long long int find_pos(std::vector<long long int>&, long long int)':
magictree.cpp:72:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         if(cur + step<v.size()){
      |            ~~~~~~~~~~^~~~~~~~~

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