oj.uz

Submission #109999

# Submission time Handle Problem Language Result Execution time Memory
109999 2019-05-08T15:12:11 Z nvmdava Fireworks (APIO16_fireworks) C++17
0 / 100
 2000 ms 7424 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7424 KB Output is correct
2 Execution timed out 2037 ms 7424 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7424 KB Output is correct
2 Execution timed out 2037 ms 7424 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7424 KB Output is correct
2 Execution timed out 2037 ms 7424 KB Time limit exceeded
3 Halted 0 ms 0 KB -