oj.uz

Submission #945504

# Submission time Handle Problem Language Result Execution time Memory
945504 2024-03-14T02:07:29 Z 12345678 Fireworks (APIO16_fireworks) C++17
7 / 100
 8 ms 27480 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=3e5+5;

ll n, m, p, c, lz[nx], res[nx];
vector<pair<ll, ll>> d[nx];
priority_queue<ll> pql[nx];
priority_queue<ll, vector<ll>, greater<ll>> pqr[nx];

void dfs(int u)
{
    if (u>n) return pql[u].push(0), pqr[u].push(0), void();
    for (auto [v, w]:d[u]) 
    {
        dfs(v);
        lz[v]+=w;
        res[u]+=res[v];
        ll upd[2]={pql[v].top()+lz[v], pqr[v].top()+lz[v]};
        if (pql[u].empty()) 
        {
            pql[u].push(upd[0]);
            pqr[u].push(upd[1]);
            continue;
        }
        ll cl=pql[u].top(), cr=pqr[u].top();
        if (cr<upd[0]) res[u]+=(upd[0]-cr);
        else if (upd[1]<cl) res[u]+=cl-upd[1];
        if (upd[0]>=pqr[u].top()) pqr[u].push(upd[0]);
        else pql[u].push(upd[0]);
        if (upd[1]>=pqr[u].top()) pqr[u].push(upd[1]);
        else pql[u].push(upd[1]);
        while (pql[u].size()>pqr[u].size()) pqr[u].push(pql[u].top()), pql[u].pop();
        while (pqr[u].size()>pql[u].size()) pql[u].push(pqr[u].top()), pqr[u].pop();
        //cout<<"size "<<pql[u].size()<<' '<<pqr[u].size()<<'\n';
    }
    //cout<<res[u]<<'\n';
    /*
    cout<<"debug : "<<u<<'\n';
    cout<<"l : ";
    priority_queue<ll> l=pql[u];
    priority_queue<ll, vector<ll>, greater<ll>> r=pqr[u];
    while (!l.empty()) cout<<l.top()+lz[u]<<' ', l.pop();
    cout<<'\n';
    cout<<"r : ";
    while (!r.empty()) cout<<r.top()+lz[u]<<' ', r.pop();
    cout<<'\n';
    cout<<"res "<<u<<' '<<res[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});
    dfs(1);
    cout<<res[1];
}

/*

*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 27228 KB Output is correct
2 Correct 6 ms 27320 KB Output is correct
3 Correct 6 ms 27228 KB Output is correct
4 Correct 5 ms 27228 KB Output is correct
5 Correct 6 ms 27228 KB Output is correct
6 Correct 6 ms 27480 KB Output is correct
7 Correct 6 ms 27228 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 7 ms 27324 KB Output is correct
10 Correct 5 ms 27228 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27228 KB Output is correct
2 Correct 5 ms 27268 KB Output is correct
3 Incorrect 6 ms 27316 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 27228 KB Output is correct
2 Correct 6 ms 27320 KB Output is correct
3 Correct 6 ms 27228 KB Output is correct
4 Correct 5 ms 27228 KB Output is correct
5 Correct 6 ms 27228 KB Output is correct
6 Correct 6 ms 27480 KB Output is correct
7 Correct 6 ms 27228 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 7 ms 27324 KB Output is correct
10 Correct 5 ms 27228 KB Output is correct
11 Correct 6 ms 27228 KB Output is correct
12 Correct 5 ms 27268 KB Output is correct
13 Incorrect 6 ms 27316 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 27228 KB Output is correct
2 Correct 6 ms 27320 KB Output is correct
3 Correct 6 ms 27228 KB Output is correct
4 Correct 5 ms 27228 KB Output is correct
5 Correct 6 ms 27228 KB Output is correct
6 Correct 6 ms 27480 KB Output is correct
7 Correct 6 ms 27228 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 7 ms 27324 KB Output is correct
10 Correct 5 ms 27228 KB Output is correct
11 Correct 6 ms 27228 KB Output is correct
12 Correct 5 ms 27268 KB Output is correct
13 Incorrect 6 ms 27316 KB Output isn't correct
14 Halted 0 ms 0 KB -