oj.uz

Submission #945502

# Submission time Handle Problem Language Result Execution time Memory
945502 2024-03-14T01:52:16 Z 12345678 Fireworks (APIO16_fireworks) C++17
0 / 100
 3 ms 12892 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Incorrect 2 ms 12892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Incorrect 2 ms 12892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Incorrect 2 ms 12892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Incorrect 2 ms 12892 KB Output isn't correct
3 Halted 0 ms 0 KB -