oj.uz

Submission #724195

# Submission time Handle Problem Language Result Execution time Memory
724195 2023-04-14T20:36:31 Z sunnat Magic Tree (CEOI19_magictree) C++14
20 / 100
 441 ms 291860 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(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 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 1 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 1 ms 212 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 105148 KB Output is correct
2 Correct 75 ms 48000 KB Output is correct
3 Correct 441 ms 291860 KB Output is correct
4 Correct 250 ms 170020 KB Output is correct
5 Correct 271 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 62 ms 16384 KB Output is correct
5 Correct 64 ms 16404 KB Output is correct
6 Correct 82 ms 16444 KB Output is correct

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 1 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 1 ms 212 KB Output is correct
10 Incorrect 118 ms 35612 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 1 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 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 62 ms 16384 KB Output is correct
14 Correct 64 ms 16404 KB Output is correct
15 Correct 82 ms 16444 KB Output is correct
16 Incorrect 118 ms 35612 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 1 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 1 ms 212 KB Output is correct
10 Correct 150 ms 105148 KB Output is correct
11 Correct 75 ms 48000 KB Output is correct
12 Correct 441 ms 291860 KB Output is correct
13 Correct 250 ms 170020 KB Output is correct
14 Correct 271 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 62 ms 16384 KB Output is correct
19 Correct 64 ms 16404 KB Output is correct
20 Correct 82 ms 16444 KB Output is correct
21 Incorrect 61 ms 12776 KB Output isn't correct
22 Halted 0 ms 0 KB -