oj.uz

Submission #199380

# Submission time Handle Problem Language Result Execution time Memory
199380 2020-01-31T21:06:42 Z gs18115 Fireworks (APIO16_fireworks) C++14
7 / 100
 26 ms 26360 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
vector<pl>adj[300010];
priority_queue<ll,vector<ll>,less<ll> >pq1[300010];
priority_queue<ll,vector<ll>,greater<ll> >pq2[300010];
int pct;
int pn[300010];
ll b[300010];
ll ans;
inline void in1(int n,ll x)
{
    if(x>pq2[n].top()+b[n])
    {
        ans+=x-(pq2[n].top()+b[n]);
        pq2[n].ep(x-b[n]);
        pq1[n].ep(pq2[n].top());
        pq2[n].pop();
    }
    else
        pq1[n].ep(x-b[n]);
    return;
}
inline void in2(int n,ll x)
{
    if(x<pq1[n].top()+b[n])
    {
        ans+=(pq1[n].top()+b[n])-x;
        pq1[n].ep(x-b[n]);
        pq2[n].ep(pq1[n].top());
        pq1[n].pop();
    }
    else
        pq2[n].ep(x-b[n]);
    return;
}
void dfs(int x)
{
    if(adj[x].empty())
    {
        pn[x]=pct++;
        pq1[pn[x]].ep(0);
        pq2[pn[x]].ep(0);
        return;
    }
    int sz=-1;
    for(pl&t:adj[x])
    {
        dfs(t.fi);
        b[pn[t.fi]]+=t.se;
        ll l=pq1[pn[t.fi]].top();
        while(pq1[pn[t.fi]].top()>l-t.se)
            pq1[pn[t.fi]].pop(),pq1[pn[t.fi]].ep(l-t.se);
        pq1[pn[t.fi]].pop();
        pq1[pn[t.fi]].ep(l);
        l=pq2[pn[t.fi]].top();
        while(!pq2[pn[t.fi]].empty())
            pq2[pn[t.fi]].pop();
        pq2[pn[t.fi]].ep(l);
        if(sz<(int)pq1[pn[t.fi]].size())
            sz=pq1[pn[x]=pn[t.fi]].size();
    }
    for(pl&t:adj[x])
    {
        if(pn[x]==pn[t.fi])
            continue;
        while(!pq1[pn[t.fi]].empty())
            in1(pn[x],pq1[pn[t.fi]].top()+b[pn[t.fi]]),pq1[pn[t.fi]].pop();
        while(!pq2[pn[t.fi]].empty())
            in2(pn[x],pq2[pn[t.fi]].top()+b[pn[t.fi]]),pq2[pn[t.fi]].pop();
    }
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int v,c,p;
    cin>>v>>c;
    v+=c;
    for(int i=1;i++<v;)
        cin>>p>>c,adj[p].eb(i,c);
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26104 KB Output is correct
2 Correct 20 ms 26232 KB Output is correct
3 Correct 20 ms 26232 KB Output is correct
4 Correct 20 ms 26232 KB Output is correct
5 Correct 20 ms 26360 KB Output is correct
6 Correct 21 ms 26232 KB Output is correct
7 Correct 21 ms 26232 KB Output is correct
8 Correct 21 ms 26232 KB Output is correct
9 Correct 21 ms 26232 KB Output is correct
10 Correct 25 ms 26232 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 26232 KB Output is correct
2 Correct 20 ms 26236 KB Output is correct
3 Incorrect 21 ms 26232 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26104 KB Output is correct
2 Correct 20 ms 26232 KB Output is correct
3 Correct 20 ms 26232 KB Output is correct
4 Correct 20 ms 26232 KB Output is correct
5 Correct 20 ms 26360 KB Output is correct
6 Correct 21 ms 26232 KB Output is correct
7 Correct 21 ms 26232 KB Output is correct
8 Correct 21 ms 26232 KB Output is correct
9 Correct 21 ms 26232 KB Output is correct
10 Correct 25 ms 26232 KB Output is correct
11 Correct 26 ms 26232 KB Output is correct
12 Correct 20 ms 26236 KB Output is correct
13 Incorrect 21 ms 26232 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26104 KB Output is correct
2 Correct 20 ms 26232 KB Output is correct
3 Correct 20 ms 26232 KB Output is correct
4 Correct 20 ms 26232 KB Output is correct
5 Correct 20 ms 26360 KB Output is correct
6 Correct 21 ms 26232 KB Output is correct
7 Correct 21 ms 26232 KB Output is correct
8 Correct 21 ms 26232 KB Output is correct
9 Correct 21 ms 26232 KB Output is correct
10 Correct 25 ms 26232 KB Output is correct
11 Correct 26 ms 26232 KB Output is correct
12 Correct 20 ms 26236 KB Output is correct
13 Incorrect 21 ms 26232 KB Output isn't correct
14 Halted 0 ms 0 KB -