oj.uz

Submission #958678

# Submission time Handle Problem Language Result Execution time Memory
958678 2024-04-06T10:16:31 Z ro9669 Magic Tree (CEOI19_magictree) C++17
58 / 100
 1238 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 3 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 439004 KB Output is correct
2 Correct 314 ms 313796 KB Output is correct
3 Runtime error 1060 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 4 ms 11100 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 381 ms 48444 KB Output is correct
5 Correct 363 ms 48296 KB Output is correct
6 Correct 624 ms 48624 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 24308 KB Output is correct
2 Correct 62 ms 17232 KB Output is correct
3 Correct 68 ms 27956 KB Output is correct
4 Correct 51 ms 28124 KB Output is correct
5 Correct 49 ms 35924 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 3 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 168 ms 81748 KB Output is correct
11 Correct 139 ms 56292 KB Output is correct
12 Correct 92 ms 44848 KB Output is correct
13 Correct 136 ms 114008 KB Output is correct
14 Correct 64 ms 36052 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23732 KB Output is correct
2 Correct 59 ms 28780 KB Output is correct
3 Correct 43 ms 29492 KB Output is correct
4 Correct 48 ms 32884 KB Output is correct
5 Correct 27 ms 30612 KB Output is correct
6 Correct 53 ms 31436 KB Output is correct
7 Correct 46 ms 32456 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 3 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 4 ms 11100 KB Output is correct
11 Correct 4 ms 11100 KB Output is correct
12 Correct 4 ms 11100 KB Output is correct
13 Correct 381 ms 48444 KB Output is correct
14 Correct 363 ms 48296 KB Output is correct
15 Correct 624 ms 48624 KB Output is correct
16 Correct 168 ms 81748 KB Output is correct
17 Correct 139 ms 56292 KB Output is correct
18 Correct 92 ms 44848 KB Output is correct
19 Correct 136 ms 114008 KB Output is correct
20 Correct 64 ms 36052 KB Output is correct
21 Correct 145 ms 113332 KB Output is correct
22 Correct 412 ms 309076 KB Output is correct
23 Correct 806 ms 678636 KB Output is correct
24 Runtime error 1238 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 3 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 487 ms 439004 KB Output is correct
11 Correct 314 ms 313796 KB Output is correct
12 Runtime error 1060 ms 1048576 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -