oj.uz

Submission #724196

# Submission time Handle Problem Language Result Execution time Memory
724196 2023-04-14T20:43:23 Z sunnat Magic Tree (CEOI19_magictree) C++14
20 / 100
 387 ms 291844 KB 
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
using namespace std;
#define int long long
 
struct node{
    int mx;
    int left;
    int right;
    int delta;
    node(){
        mx = delta = 0;
        left = right = -1;
    }
};
 
node free_node;
int k;
 
struct Dynamic_Segment_Tree{
    vector<node> t;
    
    Dynamic_Segment_Tree(){
        t.push_back(free_node);
    }
    
    int left_side(int v){
        if(t[v].left == -1){
            t[v].left = t.size();
            t.push_back(free_node);
            t.back().mx = t[v].mx;
        }
        return t[v].left;
    }
    
    int right_side(int v){
        if(t[v].right == -1){
            t[v].right = t.size();
            t.push_back(free_node);
            t.back().mx = t[v].mx;
        }
        return t[v].right;
    }

    void set(int v, int l, int r, int id, int w){
        if(r < id || t[v].mx >= w) return;
        int m = (l + r) >> 1;
        if(t[v].delta){
            if(t[v].left != -1){
                t[left_side(v)].mx = max(t[left_side(v)].mx, t[v].mx);
                t[right_side(v)].mx = max(t[right_side(v)].mx, t[v].mx);
                t[left_side(v)].delta += t[v].delta;
                t[right_side(v)].delta += t[v].delta;
                set(right_side(v), m+1, r, id, 0);
                set(left_side(v), l, m, id, 0);
            }
            t[v].mx += t[v].delta;
            t[v].delta = 0;
        }
        if(l >= id){
            t[v].mx = max(t[v].mx, w);
            return;
        }
        
        

        set(right_side(v), m+1, r, id, w);
        set(left_side(v), l, m, id, w);
    }
    void set(int id, int w){
        set(0, 1, k, id, w);
    }
    int get(int v, int l, int r, int id){
        if(v == -1 || r < id || l > id) return 0;
        if(l == r) return t[v].mx + t[v].delta;
        int m = (l + r) / 2;
        return max({t[v].mx, get(t[v].left, l, m, id), get(t[v].right, m+1, r, id)}) + t[v].delta;
    }
    int get(int x){
        return get(0, 1, k, x);
    }
    void merge(int v, int l, int r, Dynamic_Segment_Tree&d, int vd){
        if(vd == -1) return;
        if(d.t[vd].left == -1){
            t[v].delta += d.t[vd].mx + d.t[vd].delta;
            return;
        }
        int m = (l + r) / 2;
        //d.t[d.t[vd].right].mx = max(d.t[d.t[vd].right].mx, d.t[vd].mx);
        //d.t[d.t[vd].left].mx = max(d.t[d.t[vd].left].mx, d.t[vd].mx);
        d.set(d.t[vd].right, m+1, r, m+1, d.t[vd].mx);
        d.set(d.t[vd].left, l, m, l, d.t[vd].mx);
        d.t[d.t[vd].right].delta += d.t[vd].delta;
        d.t[d.t[vd].left].delta += d.t[vd].delta;
        d.t[vd].delta = 0;
        set(v, l, m, l, 0);
        set(right_side(v), m+1, r, m+1, t[v].mx);
        merge(right_side(v), m+1, r, d, d.t[vd].right);
        
        set(left_side(v), l, m, l, t[v].mx);
        merge(left_side(v), l, m, d, d.t[vd].left);
    }
    void merge(Dynamic_Segment_Tree& d){
        merge(0, 1, k, d, 0);
    }
};
 
Dynamic_Segment_Tree free_seg_tree;
 
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m >> k;
    vector<int> seg_id(n, -1);
    vector<Dynamic_Segment_Tree> seg_tree;
    vector<vector<int> > g(n);
    vector<pair<int, int> > q(n, make_pair(-1, -1));
    for(int i = 2, f; i <= n; i ++){
        cin >> f;
        g[f-1].push_back(i-1);
    }
    for(int i = 0, v, d, w; i < m; i ++){
        cin >> v >> d >> w;
        q[v-1] = make_pair(d, w);
    }
    for(int u = n-1; u >= 0; u --){
        if(g[u].empty()){
            if(q[u].first == -1) continue;
            seg_id[u] = seg_tree.size();
            seg_tree.push_back(free_seg_tree);
            seg_tree[seg_id[u]].set(q[u].first, q[u].second);
        }
        else{
            sort(g[u].begin(), g[u].end(), [&](int r, int l){
                if(seg_id[r] == -1) return false;
                if(seg_id[l] == -1) return true;
                return seg_tree[seg_id[r]].t.size() > seg_tree[seg_id[l]].t.size();
            });
            if(seg_id[g[u][0]] == -1){
                if(q[u].first != -1) {
                    seg_id[u] = seg_tree.size();
                    seg_tree.push_back(free_seg_tree);
                    seg_tree[seg_id[u]].set(q[u].first, q[u].second);
                }
            }
            else{
                seg_id[u] = seg_id[g[u][0]];
                for(int i = 1; i < g[u].size() && seg_id[g[u][i]] != -1; i ++)
                    seg_tree[seg_id[u]].merge(seg_tree[seg_id[g[u][i]]]);
                
                seg_tree[seg_id[u]].set(q[u].first, seg_tree[seg_id[u]].get(q[u].first) + q[u].second);
            }
        }
        // cout << u + 1 << ' ' << seg_tree[seg_id[u]].get(k) << endl;
    }
    cout << seg_tree[seg_id[0]].get(k);
    return 0;
}

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:153:34: 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]
  153 |                 for(int i = 1; i < g[u].size() && seg_id[g[u][i]] != -1; i ++)
      |                                ~~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 105128 KB Output is correct
2 Correct 84 ms 48080 KB Output is correct
3 Correct 387 ms 291844 KB Output is correct
4 Correct 257 ms 170052 KB Output is correct
5 Correct 276 ms 170608 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 63 ms 16496 KB Output is correct
5 Correct 62 ms 16392 KB Output is correct
6 Correct 82 ms 16392 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 12848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 102 ms 35652 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4948 KB Output is correct
2 Incorrect 25 ms 9980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 63 ms 16496 KB Output is correct
14 Correct 62 ms 16392 KB Output is correct
15 Correct 82 ms 16392 KB Output is correct
16 Incorrect 102 ms 35652 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 144 ms 105128 KB Output is correct
11 Correct 84 ms 48080 KB Output is correct
12 Correct 387 ms 291844 KB Output is correct
13 Correct 257 ms 170052 KB Output is correct
14 Correct 276 ms 170608 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 63 ms 16496 KB Output is correct
19 Correct 62 ms 16392 KB Output is correct
20 Correct 82 ms 16392 KB Output is correct
21 Incorrect 87 ms 12848 KB Output isn't correct
22 Halted 0 ms 0 KB -