Submission #1049131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049131		anton	Magic Tree (CEOI19_magictree)	C++17	100 / 100	936 ms	566080 KiB

magictree

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
int N, M, K;
const int INF= 1e18;

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

struct Node{
    int l = 0, r = 0;
    int lazy = 0, v = 0;
    int sz = 0;
    Node(int _l, int _r){
        l = _l;
        r= _r;
    }
};
struct HollowTree{
    vector<Node> tr;

    HollowTree(){
        tr.resize(2, Node(0, 0));
    }

    Node get_node(int l, int r){
        Node res= Node(l, r);
        res.v = max(tr[l].v, tr[r].v);
        return res;
    }

    void upd(int i){
        tr[i].v = max(tr[tr[i].l].v, tr[tr[i].r].v) + tr[i].lazy;
        tr[i].sz = tr[tr[i].l].sz + tr[tr[i].r].sz;
    }

    void propagate(int t){
        if(tr[t].l == 0){
            tr[t].l = tr.size();
            tr.push_back(Node(0, 0));
        }
        if(tr[t].r == 0){
            tr[t].r = tr.size();
            tr.push_back(Node(0, 0));
        }
    }

    void insert(int pos, int v, int lt, int rt, int t){
        if(lt == rt){
            tr[t].lazy = v;
            tr[t].v = v;
            tr[t].sz = 1;
        }
        else{
            propagate(t);
            int mid = (lt+rt)/2;
            if(pos<=mid){
                insert(pos, v-tr[t].lazy, lt, mid, tr[t].l);
            }
            else{
                insert(pos, v-tr[t].lazy, mid+1, rt, tr[t].r);
            }
            upd(t);
        }
    }

    void add(int l, int r, int v, int lt, int rt, int t){
        if(l<= lt && rt <= r){
            tr[t].lazy +=v;
            tr[t].v+=v;
        }
        else if(r<lt || rt <l){
            return;
        }
        else{
            int mid = (lt+rt)/2;
            propagate(t);
            add(l, r, v, lt, mid, tr[t].l);
            add(l, r, v, mid+1, rt, tr[t].r);
            upd(t);
        }
    }

    int get(int l, int r, int lt, int rt, int t){
        if(l<= lt && rt <= r){
            return tr[t].v;
        }
        else if(r<lt || rt <l){
            return 0;
        }
        else{
            int mid = (lt+rt)/2;
            propagate(t);
            return max(get(l, r, lt, mid, tr[t].l), get(l, r, mid+1, rt, tr[t].r)) + tr[t].lazy;
        }
    }

    void iterate(vector<pii>& res,int lazy,  int lt, int rt, int t){
        if(lt == rt){
            if(res.size()==0 || tr[t].v+ lazy>= res.back().second){
                res.push_back({lt, tr[t].v+ lazy});
            }
        }
        else{
            int mid =(lt+rt)/2;
            propagate(t);
            if(tr[tr[t].l].sz>0){
                iterate(res, lazy +tr[t].lazy,lt, mid, tr[t].l);
            }
            if(tr[tr[t].r].sz>0){
                iterate(res,lazy +tr[t].lazy, mid+1, rt, tr[t].r);
            }
        }
    }
    void merge(HollowTree& rh){
        vector<pii> rh_e;
        rh.iterate(rh_e, 0, 0, INF,1);
        int prev= 0;
        
        for(auto e: rh_e){
            int max_before = get(0, e.first, 0, INF, 1);
            insert(e.first, max_before, 0, INF, 1);
            prev = e.second;
        }
        prev= 0;
        int prev_pos = 0;
        for(auto e: rh_e){
            add(prev_pos, e.first-1, prev, 0, INF, 1);
            prev_pos = e.first;
            prev= e.second;
        }
        add(prev_pos, INF, prev, 0, INF, 1);
    }

    void display(){
        vector<pii> res;
        iterate(res, 0, 0, INF, 1);
        for(auto e: res){
            cout<<e.first<<" "<<e.second<<endl;
        }
    }
};

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



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


vector<HollowTree> trees;
void dfs(int u){
    for(auto e: fruit_ch[u]){
        dfs(e);
        if(trees[e].tr.size()>trees[u].tr.size()){
            swap(trees[e], trees[u]);
        }
        trees[u].merge(trees[e]);
    }

    if(vertex_fruit[u].pos != -1){
        int max_before = trees[u].get(0, vertex_fruit[u].t, 0, INF, 1);
        trees[u].insert(vertex_fruit[u].t, max_before+vertex_fruit[u].w, 0, INF, 1);
    }

    //cout<<"tree "<<u+1<<endl;
    //trees[u].display();
}

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

    trees.resize(N);

    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);
    dfs(0);

    cout<<trees[0].get(0, INF, 0, INF, 1)<<endl;
}

Compilation message (stderr)

magictree.cpp: In function 'long long int find_pos(std::vector<long long int>&, long long int)':
magictree.cpp:175: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]
  175 |         if(cur + step<v.size()){
      |            ~~~~~~~~~~^~~~~~~~~

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