oj.uz

Submission #746943

# Submission time Handle Problem Language Result Execution time Memory
746943 2023-05-23T09:09:36 Z Prieved1 Fireworks (APIO16_fireworks) C++17
0 / 100
 18 ms 30832 KB 
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

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()) {
            lr.push(0);
            lr.push(k);
            rr.push(k);
        }else {
            int c=rr.top();
            rr.pop();
            rr.move(k);
            rr.push(c);
            rr.move(k);
            c=lr.top();
            lr.pop();
            lr.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.lr.top()) {
            b.lr.push(i);
        }
        else {
            b.rr.push(i);
            //b.val+=i-b.lr.top();
            b.lr.push(b.rr.top());
            b.rr.pop();
            b.val+=i-b.lr.top();
        }
    }
    while(a.rr.size()) {
        int i=a.rr.top();
        a.rr.pop();
        if(i>=b.rr.top()) {
            b.rr.push(i);
        }
        else {
            b.lr.push(i);
            b.rr.push(b.lr.top());
            b.lr.pop();
            b.val+=b.rr.top()-i;
        }
    }
}
const int N=300010;
vector<pair<int,int>> g[N];
node res[N];
void dfs(int at) {
    // res[at].add(0);
    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]);
    }
}
int 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 30744 KB Output is correct
2 Correct 17 ms 30784 KB Output is correct
3 Incorrect 16 ms 30732 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 30820 KB Output is correct
2 Correct 16 ms 30824 KB Output is correct
3 Correct 16 ms 30832 KB Output is correct
4 Correct 16 ms 30816 KB Output is correct
5 Correct 18 ms 30772 KB Output is correct
6 Incorrect 16 ms 30804 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 30744 KB Output is correct
2 Correct 17 ms 30784 KB Output is correct
3 Incorrect 16 ms 30732 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 30744 KB Output is correct
2 Correct 17 ms 30784 KB Output is correct
3 Incorrect 16 ms 30732 KB Output isn't correct
4 Halted 0 ms 0 KB -