oj.uz

Submission #945503

# Submission time Handle Problem Language Result Execution time Memory
945503 2024-03-14T01:56:48 Z 12345678 Fireworks (APIO16_fireworks) C++17
7 / 100
 8 ms 27332 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];
        if (pql[v].size()>pql[u].size()) swap(pql[u], pql[v]), swap(pqr[u], pqr[v]), swap(lz[u], lz[v]);
        //cout<<"here "<<u<<' '<<v<<' '<<pql[u].size()<<' '<<pql[v].size()<<'\n';
        map<ll, ll> mp;
        while (!pql[v].empty()) mp[pql[v].top()+lz[v]]++, pql[v].pop();
        while (!pqr[v].empty()) mp[pqr[v].top()+lz[v]]++, pqr[v].pop();
        for (auto [x, y]:mp)
        {
            for (int i=0; i<y; i+=2)
            {
                //cout<<"add "<<u<<' '<<lz[u]<<' '<<x<<' '<<y<<' '<<i<<'\n';
                ll cur=x;
                if (pql[u].top()+lz[u]<=cur&&cur<=pqr[u].top()+lz[u]) res[u]+=0;
                else res[u]+=min(abs(cur-(pql[u].top()+lz[u])), abs(cur-(pqr[u].top()+lz[u])));
                if (cur-lz[u]>=pqr[u].top()) pqr[u].push(cur-lz[u]), pqr[u].push(cur-lz[u]);
                else pql[u].push(cur-lz[u]), pql[u].push(cur-lz[u]);
                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<<"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 7 ms 27228 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 6 ms 27316 KB Output is correct
4 Correct 5 ms 27228 KB Output is correct
5 Correct 5 ms 27316 KB Output is correct
6 Correct 6 ms 27228 KB Output is correct
7 Correct 6 ms 27228 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 8 ms 27228 KB Output is correct
10 Correct 5 ms 27332 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 27228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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