oj.uz

Submission #723762

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

node free_node;
int k;

struct Dynamic_Segment_Tree{
    vector<node> t;
    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;
            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;
            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]].clear(q[u].first+1, k);
                seg_tree[seg_id[u]].add(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:173: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]
  173 |             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 0 ms 212 KB Output is correct
5 Correct 1 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 0 ms 324 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 182136 KB Output is correct
2 Correct 68 ms 43936 KB Output is correct
3 Correct 409 ms 397620 KB Output is correct
4 Correct 174 ms 134844 KB Output is correct
5 Correct 181 ms 135500 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 13612 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 0 ms 212 KB Output is correct
5 Correct 1 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 0 ms 324 KB Output is correct
10 Incorrect 105 ms 38628 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 6860 KB Output is correct
2 Correct 26 ms 11692 KB Output is correct
3 Correct 28 ms 11728 KB Output is correct
4 Correct 31 ms 14148 KB Output is correct
5 Correct 13 ms 8224 KB Output is correct
6 Incorrect 21 ms 8308 KB Output isn't correct
7 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 0 ms 212 KB Output is correct
5 Correct 1 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 0 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 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 0 ms 212 KB Output is correct
5 Correct 1 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 0 ms 324 KB Output is correct
10 Correct 188 ms 182136 KB Output is correct
11 Correct 68 ms 43936 KB Output is correct
12 Correct 409 ms 397620 KB Output is correct
13 Correct 174 ms 134844 KB Output is correct
14 Correct 181 ms 135500 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -