oj.uz

Submission #1049131

# Submission time Handle Problem Language Result Execution time Memory
1049131 2024-08-08T13:46:18 Z anton Magic Tree (CEOI19_magictree) C++17
100 / 100
 936 ms 566080 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 150364 KB Output is correct
2 Correct 148 ms 126816 KB Output is correct
3 Correct 592 ms 483792 KB Output is correct
4 Correct 565 ms 484096 KB Output is correct
5 Correct 603 ms 478672 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 226 ms 235476 KB Output is correct
5 Correct 223 ms 235644 KB Output is correct
6 Correct 240 ms 236236 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 335324 KB Output is correct
2 Correct 381 ms 263132 KB Output is correct
3 Correct 258 ms 194264 KB Output is correct
4 Correct 540 ms 478228 KB Output is correct
5 Correct 201 ms 207692 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 590 ms 431828 KB Output is correct
11 Correct 514 ms 403928 KB Output is correct
12 Correct 261 ms 193092 KB Output is correct
13 Correct 529 ms 478088 KB Output is correct
14 Correct 213 ms 207832 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8792 KB Output is correct
2 Correct 28 ms 26460 KB Output is correct
3 Correct 25 ms 26460 KB Output is correct
4 Correct 27 ms 27484 KB Output is correct
5 Correct 19 ms 26224 KB Output is correct
6 Correct 26 ms 26712 KB Output is correct
7 Correct 23 ms 26416 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 1624 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 1 ms 1628 KB Output is correct
13 Correct 226 ms 235476 KB Output is correct
14 Correct 223 ms 235644 KB Output is correct
15 Correct 240 ms 236236 KB Output is correct
16 Correct 590 ms 431828 KB Output is correct
17 Correct 514 ms 403928 KB Output is correct
18 Correct 261 ms 193092 KB Output is correct
19 Correct 529 ms 478088 KB Output is correct
20 Correct 213 ms 207832 KB Output is correct
21 Correct 156 ms 98412 KB Output is correct
22 Correct 430 ms 289500 KB Output is correct
23 Correct 473 ms 301016 KB Output is correct
24 Correct 936 ms 566080 KB Output is correct
25 Correct 560 ms 486672 KB Output is correct
26 Correct 485 ms 349640 KB Output is correct
27 Correct 308 ms 208848 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 184 ms 150364 KB Output is correct
11 Correct 148 ms 126816 KB Output is correct
12 Correct 592 ms 483792 KB Output is correct
13 Correct 565 ms 484096 KB Output is correct
14 Correct 603 ms 478672 KB Output is correct
15 Correct 1 ms 1624 KB Output is correct
16 Correct 1 ms 1628 KB Output is correct
17 Correct 1 ms 1628 KB Output is correct
18 Correct 226 ms 235476 KB Output is correct
19 Correct 223 ms 235644 KB Output is correct
20 Correct 240 ms 236236 KB Output is correct
21 Correct 407 ms 335324 KB Output is correct
22 Correct 381 ms 263132 KB Output is correct
23 Correct 258 ms 194264 KB Output is correct
24 Correct 540 ms 478228 KB Output is correct
25 Correct 201 ms 207692 KB Output is correct
26 Correct 590 ms 431828 KB Output is correct
27 Correct 514 ms 403928 KB Output is correct
28 Correct 261 ms 193092 KB Output is correct
29 Correct 529 ms 478088 KB Output is correct
30 Correct 213 ms 207832 KB Output is correct
31 Correct 10 ms 8792 KB Output is correct
32 Correct 28 ms 26460 KB Output is correct
33 Correct 25 ms 26460 KB Output is correct
34 Correct 27 ms 27484 KB Output is correct
35 Correct 19 ms 26224 KB Output is correct
36 Correct 26 ms 26712 KB Output is correct
37 Correct 23 ms 26416 KB Output is correct
38 Correct 156 ms 98412 KB Output is correct
39 Correct 430 ms 289500 KB Output is correct
40 Correct 473 ms 301016 KB Output is correct
41 Correct 936 ms 566080 KB Output is correct
42 Correct 560 ms 486672 KB Output is correct
43 Correct 485 ms 349640 KB Output is correct
44 Correct 308 ms 208848 KB Output is correct
45 Correct 140 ms 96352 KB Output is correct
46 Correct 408 ms 286200 KB Output is correct
47 Correct 423 ms 288540 KB Output is correct
48 Correct 875 ms 548048 KB Output is correct
49 Correct 559 ms 486784 KB Output is correct
50 Correct 507 ms 351180 KB Output is correct
51 Correct 300 ms 209608 KB Output is correct