oj.uz

Submission #958676

# Submission time Handle Problem Language Result Execution time Memory
958676 2024-04-06T10:15:33 Z ro9669 Magic Tree (CEOI19_magictree) C++17
58 / 100
 1266 ms 1048576 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) (int)v.size()
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
using namespace std;

typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;

const int maxN = int(1e5)+1;

int n , m , k;
int p[maxN] , d[maxN] , w[maxN];
vector<int> g[maxN];

struct node{
    int l , r , lef , rig;
    ll val , lazy_gan , lazy_add;
    node(){}
    node(int _l , int _r , int _lef , int _rig , ll _val , ll _lazy_gan , ll _lazy_add){
        l = _l; r = _r; lef = _lef; rig = _rig;
        val = _val; lazy_gan = _lazy_gan; lazy_add = _lazy_add;
    }
};

struct segtree{
    vector<node> st;

    void refine_gan(int id , ll val){
        st[id].val = val;
        st[id].lazy_gan = val;
        st[id].lazy_add = 0;
    }

    void refine_add(int id , ll val){
        st[id].val += val;
        if (st[id].lazy_gan != 0){
            st[id].lazy_gan += val;
            st[id].lazy_add = 0;
        }
        else{
            st[id].lazy_add += val;
        }
    }

    void down(int id){
        if (st[id].l == st[id].r) return;
        int mid = (st[id].l + st[id].r) / 2;
        if (st[id].lef == -1){
            st[id].lef = sz(st);
            st.push_back(node(st[id].l , mid , -1 , -1 , 0 , 0 , 0));
        }
        if (st[id].rig == -1){
            st[id].rig = sz(st);
            st.push_back(node(mid + 1 , st[id].r , -1 , -1 , 0 , 0 , 0));
        }
        if (st[id].lazy_gan != 0){
            refine_gan(st[id].lef , st[id].lazy_gan);
            refine_gan(st[id].rig , st[id].lazy_gan);
        }
        if (st[id].lazy_add != 0){
            refine_add(st[id].lef , st[id].lazy_add);
            refine_add(st[id].rig , st[id].lazy_add);
        }
        st[id].lazy_gan = st[id].lazy_add = 0;
    }

    void update_gan(int id , int u , int v , ll val){
        if (v < st[id].l || st[id].r < u) return;
        if (u <= st[id].l && st[id].r <= v) return refine_gan(id , val);
        down(id);
        update_gan(st[id].lef , u , v , val);
        update_gan(st[id].rig , u , v , val);
        st[id].val = max(st[st[id].lef].val , st[st[id].rig].val);
    }

    void update_add(int id , int u , int v , ll val){
        if (v < st[id].l || st[id].r < u) return;
        if (u <= st[id].l && st[id].r <= v) return refine_add(id , val);
        down(id);
        update_add(st[id].lef , u , v , val);
        update_add(st[id].rig , u , v , val);
        st[id].val = max(st[st[id].lef].val , st[st[id].rig].val);
    }

    ll get(int id , int u , int v){
        if (v < st[id].l || st[id].r < u) return 0;
        if (u <= st[id].l && st[id].r <= v) return st[id].val;
        down(id);
        ll A = get(st[id].lef , u , v);
        ll B = get(st[id].rig , u , v);
        return max(A , B);
    }
} seg[maxN];

set<int> s[maxN];

void dfs(int u){
    for (int v : g[u]){
        dfs(v);
        if (sz(s[u]) < sz(s[v])){
            swap(s[u] , s[v]);
            swap(seg[u].st , seg[v].st);
        }
        for (auto cur = s[v].begin() ; cur != s[v].end() ; cur++){
            if (cur != prev(s[v].end())){
                auto nxt = next(cur);
                seg[u].update_add(0 , *cur , *nxt - 1 , seg[v].get(0 , *cur , *cur));
            }
            else{
                seg[u].update_add(0 , *cur , k , seg[v].get(0 , *cur , *cur));
            }
            s[u].insert(*cur);
        }
        s[v].clear();
        seg[v].st.clear();
    }
    if (d[u] > 0){
        s[u].insert(d[u]);
        int lef = d[u] , rig = k , pos = -1;
        ll val = seg[u].get(0 , d[u] , d[u]) + 1ll * w[u];
        while (lef <= rig){
            int mid = (lef + rig) / 2;
            if (seg[u].get(0 , mid , mid) <= val){
                pos = mid;
                lef = mid + 1;
            }
            else{
                rig = mid - 1;
            }
        }
        if (pos != -1){
            seg[u].update_gan(0 , d[u] , pos , val);
        }
    }
//    cout << u << "\n";
//    for (int i = 1 ; i <= k ; i++) cout << seg[u].get(0 , i , i) << " ";
//    cout << "\n";
}

void solve(){
    cin >> n >> m >> k;
    for (int i = 1 ; i < n ; i++){
        cin >> p[i];
        g[p[i]].push_back(i + 1);
    }
    for (int i = 1 ; i <= n ; i++){
        d[i] = w[i] = 0;
    }
    for (int i = 1 ; i <= m ; i++){
        int x; cin >> x;
        cin >> d[x] >> w[x];
    }
    for (int i = 1 ; i <= n ; i++) seg[i].st.push_back(node(1 , k , -1 , -1 , 0 , 0 , 0));
    dfs(1);
    cout << seg[1].st[0].val << "\n";
}

#define name "templete"

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen(name".inp" , "r" , stdin);
    // freopen(name".out" , "w" , stdout);
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10796 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 440232 KB Output is correct
2 Correct 286 ms 314584 KB Output is correct
3 Runtime error 1206 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11100 KB Output is correct
2 Correct 5 ms 11196 KB Output is correct
3 Correct 3 ms 11100 KB Output is correct
4 Correct 431 ms 51628 KB Output is correct
5 Correct 360 ms 50244 KB Output is correct
6 Correct 630 ms 49972 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 26576 KB Output is correct
2 Correct 55 ms 19280 KB Output is correct
3 Correct 59 ms 30288 KB Output is correct
4 Correct 50 ms 29700 KB Output is correct
5 Correct 48 ms 37976 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10796 KB Output is correct
10 Correct 178 ms 83328 KB Output is correct
11 Correct 143 ms 57760 KB Output is correct
12 Correct 93 ms 46580 KB Output is correct
13 Correct 142 ms 115160 KB Output is correct
14 Correct 76 ms 37460 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23992 KB Output is correct
2 Correct 43 ms 29100 KB Output is correct
3 Correct 45 ms 30060 KB Output is correct
4 Correct 46 ms 33384 KB Output is correct
5 Correct 27 ms 30868 KB Output is correct
6 Correct 42 ms 32100 KB Output is correct
7 Correct 42 ms 33220 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10796 KB Output is correct
10 Correct 4 ms 11100 KB Output is correct
11 Correct 5 ms 11196 KB Output is correct
12 Correct 3 ms 11100 KB Output is correct
13 Correct 431 ms 51628 KB Output is correct
14 Correct 360 ms 50244 KB Output is correct
15 Correct 630 ms 49972 KB Output is correct
16 Correct 178 ms 83328 KB Output is correct
17 Correct 143 ms 57760 KB Output is correct
18 Correct 93 ms 46580 KB Output is correct
19 Correct 142 ms 115160 KB Output is correct
20 Correct 76 ms 37460 KB Output is correct
21 Correct 140 ms 113744 KB Output is correct
22 Correct 487 ms 310236 KB Output is correct
23 Correct 811 ms 678948 KB Output is correct
24 Runtime error 1266 ms 1048576 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10796 KB Output is correct
10 Correct 500 ms 440232 KB Output is correct
11 Correct 286 ms 314584 KB Output is correct
12 Runtime error 1206 ms 1048576 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -