Submission #1572943
Source Code Expand
#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <stack>
#include <queue>
#include <tuple>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define _rep(_1, _2, _3, _4, name, ...) name
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))
#define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)
using namespace std;
using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f80 = long double;
i64 get_i64() {
int c; i64 n;
while ((c = getchar()) < '0');
n = c - '0';
while ((c = getchar()) >= '0') n = n * 10 + (c - '0');
return n;
}
template <typename T>
class PHeap {
/*
- Running Times: N = 10 ** 7
- Ascend: 0.709 seconds
- Descend: 0.249 seconds
- Random: 15.6 seconds
*/
private:
static constexpr T Inf = (T(1) << (sizeof(T) * 8 - 2)) - 1;
struct Node {
Node() {}
Node(T v) : elem(v), sibling(nullptr), next(nullptr) {}
T elem; Node *sibling, *next;
static Node* merge(Node* l, Node* r) {
if (!l) return r;
if (!r) return l;
if (l->elem > r->elem) swap(l, r);
r->next = l->sibling;
l->sibling = r;
return l;
};
static Node* merge_list(Node* root) {
if (!root->sibling) return nullptr;
Node *a = root->sibling; root = nullptr;
while (a) {
Node *b = a->next, *na = nullptr;
a->next = nullptr;
if (b) na = b->next, b->next = nullptr;
a = merge(a, b);
a->next = root, root = a, a = na;
}
Node* s = root->next; root->next = nullptr;
while (s) {
Node* u = s->next; s->next = nullptr;
root = merge(root, s);
s = u;
}
return root;
}
};
public:
class Allocator { // ...
public:
Allocator(int N) : N(N), nodes(N), unused(N) { clear_all(); }
void clear_all() {
for (int i = 0; i < N; ++i) unused[i] = i;
unused_pos = 0;
}
Node* new_node(T v) { return &(nodes[ unused[unused_pos++] ] = Node(v)); }
void pop(Node* p) { unused[--unused_pos] = p - nodes.data(); }
private:
int N;
vector<Node> nodes;
vector<int> unused; int unused_pos;
};
public:
PHeap() : root(nullptr) {}
const T top() const { return root->elem; }
const T second() {
return (root->sibling = Node::merge_list(root)) ? root->sibling->elem : Inf;
}
bool empty() const { return !root; }
void push(T v, Allocator& al) { root = Node::merge(root, al.new_node(v)); }
void meld(PHeap& rhs) { root = Node::merge(root, rhs.root); }
void pop(Allocator& al) { al.pop(root); root = Node::merge_list(root); }
private:
Node* root;
};
template <typename T>
i64 optimal_alphabetic_tree(const vector<i64>& vs) {
/*
- Random:
- 10 ** 6: 1.387 seconds
- 10 ** 7: 21.61 seconds
*/
static constexpr T Inf = (T(1) << (sizeof(T) * 8 - 2)) - 1;
const int N = vs.size();
if (N <= 1) return 0;
vector<T> A(N + 2);
A[0] = A[N + 1] = Inf;
for (int i = 1; i <= N; ++i) A[i] = vs[i - 1];
using Heap = PHeap<T>;
vector<Heap> heaps(N + 1);
auto alloc = typename Heap::Allocator(N - 1);
auto pop = [&] (int k) { heaps[k].pop(alloc); };
auto push = [&] (int k, T v) { heaps[k].push(v, alloc); };
vector<int> L(N + 2), R(N + 1);
vector<T> best(N + 1);
using P = pair<i64, int>;
priority_queue< P, vector<P>, greater<P> > que;
for (int i = 0; i < N + 1; ++i) {
L[i] = i - 1, R[i] = i + 1;
best[i] = A[i] + A[i + 1];
que.emplace(best[i], i);
}
auto merge = [&] (int l, int r) {
heaps[l].meld(heaps[r]);
R[l] = R[r], L[R[r]] = l, best[r] = 2 * Inf + 1;
return l;
};
i64 ret = 0;
for (int remaining = N - 1; remaining; --remaining) {
T w; int k;
do { tie(w, k) = que.top(); que.pop(); } while (best[k] != w);
ret += w;
int f = 0;
if (A[k] + A[R[k]] == w) f |= 3;
else if (heaps[k].top() + A[R[k]] == w) f |= 2, pop(k);
else if (A[k] + heaps[k].top() == w) f |= 1, pop(k);
else pop(k), pop(k);
push(k, w);
if (f & 1) k = merge(L[k], k);
if (f & 2) k = merge(k, R[k]);
i64 new_w = A[k] + A[R[k]];
new_w = min(new_w, min(A[k], A[R[k]]) + heaps[k].top());
new_w = min(new_w, heaps[k].top() + heaps[k].second());
que.emplace(best[k] = new_w, k);
}
return ret;
}
void solve() {
int N;
while (~scanf("%d", &N)) {
vector<i64> A(N); rep(i, N) A[i] = get_i64();
printf("%llu\n", optimal_alphabetic_tree<i64>(A));
}
}
int main() {
clock_t beg = clock();
solve();
clock_t end = clock();
fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);
return 0;
}
Submission Info
Submission Time |
|
Task |
J - 刺身 |
User |
Min_25 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
5058 Byte |
Status |
AC |
Exec Time |
2 ms |
Memory |
640 KB |
Judge Result
Set Name |
Partial 1 |
All |
Score / Max Score |
3 / 3 |
97 / 97 |
Status |
|
|
Set Name |
Test Cases |
Partial 1 |
00_Teuchi_00, 00_Teuchi_01, 00_alternate_0, 00_alternate_1, 00_alternate_2, 00_alternate_3, 00_alternate_4, 00_alternate_5, 00_random_0, 00_random_1, 00_random_2, 00_random_3, 00_random_4, 00_random_5, 00_random_6, 00_random_7, 00_random_8, 00_sample_00, 00_sample_01, 00_sample_02, 00_sorted_0, 00_sorted_1, 00_sorted_2 |
All |
00_Teuchi_00, 00_Teuchi_01, 00_alternate_0, 00_alternate_1, 00_alternate_2, 00_alternate_3, 00_alternate_4, 00_alternate_5, 00_random_0, 00_random_1, 00_random_2, 00_random_3, 00_random_4, 00_random_5, 00_random_6, 00_random_7, 00_random_8, 00_sample_00, 00_sample_01, 00_sample_02, 00_sorted_0, 00_sorted_1, 00_sorted_2, 20_random_11, 20_random_12, 40_alternate_6, 40_alternate_7, 40_alternate_8, 40_alternate_9, 40_random_10, 40_random_13, 40_random_14, 40_random_15, 40_random_16, 40_random_17, 40_random_18, 40_random_19, 40_random_9, 40_sorted_3, 40_sorted_4, 40_sorted_5, 99_Teuchi_00, 99_Teuchi_01, 99_Teuchi_02 |
Case Name |
Status |
Exec Time |
Memory |
00_Teuchi_00 |
AC |
1 ms |
256 KB |
00_Teuchi_01 |
AC |
1 ms |
256 KB |
00_alternate_0 |
AC |
1 ms |
256 KB |
00_alternate_1 |
AC |
1 ms |
256 KB |
00_alternate_2 |
AC |
1 ms |
256 KB |
00_alternate_3 |
AC |
1 ms |
256 KB |
00_alternate_4 |
AC |
1 ms |
256 KB |
00_alternate_5 |
AC |
1 ms |
256 KB |
00_random_0 |
AC |
1 ms |
256 KB |
00_random_1 |
AC |
1 ms |
256 KB |
00_random_2 |
AC |
1 ms |
256 KB |
00_random_3 |
AC |
1 ms |
256 KB |
00_random_4 |
AC |
1 ms |
256 KB |
00_random_5 |
AC |
1 ms |
256 KB |
00_random_6 |
AC |
1 ms |
256 KB |
00_random_7 |
AC |
1 ms |
256 KB |
00_random_8 |
AC |
1 ms |
256 KB |
00_sample_00 |
AC |
1 ms |
256 KB |
00_sample_01 |
AC |
1 ms |
256 KB |
00_sample_02 |
AC |
1 ms |
256 KB |
00_sorted_0 |
AC |
1 ms |
256 KB |
00_sorted_1 |
AC |
1 ms |
256 KB |
00_sorted_2 |
AC |
1 ms |
256 KB |
20_random_11 |
AC |
2 ms |
384 KB |
20_random_12 |
AC |
1 ms |
512 KB |
40_alternate_6 |
AC |
2 ms |
512 KB |
40_alternate_7 |
AC |
2 ms |
512 KB |
40_alternate_8 |
AC |
2 ms |
512 KB |
40_alternate_9 |
AC |
2 ms |
512 KB |
40_random_10 |
AC |
2 ms |
640 KB |
40_random_13 |
AC |
2 ms |
640 KB |
40_random_14 |
AC |
2 ms |
640 KB |
40_random_15 |
AC |
2 ms |
640 KB |
40_random_16 |
AC |
2 ms |
640 KB |
40_random_17 |
AC |
2 ms |
512 KB |
40_random_18 |
AC |
2 ms |
640 KB |
40_random_19 |
AC |
2 ms |
512 KB |
40_random_9 |
AC |
2 ms |
640 KB |
40_sorted_3 |
AC |
2 ms |
640 KB |
40_sorted_4 |
AC |
2 ms |
640 KB |
40_sorted_5 |
AC |
2 ms |
512 KB |
99_Teuchi_00 |
AC |
2 ms |
640 KB |
99_Teuchi_01 |
AC |
2 ms |
640 KB |
99_Teuchi_02 |
AC |
2 ms |
640 KB |