Submission #1124292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124292		nikd	Fireworks (APIO16_fireworks)	C++20	0 / 100	1 ms	320 KiB

fireworks

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef __gnu_pbds::priority_queue<ll> pq;

long long aggiusta(int N, int M, vector<int> P, vector<int> L){
    ll n = N; ll m = M;
    vector<ll> l(n+m);
    for(int i = 0; i<n+m; i++) l[i] = L[i];
    l[0]=0;
    vector<vector<int>> adj(N+M);
    for(int i= 1; i<N+M; i++){
        adj[P[i]].push_back(i);
        adj[i].push_back(P[i]);
    }
    adj[0].push_back(-1);
    auto dfs = [&](int v, int p, auto&& dfs) -> pq{
        pq q;
        if(v>=N){
            q.push(l[v]);
            q.push(l[v]);
            return q;
        }
        for(int u: adj[v]){
            if(u==p) continue;
            pq q2 = dfs(u, v, dfs);
            q.join(q2);
        }
        for(int i= 0; i<adj[v].size()-2; i++){
            q.pop();
        }
        ll x1 = q.top(); q.pop();
        ll x0 = q.top(); q.pop();
        q.push(x1+l[v]);
        q.push(x0+l[v]);
        return q;
    };
    pq q;
    q = dfs(0, -1, dfs);
    vector<ll> slp;
    while(!q.empty()){
        slp.push_back(q.top()); 
        q.pop();
    }
    //reverse(slp.begin(), slp.end());
    ll dp0 = 0;
    for(int i = 1; i<n+m; i++) dp0+=l[i];
    ll slope = 1-slp.size();
    ll lst = 0;
    for(int i = slope; i<0; i++){
        dp0 += i*(slp[-i]-lst);
        lst = slp[-i];
    }
    return dp0;
}


int main(){
    int n, m; cin >> n >> m;
    vector<int> p(n+m);
    vector<int> f(n+m);
    for(int i= 0; i<n+m; i++){
        cin >> p[i] >> f[i]; 
        p[i]--;
    }
    cout << aggiusta(n, m, p, f) << '\n';
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45