oj.uz

Submission #110001

# Submission time Handle Problem Language Result Execution time Memory
110001 2019-05-08T15:35:09 Z nvmdava Fireworks (APIO16_fireworks) C++17
7 / 100
 11 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, 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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 10 ms 7424 KB Output is correct
5 Correct 10 ms 7424 KB Output is correct
6 Correct 10 ms 7424 KB Output is correct
7 Correct 9 ms 7424 KB Output is correct
8 Correct 11 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 9 ms 7424 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 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 11 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 10 ms 7424 KB Output is correct
5 Correct 10 ms 7424 KB Output is correct
6 Correct 10 ms 7424 KB Output is correct
7 Correct 9 ms 7424 KB Output is correct
8 Correct 11 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 9 ms 7424 KB Output is correct
11 Incorrect 9 ms 7424 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 10 ms 7424 KB Output is correct
5 Correct 10 ms 7424 KB Output is correct
6 Correct 10 ms 7424 KB Output is correct
7 Correct 9 ms 7424 KB Output is correct
8 Correct 11 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 9 ms 7424 KB Output is correct
11 Incorrect 9 ms 7424 KB Output isn't correct
12 Halted 0 ms 0 KB -