oj.uz

Submission #20610

# Submission time Handle Problem Language Result Execution time Memory
20610 2017-02-12T16:18:10 Z model_code Roller Coaster Railroad (IOI16_railroad) C
34 / 100
 79 ms 41268 KB 
// name = railroad_c.c, type = c.gcc

#include "railroad_c.h"
#include <stdlib.h>
#define max(x, y) ((x) > (y) ? (x) : (y))

const int INF = (int) 1e9;

#define N 1234567

typedef struct {
  int a;
  int b;
  int c;
} st;

int p[N], id[N];
st e[N], ee[N];

int dsu_get(int u) {
  return (u == p[u]) ? u : (p[u] = dsu_get(p[u]));
}

int dsu_union(int u, int v) {
  u = dsu_get(u);
  v = dsu_get(v);
  p[u] = v;
  return (u != v);
}

int comp(void const *i, void const *j) {
  st *x = e + *(int*)i;
  st *y = e + *(int*)j;
  if (x->a != y->a) return x->a - y->a;
  if (x->b != y->b) return x->b - y->b;
  return x->c - y->c;
}

long long plan_roller_coaster(int n, int *s, int *t) {
  int len = 0;
  for (int i = 0; i < n; i++) {
    e[len++] = (st) {s[i], 1, i};
    e[len++] = (st) {t[i], -1, i};
  }
  e[len++] = (st) {INF, 1, n};
  e[len++] = (st) {1, -1, n};
  n++;
  for (int i = 0; i < n; ++i) {
    p[i] = i;
  }
  for (int i = 0; i < len; i++) {
    id[i] = i;
  }
  qsort(id, len, sizeof(int), comp);
  int cn = 0;
  long long res = 0;
  for (int i = 0, delta = 0; i + 1 < len; ++i) {
    delta += e[id[i]].b;
    res += max(0, delta) * (long long) (e[id[i + 1]].a - e[id[i]].a);
    if ((e[id[i + 1]].a == e[id[i]].a) || (delta != 0))
      dsu_union(e[id[i]].c, e[id[i + 1]].c);
    ee[cn++] = (st) {e[id[i + 1]].a - e[id[i]].a, e[id[i]].c, e[id[i + 1]].c};
  }
  for (int i = 0; i < cn; i++) e[i] = (st) {ee[i].a, ee[i].b, ee[i].c};
  for (int i = 0; i < cn; i++) id[i] = i;
  qsort(id, cn, sizeof(int), comp);
  for (int i = 0; i < cn; ++i)
    if (dsu_union(e[id[i]].b, e[id[i]].c))
      res += e[id[i]].a;
  return res;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 39700 KB n = 2
2 Correct 0 ms 39700 KB n = 2
3 Correct 0 ms 39700 KB n = 2
4 Correct 0 ms 39700 KB n = 2
5 Correct 0 ms 39700 KB n = 2
6 Correct 0 ms 39700 KB n = 2
7 Correct 0 ms 39700 KB n = 3
8 Correct 0 ms 39700 KB n = 3
9 Correct 0 ms 39700 KB n = 3
10 Correct 0 ms 39700 KB n = 8
11 Correct 0 ms 39700 KB n = 8
12 Correct 0 ms 39700 KB n = 8
13 Correct 0 ms 39700 KB n = 8
14 Correct 0 ms 39700 KB n = 8
15 Correct 0 ms 39700 KB n = 8
16 Correct 0 ms 39700 KB n = 8
17 Correct 0 ms 39700 KB n = 8
18 Correct 0 ms 39700 KB n = 8
19 Correct 0 ms 39700 KB n = 3
20 Correct 0 ms 39700 KB n = 7
21 Correct 0 ms 39700 KB n = 8
22 Correct 0 ms 39700 KB n = 8
23 Correct 0 ms 39700 KB n = 8
24 Correct 0 ms 39700 KB n = 8
25 Correct 0 ms 39700 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 39700 KB n = 2
2 Correct 0 ms 39700 KB n = 2
3 Correct 0 ms 39700 KB n = 2
4 Correct 0 ms 39700 KB n = 2
5 Correct 0 ms 39700 KB n = 2
6 Correct 0 ms 39700 KB n = 2
7 Correct 0 ms 39700 KB n = 3
8 Correct 0 ms 39700 KB n = 3
9 Correct 0 ms 39700 KB n = 3
10 Correct 0 ms 39700 KB n = 8
11 Correct 0 ms 39700 KB n = 8
12 Correct 0 ms 39700 KB n = 8
13 Correct 0 ms 39700 KB n = 8
14 Correct 0 ms 39700 KB n = 8
15 Correct 0 ms 39700 KB n = 8
16 Correct 0 ms 39700 KB n = 8
17 Correct 0 ms 39700 KB n = 8
18 Correct 0 ms 39700 KB n = 8
19 Correct 0 ms 39700 KB n = 3
20 Correct 0 ms 39700 KB n = 7
21 Correct 0 ms 39700 KB n = 8
22 Correct 0 ms 39700 KB n = 8
23 Correct 0 ms 39700 KB n = 8
24 Correct 0 ms 39700 KB n = 8
25 Correct 0 ms 39700 KB n = 8
26 Correct 0 ms 39700 KB n = 8
27 Correct 0 ms 39700 KB n = 8
28 Correct 0 ms 39700 KB n = 8
29 Correct 0 ms 39700 KB n = 16
30 Correct 0 ms 39700 KB n = 16
31 Correct 0 ms 39700 KB n = 16
32 Correct 0 ms 39700 KB n = 16
33 Correct 0 ms 39700 KB n = 16
34 Correct 0 ms 39700 KB n = 16
35 Correct 0 ms 39700 KB n = 16
36 Correct 0 ms 39700 KB n = 15
37 Correct 0 ms 39700 KB n = 8
38 Correct 0 ms 39700 KB n = 16
39 Correct 0 ms 39700 KB n = 16
40 Correct 0 ms 39700 KB n = 9
41 Correct 0 ms 39700 KB n = 16
42 Correct 0 ms 39700 KB n = 16
43 Correct 0 ms 39700 KB n = 16
44 Correct 0 ms 39700 KB n = 9
45 Correct 0 ms 39700 KB n = 15
46 Correct 0 ms 39700 KB n = 16
47 Correct 0 ms 39700 KB n = 16
48 Correct 0 ms 39700 KB n = 16

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 41268 KB Execution killed because of forbidden syscall sysinfo (99)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 39700 KB n = 2
2 Correct 0 ms 39700 KB n = 2
3 Correct 0 ms 39700 KB n = 2
4 Correct 0 ms 39700 KB n = 2
5 Correct 0 ms 39700 KB n = 2
6 Correct 0 ms 39700 KB n = 2
7 Correct 0 ms 39700 KB n = 3
8 Correct 0 ms 39700 KB n = 3
9 Correct 0 ms 39700 KB n = 3
10 Correct 0 ms 39700 KB n = 8
11 Correct 0 ms 39700 KB n = 8
12 Correct 0 ms 39700 KB n = 8
13 Correct 0 ms 39700 KB n = 8
14 Correct 0 ms 39700 KB n = 8
15 Correct 0 ms 39700 KB n = 8
16 Correct 0 ms 39700 KB n = 8
17 Correct 0 ms 39700 KB n = 8
18 Correct 0 ms 39700 KB n = 8
19 Correct 0 ms 39700 KB n = 3
20 Correct 0 ms 39700 KB n = 7
21 Correct 0 ms 39700 KB n = 8
22 Correct 0 ms 39700 KB n = 8
23 Correct 0 ms 39700 KB n = 8
24 Correct 0 ms 39700 KB n = 8
25 Correct 0 ms 39700 KB n = 8
26 Correct 0 ms 39700 KB n = 8
27 Correct 0 ms 39700 KB n = 8
28 Correct 0 ms 39700 KB n = 8
29 Correct 0 ms 39700 KB n = 16
30 Correct 0 ms 39700 KB n = 16
31 Correct 0 ms 39700 KB n = 16
32 Correct 0 ms 39700 KB n = 16
33 Correct 0 ms 39700 KB n = 16
34 Correct 0 ms 39700 KB n = 16
35 Correct 0 ms 39700 KB n = 16
36 Correct 0 ms 39700 KB n = 15
37 Correct 0 ms 39700 KB n = 8
38 Correct 0 ms 39700 KB n = 16
39 Correct 0 ms 39700 KB n = 16
40 Correct 0 ms 39700 KB n = 9
41 Correct 0 ms 39700 KB n = 16
42 Correct 0 ms 39700 KB n = 16
43 Correct 0 ms 39700 KB n = 16
44 Correct 0 ms 39700 KB n = 9
45 Correct 0 ms 39700 KB n = 15
46 Correct 0 ms 39700 KB n = 16
47 Correct 0 ms 39700 KB n = 16
48 Correct 0 ms 39700 KB n = 16
49 Runtime error 79 ms 41268 KB Execution killed because of forbidden syscall sysinfo (99)
50 Halted 0 ms 0 KB -