Submission #109858

#	Time	Username	Problem	Language	Result	Execution time	Memory
109858		Alexa2001	Fireworks (APIO16_fireworks)	C++17	7 / 100	18 ms	14592 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Nmax = 6e5 + 5;

vector<int> v[Nmax];
ll opt[Nmax], A[Nmax], B[Nmax];
int up[Nmax];
int n, m;


ll moove(ll x, ll l, ll r)
{
    if(x < l) return l - x;
    if(x > r) return x - r;
    return 0;
}

void dfs(int node)
{
    if(v[node].empty())
    {
        opt[node] = 0;
        A[node] = up[node];
        B[node] = up[node];
        return;
    }

    for(auto son : v[node]) dfs(son);

    map<ll,int> change;

    for(auto son : v[node])
    {
        change[0] -= 1;
        change[A[son]] += 1;
        change[B[son]] += 1;
    }

    int sum = 0;
    ll L = -1, R = -1;

    for(auto &it : change)
    {
        sum += it.second;
        it.second = sum;

        if(it.second >= 0 && L == -1) L = it.first;
        if(it.second > 0  && R == -1) R = it.first;
    }

    A[node] = L;
    B[node] = R;

    ll s2 = 0;

    for(auto son : v[node])
    {
        opt[node] += opt[son] + moove(L, A[son], B[son]);
        s2 += opt[son] + moove(R, A[son], B[son]);
    }

    assert(opt[node] == s2);

    A[node] += up[node];
    B[node] += up[node];
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    int i, x;

    cin >> n >> m; n += m;

    for(i=2; i<=n; ++i)
    {
        cin >> x >> up[i];
        v[x].push_back(i);
    }

    dfs(1);
    cout << opt[1] << '\n';

    return 0;
}

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