Submission #1180263

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <queue>

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, w;
  ll c;
  Node(int i, int w, ll c) : i(i), w(w), c(c) {
    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) {
  return meld(root, new Node(*x));
}

Node *pop(Node *root) {
  Node *p = root;
  root = meld(root->r, root->l);
  delete p;
  return root;
}

#ifdef DEBUG
void dump(Node *x) {
  if (!x) return;
  printf ("  Node[%d] : w = %d, c = %lld\n", x->i, x->w, x->c);
  dump(x->l);
  dump(x->r);
}
#endif

//------------------------------------------------------------------------------
const int N_MAX = 100000;

struct qe {
  int w, i, 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];

int merge_weight(Node *a, Node *b) {
  return a->w + b->w;
}

ll merge_cost(Node *a, Node *b) {
  return a->c + b->c + a->w + b->w;
}

Node *merge_node(Node *a, Node *b) {
  return new Node(a->i, merge_weight(a, b), merge_cost(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, w[i], 0);
  // 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
    while (true) {
      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) break;
    }
    // merge destination
    int k = left_end(a->c ? i : left[i]);

#ifdef DEBUG
    printf("i: %d, j: %d, k: %d\n", i, j, k);
#endif

    // merge nodes
    nodes[i] = merge_node(a, b); nodes[j] = 0;
    delete a; delete b;

    // merge heaps
    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);
    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

Compile Error

./Main.cpp: In function ‘void input()’:
./Main.cpp:170:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:171: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