oj.uz

답안 #723692

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
723692 2023-04-14T07:38:32 Z sunnat Magic Tree (CEOI19_magictree) C++14
3 / 100
 452 ms 397592 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) >> 1;
        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) >> 1;
        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) >> 1;
        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) >> 1;
        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);
        // d.t.clear();
        // d.t.shrink_to_fit();
    }
};

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:175: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]
  175 |             for(int i = 1; i < g[u].size() && seg_id[g[u][i]] != -1; i ++)
      |                            ~~^~~~~~~~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 182080 KB Output is correct
2 Correct 72 ms 43916 KB Output is correct
3 Correct 452 ms 397592 KB Output is correct
4 Correct 188 ms 134824 KB Output is correct
5 Correct 189 ms 135424 KB Output is correct

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 13592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6860 KB Output is correct
2 Correct 27 ms 11916 KB Output is correct
3 Correct 27 ms 11684 KB Output is correct
4 Correct 28 ms 14148 KB Output is correct
5 Correct 12 ms 8220 KB Output is correct
6 Incorrect 20 ms 8308 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -