oj.uz

Submission #952884

# Submission time Handle Problem Language Result Execution time Memory
952884 2024-03-25T04:08:03 Z ttamx Fireworks (APIO16_fireworks) C++17
7 / 100
 16 ms 68864 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int N=6e5+5;

int n,m;
vector<pair<int,int>> adj[N];
int sz[N],hv[N];

struct SlopeTirck{
    int sz;
    ll lz,mn;
    priority_queue<ll> pl;
    priority_queue<ll,vector<ll>,greater<ll>> pr;
    SlopeTirck():lz(0),mn(0),pl(),pr(){}
    void insertpoint(ll x){
        if(pl.empty()||x<=pl.top()+lz){
            pl.emplace(x-lz);
        }else{
            pr.emplace(x-lz);
        }
        if(pl.size()>pr.size()){
            pr.emplace(pl.top());
            pl.pop();
        }else if(pl.size()<pr.size()){
            pl.emplace(pr.top());
            pr.pop();
        }
        sz++;
    }
    void insert(ll x){
        if(!pl.empty())mn+=max(pl.top()+lz-x,0LL);
        if(!pr.empty())mn+=max(x-pr.top()-lz,0LL);
        insertpoint(x);
        insertpoint(x);
    }
    void merge(SlopeTirck &o){
        if(!pl.empty()&&!o.pr.empty())mn+=max(pl.top()+lz-o.pr.top()-o.lz,0LL);
        if(!pr.empty()&&!o.pl.empty())mn+=max(o.pl.top()+o.lz-pr.top()-lz,0LL);
        while(!o.pl.empty()){
            insertpoint(o.pl.top()+o.lz);
            o.pl.pop();
        }
        while(!o.pr.empty()){
            insertpoint(o.pr.top()+o.lz);
            o.pr.pop();
        }
        mn+=o.mn;
    }
    void shift(ll x){
        lz+=x;
    }
    void shrink(){
        ll l=pl.top(),r=pr.top();
        while(!pl.empty())pl.pop();
        while(!pr.empty())pr.pop();
        pl.emplace(l),pr.emplace(r);
    }
}dp[N];

void dfs(int u){
    for(auto [v,w]:adj[u]){
        dfs(v);
        dp[v].shift(w);
        dp[u].merge(dp[v]);
    }
    dp[u].shrink();
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=2;i<=n+m;i++){
        int p,c;
        cin >> p >> c;
        adj[p].emplace_back(i,c);
    }
    for(int i=1;i<=m;i++)dp[n+i].insert(0);
    dfs(1);
    cout << dp[1].mn;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 68700 KB Output is correct
2 Correct 16 ms 68700 KB Output is correct
3 Correct 14 ms 68864 KB Output is correct
4 Correct 14 ms 68864 KB Output is correct
5 Correct 14 ms 68700 KB Output is correct
6 Correct 14 ms 68784 KB Output is correct
7 Correct 14 ms 68700 KB Output is correct
8 Correct 14 ms 68816 KB Output is correct
9 Correct 14 ms 68700 KB Output is correct
10 Correct 15 ms 68864 KB Output is correct

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 68700 KB Output is correct
2 Correct 16 ms 68700 KB Output is correct
3 Correct 14 ms 68864 KB Output is correct
4 Correct 14 ms 68864 KB Output is correct
5 Correct 14 ms 68700 KB Output is correct
6 Correct 14 ms 68784 KB Output is correct
7 Correct 14 ms 68700 KB Output is correct
8 Correct 14 ms 68816 KB Output is correct
9 Correct 14 ms 68700 KB Output is correct
10 Correct 15 ms 68864 KB Output is correct
11 Incorrect 15 ms 68700 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 68700 KB Output is correct
2 Correct 16 ms 68700 KB Output is correct
3 Correct 14 ms 68864 KB Output is correct
4 Correct 14 ms 68864 KB Output is correct
5 Correct 14 ms 68700 KB Output is correct
6 Correct 14 ms 68784 KB Output is correct
7 Correct 14 ms 68700 KB Output is correct
8 Correct 14 ms 68816 KB Output is correct
9 Correct 14 ms 68700 KB Output is correct
10 Correct 15 ms 68864 KB Output is correct
11 Incorrect 15 ms 68700 KB Output isn't correct
12 Halted 0 ms 0 KB -