oj.uz

Submission #171989

# Submission time Handle Problem Language Result Execution time Memory
171989 2019-12-30T18:24:38 Z rama_pang Fireworks (APIO16_fireworks) C++14
0 / 100
 2 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;

struct Node {
    lint a, b; // y = ax + b, for big x where x >= pq.top()
    priority_queue<lint> pq; // point-slope container

    Node() : a(0), b(0), pq()  {}

    Node& operator+=(Node& o) {
        a += o.a;
        b += o.b;

        if (pq.size() < o.pq.size()) {
            swap(pq, o.pq);
        }

        while (!o.pq.empty()) { // weighted union heuristic
            pq.emplace(o.pq.top());
            o.pq.pop();
        }

        while (a > 1) {
            a--; // ax + b = a(x - 1) + (b + x)
            b += pq.top();
            pq.pop();
        }

        return *this;
    }

    lint solve() {
        while (a > 0) {
            a--;
            b += pq.top();
            pq.pop();
        }
        return b;
    }

};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> p(n + m, -1), c(n + m, 0);
    for (int i = 1; i < n + m; i++) {
        cin >> p[i] >> c[i];
        p[i]--;
    }

    vector<Node> tree(n + m);
    for (int i = n + m - 1; i >= n; i--) {
        tree[i].a = 1;
        tree[i].b = -c[i];
        tree[i].pq.emplace(c[i]); // between slope -1 and 0
        tree[i].pq.emplace(c[i]); // between slope 0 and 1
        tree[p[i]] += tree[i];
    }

    for (int i = n - 1; i > 0; i--) {
        lint top1 = tree[i].pq.top();
        tree[i].pq.pop();
        lint top2 = tree[i].pq.top();
        tree[i].pq.pop();

        tree[i].pq.emplace(top1 + c[i]); // shift slope 1 by c[i]
        tree[i].pq.emplace(top2 + c[i]); // shift slope 0 by c[i]

        tree[i].b -= c[i]; // shift line to right by c[i]
        tree[p[i]] += tree[i];
    }

    cout << tree[0].solve() << "\n";
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -