Submission #747002

#	Time	Username	Problem	Language	Result	Execution time	Memory
747002		Prieved1	Fireworks (APIO16_fireworks)	C++17	100 / 100	391 ms	92080 KiB

fireworks

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define int long long
int inf=4e18;
struct pq {
    priority_queue<int, vector<int>,
    greater<int>> q;
    int offside=0;
    void push(int val) {
        q.push(val-offside);
    }
    int top(){return q.top()+offside;}
    void pop(){q.pop();}
    void move(int k){offside+=k;}
    int size(){return q.size();}
};
struct node{
    priority_queue<int> lr;
    pq rr;
    int val=0;
    int sz(){return lr.size()+rr.size();}
    void add(int k) {
        if(!lr.size() and !rr.size()) {
            lr.push(k);
            rr.push(k);
        }else {
            int c=lr.top();
            lr.pop();
            lr.push(c+k);
            c=rr.top();
            rr=pq();
            rr.push(c+k);
        }
    }
};
void merge(node &a, node& b) {
    b.val+=a.val;
    while(a.lr.size()) {
        int i=a.lr.top();
        a.lr.pop();
        if(i<=b.rr.top()) {
            b.lr.push(i);
        }
        else {
            b.rr.push(i);
            b.val+=i-b.rr.top();
            b.lr.push(b.rr.top());
            b.rr.pop();
        }
    }
    while(a.rr.size()) {
        int i=a.rr.top();
        a.rr.pop();
        if(i>=b.lr.top()) {
            b.rr.push(i);
        }
        else {
            b.lr.push(i);
            b.val+=b.lr.top()-i;
            b.rr.push(b.lr.top());
            b.lr.pop();
        }
    }
}
const int N=300010;
vector<pair<int,int>> g[N];
node res[N];
void dfs(int at) {
    for(auto to:g[at]) {
        dfs(to.first);
        res[to.first].add(to.second);
        if(res[at].sz()<res[to.first].sz()) 
        {
          swap(res[at],res[to.first]);
        }
        merge(res[to.first], res[at]);
    }
}
int32_t main()
{
    int n, m;
    cin >> n >> m;
    for(int i =2;i<=n+m;i++) {
        int p, c;
        cin >> p >> c;
        g[p].push_back({i,c});
    }
    dfs(1);
    cout << res[1].val << endl;
    return 0;
}

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