oj.uz

Submission #952880

# Submission time Handle Problem Language Result Execution time Memory
952880 2024-03-25T04:05:37 Z ttamx Fireworks (APIO16_fireworks) C++17
7 / 100
 33 ms 68952 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);
        if(dp[v].sz>dp[u].sz)swap(dp[u],dp[v]);
        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 33 ms 68772 KB Output is correct
2 Correct 16 ms 68856 KB Output is correct
3 Correct 15 ms 68864 KB Output is correct
4 Correct 16 ms 68868 KB Output is correct
5 Correct 16 ms 68800 KB Output is correct
6 Correct 15 ms 68712 KB Output is correct
7 Correct 16 ms 68700 KB Output is correct
8 Correct 14 ms 68952 KB Output is correct
9 Correct 15 ms 68700 KB Output is correct
10 Correct 16 ms 68696 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 68696 KB Output is correct
2 Correct 14 ms 68700 KB Output is correct
3 Incorrect 15 ms 68816 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 68772 KB Output is correct
2 Correct 16 ms 68856 KB Output is correct
3 Correct 15 ms 68864 KB Output is correct
4 Correct 16 ms 68868 KB Output is correct
5 Correct 16 ms 68800 KB Output is correct
6 Correct 15 ms 68712 KB Output is correct
7 Correct 16 ms 68700 KB Output is correct
8 Correct 14 ms 68952 KB Output is correct
9 Correct 15 ms 68700 KB Output is correct
10 Correct 16 ms 68696 KB Output is correct
11 Correct 15 ms 68696 KB Output is correct
12 Correct 14 ms 68700 KB Output is correct
13 Incorrect 15 ms 68816 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 68772 KB Output is correct
2 Correct 16 ms 68856 KB Output is correct
3 Correct 15 ms 68864 KB Output is correct
4 Correct 16 ms 68868 KB Output is correct
5 Correct 16 ms 68800 KB Output is correct
6 Correct 15 ms 68712 KB Output is correct
7 Correct 16 ms 68700 KB Output is correct
8 Correct 14 ms 68952 KB Output is correct
9 Correct 15 ms 68700 KB Output is correct
10 Correct 16 ms 68696 KB Output is correct
11 Correct 15 ms 68696 KB Output is correct
12 Correct 14 ms 68700 KB Output is correct
13 Incorrect 15 ms 68816 KB Output isn't correct
14 Halted 0 ms 0 KB -