Submission #958678

#	Time	Username	Problem	Language	Result	Execution time	Memory
958678		ro9669	Magic Tree (CEOI19_magictree)	C++17	58 / 100	1238 ms	1048576 KiB

magictree

#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 / 6
• Subtask 2: 0 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17