test/aoj/2415.test.cpp

View this file on GitHub
Last update: 2024-01-08 01:52:54+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415"

#include <bits/stdc++.h>

#include "../../dp/hu_tucker.hpp"
using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;
    vector<ll> w(N);
    for (auto& x : w) cin >> x;
    cout << hu_tucker(w) << endl;
}

#line 1 "test/aoj/2415.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415"

#include <bits/stdc++.h>

#line 7 "dp/hu_tucker.hpp"

#line 5 "data-structure/leftist_heap.hpp"

template <typename T>
class LeftistHeap {
   public:
    LeftistHeap() = default;

    static LeftistHeap meld(LeftistHeap a, LeftistHeap b) {
        return LeftistHeap(meld(std::move(a.root), std::move(b.root)));
    }

    std::pair<int, T> top() const {
        push(root);
        return {root->id, root->val};
    }

    void pop() {
        push(root);
        root = meld(std::move(root->left), std::move(root->right));
    }

    void push(int id, T x) {
        root = meld(std::move(root), std::make_unique<Node>(id, x));
    }

    bool empty() const { return root == nullptr; }

    void add(T x) { root->lazy += x; }

   private:
    struct Node;
    using node_ptr = std::unique_ptr<Node>;

    struct Node {
        node_ptr left, right;
        int s;
        int id;
        T val, lazy;
        Node(int id, T x) : id(id), val(x), lazy(0) {}
    };

    node_ptr root = nullptr;

    explicit LeftistHeap(node_ptr root) : root(std::move(root)) {}

    static node_ptr meld(node_ptr a, node_ptr b) {
        if (!a) return b;
        if (!b) return a;
        push(a);
        push(b);
        if (a->val > b->val) std::swap(a, b);
        a->right = meld(std::move(a->right), std::move(b));
        if (!a->left || a->left->s < a->right->s) std::swap(a->left, a->right);
        a->s = (a->right ? a->right->s : 0) + 1;
        return a;
    }

    static void push(const node_ptr& t) {
        if (t->left) t->left->lazy += t->lazy;
        if (t->right) t->right->lazy += t->lazy;
        t->val += t->lazy;
        t->lazy = 0;
    }
};
#line 9 "dp/hu_tucker.hpp"

template <typename T>
T hu_tucker(std::vector<T> w) {
    const int n = w.size();
    const T INF = std::numeric_limits<T>::max() / 2;
    std::vector<LeftistHeap<T>> heaps(n - 1);  // interior nodes in each group
    std::vector<int> left(n), right(n);
    std::vector<T> cs(n - 1);
    using P = std::pair<T, int>;
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
    for (int i = 0; i < n - 1; ++i) {
        left[i] = i - 1;
        right[i] = i + 1;
        cs[i] = w[i] + w[i + 1];
        pq.emplace(cs[i], i);
    }
    T ret = 0;
    for (int k = 0; k < n - 1; ++k) {
        T c;
        int i;
        // find the optimal nodes to merge
        do {
            std::tie(c, i) = pq.top();
            pq.pop();
        } while (right[i] == -1 || cs[i] != c);

        bool merge_l = false, merge_r = false;
        if (w[i] + w[right[i]] == c) {  // lr
            merge_l = merge_r = true;
        } else {
            T top = heaps[i].top().second;
            heaps[i].pop();
            if (w[i] + top == c) {  // lm
                merge_l = true;
            } else if (top + w[right[i]] == c) {  // mr
                merge_r = true;
            } else {  // mm
                heaps[i].pop();
            }
        }
        ret += c;
        heaps[i].push(-1, c);
        if (merge_l) {
            w[i] = INF;
        }
        if (merge_r) {
            w[right[i]] = INF;
        }

        // merge left
        if (merge_l && i > 0) {
            int j = left[i];
            heaps[j] =
                LeftistHeap<T>::meld(std::move(heaps[j]), std::move(heaps[i]));
            right[j] = right[i];
            right[i] = -1;
            left[right[j]] = j;
            i = j;
        }
        // merge right
        if (merge_r && right[i] < n - 1) {
            int j = right[i];
            heaps[i] =
                LeftistHeap<T>::meld(std::move(heaps[i]), std::move(heaps[j]));
            right[i] = right[j];
            right[j] = -1;
            left[right[i]] = i;
        }

        cs[i] = w[i] + w[right[i]];  // lr
        if (!heaps[i].empty()) {
            T top = heaps[i].top().second;
            heaps[i].pop();
            cs[i] =
                std::min(cs[i], std::min(w[i], w[right[i]]) + top);  // lm or mr
            if (!heaps[i].empty()) {
                cs[i] = std::min(cs[i], top + heaps[i].top().second);  // mm
            }
            heaps[i].push(-1, top);
        }
        pq.emplace(cs[i], i);
    }
    return ret;
}
#line 6 "test/aoj/2415.test.cpp"
using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;
    vector<ll> w(N);
    for (auto& x : w) cin >> x;
    cout << hu_tucker(w) << endl;
}