Submission #945502

#	Time	Username	Problem	Language	Result	Execution time	Memory
945502		12345678	Fireworks (APIO16_fireworks)	C++17	0 / 100	3 ms	12892 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=3e5+5;

ll n, m, p, c, l[nx], r[nx], res[nx];
vector<pair<ll, ll>> d[nx];

void dfs(int u)
{
    if (u>n) return l[u]=r[u]=0, void();
    for (auto [v, w]:d[u]) 
    {
        dfs(v);
        l[v]+=w;
        r[v]+=w;
        res[u]+=res[v];
        //cout<<"compare "<<u<<' '<<v<<' '<<l[u]<<' '<<r[u]<<' '<<l[v]<<' '<<r[v]<<'\n';
        if (r[u]<l[v]) res[u]+=(l[v]-r[u]), l[u]=r[u], r[u]=l[v];
        else if (r[v]<l[u]) res[u]+=l[u]-r[v], r[u]=l[u], l[u]=r[v];
        else l[u]=max(l[u], l[v]), r[u]=min(r[u], r[v]);
        //cout<<u<<' '<<v<<' '<<l[u]<<' '<<r[u]<<'\n';
    }
    //cout<<u<<' '<<res[u]<<' '<<l[u]<<' '<<r[u]<<'\n';
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=2; i<=n+m; i++) cin>>p>>c, d[p].push_back({i, c});
    for (int i=1; i<=n; i++) l[i]=LLONG_MIN, r[i]=LLONG_MAX;
    dfs(1);
    cout<<res[1];
}

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