Submission #570006

#	Time	Username	Problem	Language	Result	Execution time	Memory
570006		Redhood	Magic Tree (CEOI19_magictree)	C++14	100 / 100	431 ms	36136 KiB

magictree

#include<bits/stdc++.h>

#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pb push_back
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef long double ld;

using namespace std;


const int N = (int)1e5 + 10;
const ll inf = 1e18;
struct node{
    ll eq=-1;
    ll add;
    ll pushmx;
    node(){
        eq = 0;
        add = 0;
        pushmx = 0;
    }
};
node seg[4*N];

void push(int v){
    int v1 = v << 1;
    for(auto &u : {v1 , v1|1}){
        if(seg[v].eq != -1){
            seg[u].eq=seg[v].eq,seg[u].add=0,seg[u].pushmx=seg[v].pushmx;
        }else{
            if(seg[u].eq!=-1)
                seg[u].eq+=seg[v].add,seg[u].pushmx+=seg[v].add;
            else{
                seg[u].add+=seg[v].add;
                seg[u].pushmx+=seg[v].add;
            }
            seg[u].pushmx=max(seg[u].pushmx,seg[v].pushmx);
        }
    }
    seg[v].eq = -1;
    seg[v].add = 0;
    seg[v].pushmx = 0;
}

void doadd(int v , int tl , int tr , int l , int r , ll x){
    if(tl == l && tr == r){
        if(seg[v].eq!=-1){
            seg[v].eq += x;
        }else
            seg[v].add += x;
        seg[v].pushmx += x;
        return;
    }
    push(v);
    int mid = (tl + tr) >> 1, v1 = v << 1;
    if(l <= mid)
        doadd(v1 , tl , mid , l , min(r , mid) , x);
    if(r > mid)
        doadd(v1|1, mid + 1 , tr , max(l , mid + 1) , r , x);
//    pull(v);
}
ll get(int v , int tl , int tr , int pos){
    if(tl == tr){
        return seg[v].pushmx;
    }
    push(v);
    int mid = (tl + tr) >> 1, v1 = v << 1;
    if(pos <= mid)
        return get(v1, tl , mid , pos);
    return get(v1|1,mid+1,tr,pos);
}
void domx(int v , int tl, int tr , int l , int r , ll x){
    if(tl == l && tr == r){
        seg[v].pushmx = max(seg[v].pushmx , x);
        return;
    }
    push(v);
    int mid = (tl + tr) >> 1 , v1 = v << 1;
    if(l <= mid)
        domx(v1 , tl , mid , l , min(r , mid) , x);
    if(r > mid)
        domx(v1|1,mid+1,tr,max(l,mid+1),r,x);
}
vector < int > g[N];
int ripeday[N], w[N];
vector < int > *vert[N];
vector<pair<int,ll>>temp[N];
int sz[N];
void sizes(int v){
    sz[v] = 1;
    for(auto &u : g[v]){
        sizes(u);
        sz[v] += sz[u];
    }
}
void gozero(){
    seg[1].eq = 0;
    seg[1].add=0,seg[1].pushmx=0;
}
void dfs(int v){
//    cerr << v << ' ' << endl;
    int big = -1;
    for(auto &u : g[v]){
        if(big == -1 || sz[u] > sz[big])
            big = u;
    }
    for(auto &u : g[v]){
        if(u != big){
            /// what do we do man?
            dfs(u);
            /// okay now
            if(vert[u]!=nullptr){
                for(auto &d : (*vert[u])){
                    ll x = get(1,0,N-1,d);
                    temp[u].push_back({d , x});
                }
            }
            gozero();
        }
    }
    if(big == -1){
        if(ripeday[v] != -1){
            doadd(1,0,N-1, ripeday[v], N-1, w[v]);
            vert[v] = new vector<int>;
            (*vert[v]).push_back(ripeday[v]);
        }
    }else{
        dfs(big);
        vert[v] = vert[big];
        if(vert[v] == nullptr)
            vert[v] = new vector < int >;
        for(auto &u : g[v]){
            if(u != big){
                if(temp[u].empty())continue;
                sort(all(temp[u]));
                temp[u].erase(unique(all(temp[u])) , temp[u].end());
                int prv = -1;
                for(int i = 0; i < sz(temp[u]); ++i){
                    if(i - 1 >= 0){
//                        assert(temp[u][i-1].se <= temp[u][i].se);
//                        assert(temp[u][i-1].fi != temp[u][i].fi);
                    }
                    int rb = (i == sz(temp[u]) - 1 ? N-1 : temp[u][i + 1].fi - 1);
                    doadd(1 , 0 , N - 1, temp[u][i].fi, rb, temp[u][i].se);
                }
                temp[u].clear();
                for(auto &x : (*vert[u]))
                    (*vert[v]).push_back(x);
            }
        }
        if(ripeday[v] != -1){
            ll t = get(1 , 0 , N - 1 , ripeday[v]);
            t += w[v];
            domx(1 , 0 , N -1 , ripeday[v], N - 1 , t);
            (*vert[v]).push_back(ripeday[v]);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(0), cin.tie(0) , cout.tie(0);
    int n , m, k;
    cin >> n >> m >> k;
    for(int i = 1; i < n; ++i){
        int p;cin >> p, --p;
        g[p].pb(i);
    }
    fill(ripeday , ripeday + N , -1);
    for(int i = 0; i < m; ++i){
        int v , d;
        cin >> v >> d;
        --v;
        cin >> w[v];
        ripeday[v] = d;
    }
    sizes(0);
    dfs(0);
    ll ans = 0;
    for(int t=0;t<N-1;++t){
        ans = max(ans , get(1 , 0 , N - 1, t));
    }
    cout << ans;

    return 0;
}
/*
5 1 1
1 2 1 1
2 3 1

*/

Compilation message (stderr)

magictree.cpp: In function 'void dfs(int)':
magictree.cpp:141:21: warning: unused variable 'prv' [-Wunused-variable]
  141 |                 int prv = -1;
      |                     ^~~

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17