Submission #1180201
Source Code Expand
#include <cstdio> #include <algorithm> #include <queue> #include <functional> using namespace std; // #define DEBUG 1 #define REP(i,n) for(int i=0; i<(int)(n); i++) #define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++) #define DUMP(a, n) REP(i, n) printf("%d%c", a[i], i + 1 == n ? '\n' : ' ') //------------------------------------------------------------------------------ typedef long long ll; struct Node { Node *l, *r; int i; ll c; int w; Node(int i, ll c, int w) : i(i), c(c), w(w) { l = r = (Node *)0; } }; Node *meld(Node *a, Node *b) { if (!a) return b; if (!b) return a; if (a->w > b->w) swap(a, b); a->r = meld(a->r, b); swap(a->l, a->r); return a; } Node *push(Node *root, Node *x) { if (!x) return root; return meld(root, new Node(*x)); } Node *pop(Node *root) { if (!root) return 0; Node *p = root; root = meld(root->r, root->l); delete p; return root; } void dump(Node *x) { if (!x) return; printf (" Node[%d] : c = %lld, w = %d\n", x->i, x->c, x->w); dump(x->l); dump(x->r); } //------------------------------------------------------------------------------ const int N_MAX = 100000; struct qe { int w; int i; int j; bool operator < (const qe &e) const { return w > e.w; } }; int n; int w[N_MAX]; Node *nodes[N_MAX]; Node *heaps[N_MAX]; int left[N_MAX]; ll merge_cost(Node *a, Node *b) { return a->c + b->c + a->w + b->w; } int merge_weight(Node *a, Node *b) { return a->w + b->w; } Node *merge_node(Node *a, Node *b) { return new Node(a->i, merge_cost(a, b), merge_weight(a, b)); } int fetch(int k) { while (true) { if (!heaps[k]) return -1; Node *a = heaps[k]; int i = a->i; Node *b = nodes[i]; bool check = (b && b->w == a->w); heaps[k] = pop(heaps[k]); if (check) return i; } } int left_end(int i) { if (heaps[i]) return i; return left[i] = left_end(left[i]); } void solve() { priority_queue<qe> pq; // make nodes REP(i, n) nodes[i] = new Node(i, 0, w[i]); // build heaps for each adjacent node pair REP(i, n - 1) { int j = i + 1; heaps[i] = push(heaps[i], nodes[i]); heaps[i] = push(heaps[i], nodes[j]); left[j] = i; pq.push((qe) { merge_weight(nodes[i], nodes[j]), i, j }); } REP(s, n - 1) { int i, j; Node *a, *b; // find lowest cost node pair bool found = false; while (!pq.empty()) { qe p = pq.top(); pq.pop(); i = p.i; j = p.j; a = nodes[i]; b = nodes[j]; if (a && b && merge_weight(a, b) == p.w) { found = true; break; } } if (!found) break; #ifdef DEBUG printf("i: %d, j: %d\n", i, j); #endif // merge nodes nodes[i] = merge_node(a, b); nodes[j] = 0; delete a; delete b; // merge heaps int k = left_end(a->c ? i : left[i]); if (heaps[i] && k != i) { // i is leaf and left heap of i exists heaps[k] = meld(heaps[k], heaps[i]); heaps[i] = 0; left[i] = k; } if (heaps[j] && k != j) { // j is leaf and right heap of j exists heaps[k] = meld(heaps[k], heaps[j]); heaps[j] = 0; left[j] = k; } // add merged node heaps[k] = push(heaps[k], nodes[i]); // choose new heap's top 2 lowest cost nodes i = fetch(k); if (i < 0) break; do { j = fetch(k); } while (j == i); if (j < 0) break; if (i > j) swap(i, j); a = nodes[i]; b = nodes[j]; pq.push((qe) { merge_weight(a, b), i, j }); heaps[k] = push(heaps[k], a); heaps[k] = push(heaps[k], b); #ifdef DEBUG puts("Nodes:"); REP(r, n) dump(nodes[r]); REP(r, n) if (heaps[r]) { printf("heap[%d]:\n", r); dump(heaps[r]); } #endif } // output final node's cost printf("%lld\n", nodes[0]->c); } void input() { scanf("%d", &n); REP(i, n) scanf("%d", w + i); } int main() { input(); solve(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 最適二分探索木 |
User | nejiko96 |
Language | C++14 (GCC 5.4.1) |
Score | 101 |
Code Size | 3869 Byte |
Status | AC |
Exec Time | 134 ms |
Memory | 17972 KB |
Compile Error
./Main.cpp: In function ‘void input()’: ./Main.cpp:181:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &n); ^ ./Main.cpp:182:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] REP(i, n) scanf("%d", w + i); ^
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 50 / 50 | 1 / 1 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_01.txt |
Dataset1 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt |
Dataset2 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 02_00.txt, 02_01.txt, 02_02.txt, 02_03.txt, 02_04.txt, 02_05.txt, 02_06.txt, 02_07.txt, 02_08.txt, 02_09.txt, 02_10.txt, 02_11.txt, 02_12.txt, 02_13.txt, 02_14.txt, 02_15.txt, 02_16.txt, 02_17.txt, 02_18.txt, 02_19.txt, 02_20.txt, 02_21.txt, 02_22.txt, 02_23.txt, 02_24.txt, 02_25.txt, 02_26.txt, 02_27.txt, 02_28.txt, 02_29.txt |
Dataset3 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 02_00.txt, 02_01.txt, 02_02.txt, 02_03.txt, 02_04.txt, 02_05.txt, 02_06.txt, 02_07.txt, 02_08.txt, 02_09.txt, 02_10.txt, 02_11.txt, 02_12.txt, 02_13.txt, 02_14.txt, 02_15.txt, 02_16.txt, 02_17.txt, 02_18.txt, 02_19.txt, 02_20.txt, 02_21.txt, 02_22.txt, 02_23.txt, 02_24.txt, 02_25.txt, 02_26.txt, 02_27.txt, 02_28.txt, 02_29.txt, 03_00.txt, 03_01.txt, 03_02.txt, 03_03.txt, 03_04.txt, 03_05.txt, 03_06.txt, 03_07.txt, 03_08.txt, 03_09.txt, 03_10.txt, 03_11.txt, 03_12.txt, 03_13.txt, 03_14.txt, 03_15.txt, 03_16.txt, 03_17.txt, 03_18.txt, 03_19.txt, 03_20.txt, 03_21.txt, 03_22.txt, 03_23.txt, 03_24.txt, 03_25.txt, 03_26.txt, 03_27.txt, 03_28.txt, 03_29.txt, 03_30.txt, 03_31.txt, 03_32.txt, 03_33.txt, 03_34.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01.txt | AC | 1 ms | 256 KB |
01_00.txt | AC | 1 ms | 256 KB |
01_01.txt | AC | 1 ms | 256 KB |
01_02.txt | AC | 1 ms | 256 KB |
01_03.txt | AC | 1 ms | 256 KB |
01_04.txt | AC | 1 ms | 256 KB |
01_05.txt | AC | 1 ms | 256 KB |
01_06.txt | AC | 1 ms | 256 KB |
01_07.txt | AC | 1 ms | 256 KB |
01_08.txt | AC | 1 ms | 256 KB |
01_09.txt | AC | 1 ms | 256 KB |
01_10.txt | AC | 1 ms | 256 KB |
01_11.txt | AC | 1 ms | 256 KB |
01_12.txt | AC | 1 ms | 256 KB |
01_13.txt | AC | 1 ms | 256 KB |
01_14.txt | AC | 1 ms | 256 KB |
01_15.txt | AC | 1 ms | 256 KB |
01_16.txt | AC | 1 ms | 256 KB |
01_17.txt | AC | 1 ms | 256 KB |
01_18.txt | AC | 1 ms | 256 KB |
01_19.txt | AC | 1 ms | 256 KB |
01_20.txt | AC | 1 ms | 256 KB |
01_21.txt | AC | 1 ms | 256 KB |
01_22.txt | AC | 1 ms | 256 KB |
01_23.txt | AC | 1 ms | 256 KB |
01_24.txt | AC | 1 ms | 256 KB |
01_25.txt | AC | 1 ms | 256 KB |
01_26.txt | AC | 1 ms | 256 KB |
01_27.txt | AC | 1 ms | 256 KB |
01_28.txt | AC | 1 ms | 256 KB |
01_29.txt | AC | 1 ms | 256 KB |
02_00.txt | AC | 3 ms | 768 KB |
02_01.txt | AC | 3 ms | 768 KB |
02_02.txt | AC | 3 ms | 768 KB |
02_03.txt | AC | 3 ms | 768 KB |
02_04.txt | AC | 3 ms | 768 KB |
02_05.txt | AC | 3 ms | 768 KB |
02_06.txt | AC | 3 ms | 768 KB |
02_07.txt | AC | 3 ms | 768 KB |
02_08.txt | AC | 3 ms | 768 KB |
02_09.txt | AC | 3 ms | 768 KB |
02_10.txt | AC | 3 ms | 768 KB |
02_11.txt | AC | 3 ms | 768 KB |
02_12.txt | AC | 3 ms | 768 KB |
02_13.txt | AC | 3 ms | 768 KB |
02_14.txt | AC | 3 ms | 768 KB |
02_15.txt | AC | 3 ms | 768 KB |
02_16.txt | AC | 3 ms | 768 KB |
02_17.txt | AC | 3 ms | 768 KB |
02_18.txt | AC | 3 ms | 768 KB |
02_19.txt | AC | 3 ms | 768 KB |
02_20.txt | AC | 3 ms | 768 KB |
02_21.txt | AC | 3 ms | 768 KB |
02_22.txt | AC | 4 ms | 768 KB |
02_23.txt | AC | 3 ms | 768 KB |
02_24.txt | AC | 3 ms | 768 KB |
02_25.txt | AC | 3 ms | 768 KB |
02_26.txt | AC | 3 ms | 768 KB |
02_27.txt | AC | 3 ms | 768 KB |
02_28.txt | AC | 3 ms | 768 KB |
02_29.txt | AC | 3 ms | 768 KB |
03_00.txt | AC | 123 ms | 17844 KB |
03_01.txt | AC | 118 ms | 17844 KB |
03_02.txt | AC | 121 ms | 17844 KB |
03_03.txt | AC | 118 ms | 17844 KB |
03_04.txt | AC | 115 ms | 17844 KB |
03_05.txt | AC | 106 ms | 17844 KB |
03_06.txt | AC | 114 ms | 17844 KB |
03_07.txt | AC | 116 ms | 17844 KB |
03_08.txt | AC | 113 ms | 17844 KB |
03_09.txt | AC | 110 ms | 17844 KB |
03_10.txt | AC | 106 ms | 17844 KB |
03_11.txt | AC | 118 ms | 17844 KB |
03_12.txt | AC | 117 ms | 17844 KB |
03_13.txt | AC | 116 ms | 17844 KB |
03_14.txt | AC | 116 ms | 17844 KB |
03_15.txt | AC | 109 ms | 17844 KB |
03_16.txt | AC | 110 ms | 17844 KB |
03_17.txt | AC | 124 ms | 17972 KB |
03_18.txt | AC | 113 ms | 17844 KB |
03_19.txt | AC | 115 ms | 17844 KB |
03_20.txt | AC | 117 ms | 17844 KB |
03_21.txt | AC | 112 ms | 17844 KB |
03_22.txt | AC | 112 ms | 17844 KB |
03_23.txt | AC | 134 ms | 17844 KB |
03_24.txt | AC | 118 ms | 17844 KB |
03_25.txt | AC | 117 ms | 17844 KB |
03_26.txt | AC | 117 ms | 17844 KB |
03_27.txt | AC | 114 ms | 17844 KB |
03_28.txt | AC | 112 ms | 17844 KB |
03_29.txt | AC | 128 ms | 17844 KB |
03_30.txt | AC | 118 ms | 17844 KB |
03_31.txt | AC | 114 ms | 17844 KB |
03_32.txt | AC | 115 ms | 17844 KB |
03_33.txt | AC | 113 ms | 17844 KB |
03_34.txt | AC | 112 ms | 17844 KB |