oj.uz

답안 #1094522

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1094522 2024-09-29T18:43:47 Z vladilius Magic Tree (CEOI19_magictree) C++17
24 / 100
 341 ms 279892 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
#define pb push_back
#define ff first
#define ss second

struct ST{
    struct node{
        node *l, *r;
        ll x;
        int s;
        node(){
            l = r = 0;
            x = s = 0;
        }
    };
    vector<pil> vv;
    node *rt;
    int n;
    void init(int ns){
        n = ns;
        rt = new node();
    }
    int size(){
        return rt -> s;
    }
    void fn(node *v, int tl, int tr){
        if (!(v -> s)) return;
        if (tl == tr){
            vv.pb({tl, v -> x});
            return;
        }
        int tm = (tl + tr) / 2;
        if (v -> l) fn(v -> l, tl, tm);
        if (v -> r) fn(v -> r, tm + 1, tr);
    }
    void fn(){
        vv.clear();
        fn(rt, 1, n);
    }
    void recalc(node *v){
        v -> x = v -> s = 0;
        if (v -> l){
            v -> x += v -> l -> x;
            v -> s += v -> l -> s;
        }
        if (v -> r){
            v -> x += v -> r -> x;
            v -> s += v -> r -> s;
        }
    }
    void add(node *v, int tl, int tr, int& p, ll& x){
        if (tl == tr){
            v -> x += x;
            v -> s = 1;
            return;
        }
        int tm = (tl + tr) / 2;
        if (p <= tm){
            if (!(v -> l)) v -> l = new node();
            add(v -> l, tl, tm, p, x);
        }
        else {
            if (!(v -> r)) v -> r = new node();
            add(v -> r, tm + 1, tr, p, x);
        }
        recalc(v);
    }
    void add(int p, ll x){
        add(rt, 1, n, p, x);
    }
    ll get(node *v, int tl, int tr, int& p){
        if (tl > p) return 0;
        if (tr <= p){
            return (v -> x);
        }
        int tm = (tl + tr) / 2;
        ll S = 0;
        if (v -> l) S += get(v -> l, tl, tm, p);
        if (v -> r) S += get(v -> r, tm + 1, tr, p);
        return S;
    }
    ll get(int p){
        return get(rt, 1, n, p);
    }
    int find(ll x){
        int l = 1, r = n;
        while (l + 1 < r){
            int m = (l + r) / 2;
            if (get(m) >= x){
                r = m - 1;
            }
            else {
                l = m;
            }
        }
        if (get(r) < x) l = r;
        return l;
    }
    void clear(node *&v, int tl, int tr, int l, int r){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            v = 0;
            return;
        }
        int tm = (tl + tr) / 2;
        if (v -> l) clear(v -> l, tl, tm, l, r);
        if (v -> r) clear(v -> r, tm + 1, tr, l, r);
        recalc(v);
    }
    void ch(int l, int r, ll x){
        ll S1 = 0, S2 = 0;
        if (l > 1) S1 = get(l - 1);
        if (r < n) S2 = get(r + 1);
        clear(rt, 1, n, l, min(n, r + 1));
        add(l, x - S1);
        if (r < n) add(r + 1, S2 - x);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, k; cin>>n>>m>>k;
    vector<int> g[n + 1];
    for (int i = 2; i <= n; i++){
        int p; cin>>p;
        g[p].pb(i);
    }
    vector<int> d(n + 1), w(n + 1);
    for (int i = 1; i <= m; i++){
        int u, x, y; cin>>u>>x>>y;
        d[u] = x; w[u] = y;
    }
    
    ST T[n + 1];
    function<void(int)> solve = [&](int v){
        for (int i: g[v]){
            solve(i);
        }
        T[v].init(k);
        ll S = 0;
        if (d[v] > 0){
            for (int i: g[v]){
                S += T[i].get(d[v]);
            }
        }
        for (int i: g[v]){
            if (T[v].size() < T[i].size()){
                swap(T[v], T[i]);
            }
            T[i].fn();
            for (auto [p, x]: T[i].vv){
                T[v].add(p, x);
            }
        }
        if (w[v] > 0){
            S += w[v];
            int r = T[v].find(S);
            if (d[v] <= r){
                T[v].ch(d[v], r, S);
            }
        }
    };
    solve(1);
    cout<<T[1].get(k)<<"\n";
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 77132 KB Output is correct
2 Correct 59 ms 46400 KB Output is correct
3 Runtime error 341 ms 279892 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 140 ms 56312 KB Output is correct
5 Correct 87 ms 50000 KB Output is correct
6 Correct 249 ms 82260 KB Output is correct

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 38 ms 20140 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4952 KB Output is correct
2 Correct 24 ms 15960 KB Output is correct
3 Correct 24 ms 15868 KB Output is correct
4 Correct 25 ms 16476 KB Output is correct
5 Correct 13 ms 13992 KB Output is correct
6 Correct 24 ms 19500 KB Output is correct
7 Correct 27 ms 25052 KB Output is correct

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -