oj.uz

Submission #723780

# Submission time Handle Problem Language Result Execution time Memory
723780 2023-04-14T09:54:59 Z sunnat Magic Tree (CEOI19_magictree) C++14
21 / 100
 502 ms 475236 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 s;
    int ns;
    int left;
    int right;
    int cnt;
    bool clear;
    node(){
        s = 0;
        left = -1;
        right = -1;
        cnt = 0;
        clear = false;
        ns = 0;
    }
};

node free_node;
int k;

struct Dynamic_Segment_Tree{
    vector<node> t;

    int get_ns(int v, int l, int r, int id){
        if(v == -1 || t[v].clear) return 0;
        if(l == r) return t[v].ns;
        int m = (l + r) / 2;
        if(id <= m) return get_ns(t[v].left, l, m, id);
        else return get_ns(t[v].right, l, m, id);
    }
    int get_ns(int id){
        return get_ns(0, 1, k, id);
    }

    void clear_ns(int v, int l, int r, int id){
        if(v == -1) return;
        if(l == r){
            t[v].ns = 0;
            return;
        }
        int m = (l + r) >> 1;
        if(m < id) clear_ns(t[v].right, m+1, r, id);
        else clear_ns(t[v].left, l, m, id);
    }

    void clear_ns(int id){
        clear_ns(0, 1, k, id);
    }

    void add_ns(int v, int l, int r, int id, int w){
        if(l == r){
            t[v].ns += w;
            t[v].cnt = 1;
            t[v].clear = false;
            return;
        }
        
        int m = (l + r) / 2;
        if(t[v].clear){
            clear(t[v].left, l, m, l, m);
            clear(t[v].right, m+1, r, m+1, r);
            t[v].clear = false;
        }
        if(id <= m) add_ns(left_side(v), l, m, id, w);
        else add_ns(right_side(v), m+1, r, id, w);
        t[v].s = sum(t[v].left) + sum(t[v].right);
        t[v].cnt = (t[v].left != -1 ? t[t[v].left].cnt : 0) + 
                   (t[v].right != -1 ? t[t[v].right].cnt : 0);
    }
    void add_ns(int id, int w){
        add_ns(0, 1, k, id, w);
    }
    void clear(int v, int l, int r, int L, int R){
        if(v == -1 || t[v].clear) return;
        if(l == L && r == R){
            t[v].clear = true;
            t[v].cnt = 0;
            t[v].s = 0;
            t[v].ns = 0;
            return;
        }
        int m = (l + r) / 2;
        if(m < L) clear(t[v].right, m+1, r, L, R);
        else if(m >= R) clear(t[v].left, l, m, L, R);
        else{
            clear(t[v].right, m+1, r, m+1, R);
            clear(t[v].left, l, m, L, m);
        }
        t[v].s = sum(t[v].left) + sum(t[v].right);
        t[v].cnt = (t[v].left != -1 ? t[t[v].left].cnt : 0) + 
                   (t[v].right != -1 ? t[t[v].right].cnt : 0);
    }
    void clear(int l, int r){
        if(l > r) return;
        clear(0, 1, k, l, r);
    }
    int get_sum(int v, int l, int r, int L, int R){
        if(v == -1 || t[v].clear) return 0;
        if(l == L && r == R) return t[v].s;
        int m = (l + r) / 2;
        if(L > m) return get_sum(t[v].right, m+1, r, L, R);
        if(m >= R) return get_sum(t[v].left, l, m, L, R);
        return get_sum(t[v].left, l, m, L, m) + get_sum(t[v].right, m+1, r, m+1, R);
    }
    int get_sum(int l, int r){
        return l > r ? 0 : get_sum(0, 1, k, l, r);
    }
    Dynamic_Segment_Tree(){
        //t.clear();
        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);
        }
        return t[v].left;
    }
    int sum(int v){
        return v == -1 ? 0 : t[v].s;
    }
    int right_side(int v){
        if(t[v].right == -1){
            t[v].right = t.size();
            t.push_back(free_node);
        }
        return t[v].right;
    }
    void add(int v, int l, int r, int id, int w){
        if(l == r){
            t[v].s += w;
            t[v].cnt = 1;
            t[v].clear = false;
            return;
        }
        
        int m = (l + r) / 2;
        if(t[v].clear){
            clear(t[v].left, l, m, l, m);
            clear(t[v].right, m+1, r, m+1, r);
            t[v].clear = false;
        }
        if(id <= m) add(left_side(v), l, m, id, w);
        else add(right_side(v), m+1, r, id, w);
        t[v].s = sum(t[v].left) + sum(t[v].right);
        t[v].cnt = (t[v].left != -1 ? t[t[v].left].cnt : 0) + 
                   (t[v].right != -1 ? t[t[v].right].cnt : 0);
    }
    void add(int id, int w){
        add(0, 1, k, id, w);
    }
    void merge(int v, int l, int r, Dynamic_Segment_Tree&d, int vd){
        if(vd == -1 || d.t[vd].clear) return;
        if(l == r){
            t[v].cnt = 1;
            t[v].s += d.t[vd].s;
            t[v].clear = false;
            t[v].ns += d.t[vd].ns;
            return;
        }
        int m = (l + r) / 2;
        if(t[v].clear){
            clear(t[v].left, l, m, l, m);
            clear(t[v].right, m+1, r, m+1, r);
            t[v].clear = false;
        }
        merge(left_side(v), l, m, d, d.t[vd].left);
        merge(right_side(v), m+1, r, d, d.t[vd].right);
        t[v].s = sum(t[v].left) + sum(t[v].right);
        t[v].cnt = (t[v].left != -1 ? t[t[v].left].cnt : 0) + 
                   (t[v].right != -1 ? t[t[v].right].cnt : 0);
    }
    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]].add(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[0].cnt > seg_tree[seg_id[l]].t[0].cnt;
            });
            if(seg_id[g[u][0]] == -1){
                if(q[u].first == -1) continue;
                seg_id[u] = seg_tree.size();
                seg_tree.push_back(free_seg_tree);
                seg_tree[seg_id[u]].add(q[u].first, q[u].second);
                continue;
            }
            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]]]);
            if(q[u].first == -1) continue;
            if(seg_tree[seg_id[u]].get_sum(q[u].first+1, k) <= q[u].second + seg_tree[seg_id[u]].get_ns(q[u].first)){
                seg_tree[seg_id[u]].clear(q[u].first+1, k);
                seg_tree[seg_id[u]].add(q[u].first, q[u].second + seg_tree[seg_id[u]].get_ns(q[u].first));
                seg_tree[seg_id[u]].clear_ns(q[u].first);
            }
            else seg_tree[seg_id[u]].add_ns(q[u].first, q[u].second);
        }
    }
    cout << seg_tree[seg_id[0]].t[0].s;
    return 0;
}

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:227:30: 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]
  227 |             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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 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 232 ms 216548 KB Output is correct
2 Correct 106 ms 52096 KB Output is correct
3 Correct 502 ms 475236 KB Output is correct
4 Correct 220 ms 158108 KB Output is correct
5 Correct 203 ms 158764 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 14696 KB Output is correct
2 Correct 76 ms 10788 KB Output is correct
3 Correct 74 ms 10056 KB Output is correct
4 Correct 61 ms 17712 KB Output is correct
5 Correct 39 ms 8148 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 130 ms 43968 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7692 KB Output is correct
2 Correct 33 ms 12780 KB Output is correct
3 Correct 32 ms 12716 KB Output is correct
4 Correct 34 ms 15664 KB Output is correct
5 Correct 15 ms 8756 KB Output is correct
6 Incorrect 30 ms 8780 KB Output isn't correct
7 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 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 Incorrect 1 ms 468 KB Output isn't correct
12 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 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 232 ms 216548 KB Output is correct
11 Correct 106 ms 52096 KB Output is correct
12 Correct 502 ms 475236 KB Output is correct
13 Correct 220 ms 158108 KB Output is correct
14 Correct 203 ms 158764 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Incorrect 1 ms 468 KB Output isn't correct
17 Halted 0 ms 0 KB -