sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#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; }