Submission #110001

#	Time	Username	Problem	Language	Result	Execution time	Memory
110001		nvmdava	Fireworks (APIO16_fireworks)	C++17	7 / 100	11 ms	7424 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 300005
#define ff first
#define ss second

int n, m;
vector<pair<int, ll> > child[N];
pair<ll, ll> bound[N];

ll get(int v, ll val){
    ll res = 0;
    for(auto x : child[v]){
        if(val <= bound[x.ff].ff) res += bound[x.ff].ff - val;
        else if(val >= bound[x.ff].ss) res += val - bound[x.ff].ss;
        else res += val;
    }
    return res;
}

ll dfs(int v){
    if(v > n){
        bound[v] = {0, 0};
        return 0;
    }
    ll res = 0;
    ll lll = LLONG_MAX, rrr = 0, m, l, r, L, R;
    for(auto x : child[v]){
        res += dfs(x.ff);
        bound[x.ff].ff += x.ss;
        bound[x.ff].ss += x.ss;
        lll = min(lll, bound[x.ff].ff);
        rrr = max(rrr, bound[x.ff].ss);
    }
    l = lll;
    r = rrr;
    while(l != r){
        m = (l + r) >> 1;
        if(get(v, m) < get(v, m + 1)) r = m;
        else l = m + 1;
    }
    L = l;
    R = l;

    while(lll != L){
        m = (lll + L) >> 1;
        if(get(v, m) == get(v, L)) L = m;
        else lll = m + 1;
    }
    while(rrr != R){
        m = (rrr + R + 1) >> 1;
        if(get(v, m) == get(v, R)) R = m;
        else rrr = m - 1;
    }

    bound[v].ff = L;
    bound[v].ss = R;
    res += get(v, L);
//    cout<<v<<' '<<L<<' '<<R<<' '<<res<<'\n';

    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;

    for(int i = 2; i <= n + m; i++){
        int p;
        ll c;
        cin>>p>>c;
        child[p].push_back({i, c});
    }

    cout<<dfs(1);
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45