oj.uz

Submission #1094523

# Submission time Handle Problem Language Result Execution time Memory
1094523 2024-09-29T18:50:40 Z vladilius Magic Tree (CEOI19_magictree) C++17
100 / 100
 341 ms 204368 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){
        if (get(1) >= x) return 0;
        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 = new node();
            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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 452 KB Output is correct
9 Correct 0 ms 460 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 76156 KB Output is correct
2 Correct 63 ms 45392 KB Output is correct
3 Correct 292 ms 204368 KB Output is correct
4 Correct 133 ms 94932 KB Output is correct
5 Correct 164 ms 97872 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 151 ms 55696 KB Output is correct
5 Correct 98 ms 47952 KB Output is correct
6 Correct 261 ms 83536 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 22496 KB Output is correct
2 Correct 47 ms 21544 KB Output is correct
3 Correct 49 ms 34128 KB Output is correct
4 Correct 35 ms 23252 KB Output is correct
5 Correct 51 ms 47780 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 452 KB Output is correct
9 Correct 0 ms 460 KB Output is correct
10 Correct 83 ms 40784 KB Output is correct
11 Correct 68 ms 34236 KB Output is correct
12 Correct 60 ms 37204 KB Output is correct
13 Correct 48 ms 35292 KB Output is correct
14 Correct 63 ms 48744 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4860 KB Output is correct
2 Correct 30 ms 15500 KB Output is correct
3 Correct 25 ms 15444 KB Output is correct
4 Correct 33 ms 15948 KB Output is correct
5 Correct 13 ms 13532 KB Output is correct
6 Correct 25 ms 19024 KB Output is correct
7 Correct 26 ms 24148 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 452 KB Output is correct
9 Correct 0 ms 460 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 151 ms 55696 KB Output is correct
14 Correct 98 ms 47952 KB Output is correct
15 Correct 261 ms 83536 KB Output is correct
16 Correct 83 ms 40784 KB Output is correct
17 Correct 68 ms 34236 KB Output is correct
18 Correct 60 ms 37204 KB Output is correct
19 Correct 48 ms 35292 KB Output is correct
20 Correct 63 ms 48744 KB Output is correct
21 Correct 38 ms 22096 KB Output is correct
22 Correct 120 ms 67924 KB Output is correct
23 Correct 193 ms 119504 KB Output is correct
24 Correct 341 ms 202572 KB Output is correct
25 Correct 137 ms 94416 KB Output is correct
26 Correct 236 ms 83916 KB Output is correct
27 Correct 256 ms 71628 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 452 KB Output is correct
9 Correct 0 ms 460 KB Output is correct
10 Correct 109 ms 76156 KB Output is correct
11 Correct 63 ms 45392 KB Output is correct
12 Correct 292 ms 204368 KB Output is correct
13 Correct 133 ms 94932 KB Output is correct
14 Correct 164 ms 97872 KB Output is correct
15 Correct 1 ms 860 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Correct 1 ms 860 KB Output is correct
18 Correct 151 ms 55696 KB Output is correct
19 Correct 98 ms 47952 KB Output is correct
20 Correct 261 ms 83536 KB Output is correct
21 Correct 47 ms 22496 KB Output is correct
22 Correct 47 ms 21544 KB Output is correct
23 Correct 49 ms 34128 KB Output is correct
24 Correct 35 ms 23252 KB Output is correct
25 Correct 51 ms 47780 KB Output is correct
26 Correct 83 ms 40784 KB Output is correct
27 Correct 68 ms 34236 KB Output is correct
28 Correct 60 ms 37204 KB Output is correct
29 Correct 48 ms 35292 KB Output is correct
30 Correct 63 ms 48744 KB Output is correct
31 Correct 6 ms 4860 KB Output is correct
32 Correct 30 ms 15500 KB Output is correct
33 Correct 25 ms 15444 KB Output is correct
34 Correct 33 ms 15948 KB Output is correct
35 Correct 13 ms 13532 KB Output is correct
36 Correct 25 ms 19024 KB Output is correct
37 Correct 26 ms 24148 KB Output is correct
38 Correct 38 ms 22096 KB Output is correct
39 Correct 120 ms 67924 KB Output is correct
40 Correct 193 ms 119504 KB Output is correct
41 Correct 341 ms 202572 KB Output is correct
42 Correct 137 ms 94416 KB Output is correct
43 Correct 236 ms 83916 KB Output is correct
44 Correct 256 ms 71628 KB Output is correct
45 Correct 38 ms 21332 KB Output is correct
46 Correct 118 ms 66384 KB Output is correct
47 Correct 180 ms 113616 KB Output is correct
48 Correct 316 ms 190292 KB Output is correct
49 Correct 145 ms 94928 KB Output is correct
50 Correct 240 ms 86640 KB Output is correct
51 Correct 258 ms 75220 KB Output is correct