oj.uz

Submission #724194

# Submission time Handle Problem Language Result Execution time Memory
724194 2023-04-14T20:33:34 Z sunnat Magic Tree (CEOI19_magictree) C++14
20 / 100
 417 ms 291724 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;
        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;
            }
            t[v].mx += t[v].delta;
            t[v].delta = 0;
        }
        if(l >= id){
            t[v].mx = max(t[v].mx, w);
            return;
        }
        
        int m = (l + r) >> 1;

        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(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:149: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]
  149 |                 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 1 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 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 175 ms 105064 KB Output is correct
2 Correct 79 ms 48032 KB Output is correct
3 Correct 417 ms 291724 KB Output is correct
4 Correct 238 ms 170024 KB Output is correct
5 Correct 246 ms 170708 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 2 ms 468 KB Output is correct
4 Correct 64 ms 16396 KB Output is correct
5 Correct 59 ms 16440 KB Output is correct
6 Correct 77 ms 16456 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 12828 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 1 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 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 109 ms 35564 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 4856 KB Output is correct
2 Incorrect 27 ms 9876 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 1 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 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 2 ms 468 KB Output is correct
13 Correct 64 ms 16396 KB Output is correct
14 Correct 59 ms 16440 KB Output is correct
15 Correct 77 ms 16456 KB Output is correct
16 Incorrect 109 ms 35564 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 1 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 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 175 ms 105064 KB Output is correct
11 Correct 79 ms 48032 KB Output is correct
12 Correct 417 ms 291724 KB Output is correct
13 Correct 238 ms 170024 KB Output is correct
14 Correct 246 ms 170708 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 64 ms 16396 KB Output is correct
19 Correct 59 ms 16440 KB Output is correct
20 Correct 77 ms 16456 KB Output is correct
21 Incorrect 63 ms 12828 KB Output isn't correct
22 Halted 0 ms 0 KB -