Submission #1194224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194224		sabino1	Fireworks (APIO16_fireworks)	C++20	100 / 100	150 ms	74308 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;

using ll = long long int;

const int MAX = (int) 3e5 + 10;

struct SlopeTrick{
    struct Function{
        ll a = 0,b = 0;
        void operator +=(Function & ot){
            a += ot.a;
            b += ot.b;
        }
    };
    priority_queue<ll> pts; // slope change
    Function f; // last linear function

    void arruma(int z){
        if(pts.empty()){
            f.a = 1;
            f.b = -z;
            pts.push(z);
            pts.push(z);
            return;
        }
        // os caras da inclinacao zero eu vou shiftar +z, dai os caras da esquerda eu vou shiftar +z e depois shiftar -z, ou seja, n vou fazer nada
        ll lst=0;
        while(f.a != 0){
            ll x = pts.top();
            pts.pop();
            ll y = f.a*x + f.b;
            f.a--;
            f.b = y - f.a*x;
            lst = x;
        }
        
        ll lst2 = pts.top();
        pts.pop();
        pts.push(lst2 + z); 
        pts.push(lst + z);

        // considerar a nova inclinacao 1
        f.a++;
        f.b = f.b - f.a*(lst+z);
    }

    ll solve(){
        while(f.a != 0){
            ll x = pts.top();
            pts.pop();
            ll y = f.a*x + f.b;
            f.a--;
            f.b = y - f.a*x;
        }
        return f.b;
    }

    void show(){
        priority_queue<ll> pq = pts;
        Function g = f;
        while(!pq.empty()){
            ll x = pq.top();
            pq.pop();
            cout << x << ' ' << g.a << ' ' << g.b << endl;
            ll y = g.a*x + g.b;
            g.a--;
            g.b = y - g.a*x;
        }
        cout << "-inf " << g.a << ' ' << g.b << endl;
    }
};

vector<pair<int,int>> graph[MAX];
int rep[MAX];
SlopeTrick slp[MAX];

int get(int u){return rep[u] = rep[u] == u ? u : get(rep[u]);}
void merge(int u,int v){
    u = get(u), v = get(v);
    if(u  == v) return;
    if(slp[u].pts.size() < slp[v].pts.size()){
        merge(v,u);
        return;
    }
    auto & at = slp[u];
    auto & ot = slp[v];
    while(!ot.pts.empty()){
        ll x = ot.pts.top();
        ot.pts.pop();
        at.pts.push(x);
    }
    at.f += ot.f;
    rep[v] = u;
}

void solve(int u,int ant){
    for(auto [v,z] : graph[u]){
        if(v == ant) continue;
        solve(v,u);
        slp[get(v)].arruma(z);
        merge(u,v);
    }
    // cout << u << ":\n";
    // slp[get(u)].show();
}

void test(){
    int n,m;
    cin >> n >> m;
    for(int i=1; i<=n+m; i++) rep[i] = i;
    for(int i=2; i<=n+m; i++){
        int x,z;
        cin >> x >> z;
        graph[x].push_back(make_pair(i,z));
        graph[i].push_back(make_pair(x,z));
    }
    solve(1,1);
    cout << slp[get(1)].solve() << '\n';
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int ttt_ = 1;
    // cin >> ttt_;
    while(ttt_--) test();
    return 0;
}

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