oj.uz

Submission #724191

# Submission time Handle Problem Language Result Execution time Memory
724191 2023-04-14T20:21:50 Z sunnat Magic Tree (CEOI19_magictree) C++14
20 / 100
 370 ms 294204 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.set(d.t[vd].right, m+1, r, m+1, d.t[vd].mx);
        set(right_side(v), m+1, r, m+1, t[v].mx);
        merge(right_side(v), m+1, r, d, d.t[vd].right);

        d.set(d.t[vd].left, l, m, l, d.t[vd].mx);
        set(left_side(v), l, m, l, t[v].mx);
        merge(left_side(v), l, m, d, d.t[vd].left);
        t[v].delta += d.t[vd].delta;
    }
    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:145: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]
  145 |                 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 1 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 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 165 ms 105088 KB Output is correct
2 Correct 78 ms 49132 KB Output is correct
3 Correct 370 ms 294204 KB Output is correct
4 Correct 247 ms 172048 KB Output is correct
5 Correct 237 ms 172980 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 76 ms 16416 KB Output is correct
5 Correct 70 ms 16448 KB Output is correct
6 Correct 77 ms 16476 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 12732 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 1 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 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 106 ms 37076 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 10552 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 1 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 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 2 ms 468 KB Output is correct
13 Correct 76 ms 16416 KB Output is correct
14 Correct 70 ms 16448 KB Output is correct
15 Correct 77 ms 16476 KB Output is correct
16 Incorrect 106 ms 37076 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 1 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 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 165 ms 105088 KB Output is correct
11 Correct 78 ms 49132 KB Output is correct
12 Correct 370 ms 294204 KB Output is correct
13 Correct 247 ms 172048 KB Output is correct
14 Correct 237 ms 172980 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 76 ms 16416 KB Output is correct
19 Correct 70 ms 16448 KB Output is correct
20 Correct 77 ms 16476 KB Output is correct
21 Incorrect 65 ms 12732 KB Output isn't correct
22 Halted 0 ms 0 KB -