oj.uz

Submission #724199

# Submission time Handle Problem Language Result Execution time Memory
724199 2023-04-14T20:48:33 Z sunnat Magic Tree (CEOI19_magictree) C++14
20 / 100
 419 ms 291848 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, m+1, 0);
                set(left_side(v), l, m, l, 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;
            set(v, l, r, l, 0);
            return;
        }
        int m = (l + r) / 2;
        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:150: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]
  150 |                 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 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 105068 KB Output is correct
2 Correct 82 ms 48116 KB Output is correct
3 Correct 419 ms 291848 KB Output is correct
4 Correct 239 ms 170044 KB Output is correct
5 Correct 257 ms 170588 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 60 ms 16392 KB Output is correct
5 Correct 62 ms 16480 KB Output is correct
6 Correct 75 ms 16396 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 12800 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 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 107 ms 35604 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 29 ms 9972 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 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 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 60 ms 16392 KB Output is correct
14 Correct 62 ms 16480 KB Output is correct
15 Correct 75 ms 16396 KB Output is correct
16 Incorrect 107 ms 35604 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 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 155 ms 105068 KB Output is correct
11 Correct 82 ms 48116 KB Output is correct
12 Correct 419 ms 291848 KB Output is correct
13 Correct 239 ms 170044 KB Output is correct
14 Correct 257 ms 170588 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 60 ms 16392 KB Output is correct
19 Correct 62 ms 16480 KB Output is correct
20 Correct 75 ms 16396 KB Output is correct
21 Incorrect 58 ms 12800 KB Output isn't correct
22 Halted 0 ms 0 KB -