Submission #109999

#	Time	Username	Problem	Language	Result	Execution time	Memory
109999		nvmdava	Fireworks (APIO16_fireworks)	C++17	0 / 100	2037 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, l1, r1, 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 = R = lll;
    for(ll i = lll; i <= rrr; i++){
        if(get(v, L) > get(v, i)) L = i;
        if(get(v, R) >= get(v, i)) R = i;
    }

    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);
}

Compilation message (stderr)

fireworks.cpp: In function 'long long int dfs(int)':
fireworks.cpp:28:34: warning: unused variable 'l1' [-Wunused-variable]
     ll lll = LLONG_MAX, rrr = 0, l1, r1, l, r, L, R;
                                  ^~
fireworks.cpp:28:38: warning: unused variable 'r1' [-Wunused-variable]
     ll lll = LLONG_MAX, rrr = 0, l1, r1, l, r, L, R;
                                      ^~
fireworks.cpp:28:42: warning: unused variable 'l' [-Wunused-variable]
     ll lll = LLONG_MAX, rrr = 0, l1, r1, l, r, L, R;
                                          ^
fireworks.cpp:28:45: warning: unused variable 'r' [-Wunused-variable]
     ll lll = LLONG_MAX, rrr = 0, l1, r1, l, r, L, R;
                                             ^

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