oj.uz

Submission #160323

# Submission time Handle Problem Language Result Execution time Memory
160323 2019-10-27T02:21:19 Z model_code Climbers (RMI18_climbers) C
100 / 100
 229 ms 59256 KB 
/**
 * Method: treat pairs of altitudes as vertices in a graph, then run
 * Dijkstra's algorithm.
 *
 * Author: Catalin Francu
 *
 * Implementation details: we insert vertices into the heap lazily when they
 * are first reached. This reduces the heap size dramatically and speeds up
 * the program by a factor of 2 or 3.
 *
 * In order to run decreaseKey() when reaching a vertex that's already in the
 * heap, we store the heap index of each vertex in hp[].
 **/
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 5000

/* heap positions */
#define NEW 0       /* node not yet inserted */
#define REMOVED -1  /* node was processed and removed */

typedef unsigned long long u64;

typedef struct {
  short x, y;
  u64 dist;
} node;

int n;
int heapSize;
int alt[MAX_N + 1];
int hp[MAX_N][MAX_N];
node h[MAX_N * MAX_N + 1]; /* heap is 1-based */

/* returns true if the altitudes at i, j and k are in ascending or descending order */
int sequence(int i, int j, int k) {
  return
    (alt[i] <= alt[j] && alt[j] <= alt[k]) ||
    (alt[i] >= alt[j] && alt[j] >= alt[k]);
}

void heapMove(int from, int to) {
  hp[h[from].x][h[from].y] = to;
  h[to] = h[from];
}

void heapSiftUp(int pos) {
  node n = h[pos];

  while ((pos > 1) && (n.dist < h[pos / 2].dist)) {
    heapMove(pos / 2, pos);
    pos /= 2;
  }

  hp[n.x][n.y] = pos;
  h[pos] = n;
}

void heapSiftDown() {
  int pos = 1;
  node n = h[pos];
  int done = 0;

  while (!done) {
    int child = pos;
    if ((2 * pos <= heapSize) && (h[2 * pos].dist < h[child].dist)) {
      child = 2 * pos;
    }
    if ((2 * pos  + 1 <= heapSize) && (h[2 * pos + 1].dist < h[child].dist)) {
      child = 2 * pos + 1;
    }
    if (child != pos) {
      heapMove(child, pos);
      h[child] = n;
      pos = child;
    } else {
      done = 1;
    }
  }

  hp[n.x][n.y] = pos;
}

void heapRemoveMin(int* x, int* y, u64* dist) {
  *x = h[1].x;
  *y = h[1].y;
  *dist = h[1].dist;

  heapMove(heapSize--, 1);
  heapSiftDown();
  hp[*x][*y] = REMOVED;
}

void decreaseKey(int x, int y, u64 dist) {
  if (x < 0 || x >= n || y < 0 || y >= n) {
    return; /* range checking */
  }

  int pos = hp[x][y];

  switch (pos) {
    case REMOVED:
      /* nothing -- node was already processed */
      break;

    case NEW:
      /* add the node to the heap */
      hp[x][y] = ++heapSize;
      h[heapSize] = (node) { x, y, dist };
      heapSiftUp(heapSize);
      break;

    default:
      if (dist < h[pos].dist) {
        /* existing node and smaller distance */
        h[pos].dist = dist;
        heapSiftUp(pos);
      }
  }
}

u64 dijkstra() {
  int x = 0, y = n - 1;
  u64 d = 0;

  while (x != y) {
    /* loop invariant: alt[y], alt[x] and alt[y + 1] are sorted */

    /* corner cases */
    if (alt[x] == alt[y]) {
      decreaseKey(x, y - 1, d);
      decreaseKey(y, x, d);
      decreaseKey(y, x - 1, d);
    }
    if (alt[x] == alt[y + 1]) {
      decreaseKey(x, y, d);
      decreaseKey(y + 1, x, d);
      decreaseKey(y + 1, x - 1, d);
    }

    /* go towards x + 1 */
    if (x + 1 < n) {
      if (sequence(y, x + 1, y + 1)) {
        decreaseKey(x + 1, y, d + abs(alt[x] - alt[x + 1]));
      } else if (sequence(x + 1, y, x)) {
        decreaseKey(y, x, d + abs(alt[x] - alt[y]));
      } else {
        decreaseKey(y + 1, x, d + abs(alt[x] - alt[y + 1]));
      }
    }

    /* go towards x - 1 */
    if (x > 0) {
      if (sequence(y, x - 1, y + 1)) {
        decreaseKey(x - 1, y, d + abs(alt[x] - alt[x - 1]));
      } else if (sequence(x - 1, y, x)) {
        decreaseKey(y, x - 1, d + abs(alt[x] - alt[y]));
      } else {
        decreaseKey(y + 1, x - 1, d + abs(alt[x] - alt[y + 1]));
      }
    }

    heapRemoveMin(&x, &y, &d);
  }

  return d;
}

int main() {
  int numAlts;

  /* read altitudes, suppressing repeated values and monotonic runs */
  scanf("%d%d%d", &numAlts, &alt[0], &alt[1]);
  n = 2;
  while (numAlts-- > 2) {
    scanf("%d", &alt[n]);
    if (sequence(n - 2, n - 1, n)) {
      alt[n - 1] = alt[n];
    } else {
      n++;
    }
  }

  u64 answer = dijkstra();

  printf("%llu\n", answer);
}

Compilation message

climbers.c: In function 'main':
climbers.c:174:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &numAlts, &alt[0], &alt[1]);
   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
climbers.c:177:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &alt[n]);
     ^~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 3 ms 1656 KB Output is correct
3 Correct 9 ms 5240 KB Output is correct
4 Correct 33 ms 21880 KB Output is correct
5 Correct 95 ms 59256 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 864 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 4 ms 2040 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 4 ms 1528 KB Output is correct
3 Correct 86 ms 5980 KB Output is correct
4 Correct 142 ms 18296 KB Output is correct
5 Correct 193 ms 20600 KB Output is correct
6 Correct 205 ms 30160 KB Output is correct
7 Correct 203 ms 25080 KB Output is correct
8 Correct 192 ms 51704 KB Output is correct
9 Correct 225 ms 42168 KB Output is correct
10 Correct 229 ms 41848 KB Output is correct