oj.uz

Submission #516385

# Submission time Handle Problem Language Result Execution time Memory
516385 2022-01-21T09:03:08 Z 600Mihnea Wombats (IOI13_wombats) C++17
55 / 100
 8352 ms 262148 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 5000 + 7;
const int M = 200 + 7;
const int INF = (int) 1e9 + 7;
int H[N][M];
int V[N][M];

int n;
int m;

struct Node {
  int l;
  int r;
  Node* lft;
  Node* rgh;
  int cost[M][M];
  Node() :
    l(),
    r(0),
    lft(nullptr),
    rgh(nullptr) {
    for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) cost[i][j] = INF;
  }
};

Node* getSmall(int l, int r) {
  assert(l <= r);
  Node* solution = new Node;
  solution->l = l;
  solution->r = r;
  for (int start = 0; start < m; start++) {
    solution->cost[start][start] = 0;
    for (int col = 1; col < m; col++) {
      solution->cost[start][col] = min(solution->cost[start][col], solution->cost[start][col - 1] + H[l][col - 1]);
    }
    for (int col = m - 2; col >= 0; col--){
      solution->cost[start][col] = min(solution->cost[start][col], solution->cost[start][col + 1] + H[l][col]);
    }
  }
  for (int row = l + 1; row <= r; row++) {
    /// add row j
    for (int start = 0; start < m; start++) {
      for (int col = 0; col < m; col++) {
        solution->cost[start][col] += V[row - 1][col];
      }
      for (int col = 1; col < m; col++) {
        solution->cost[start][col] = min(solution->cost[start][col], solution->cost[start][col - 1] + H[row][col - 1]);
      }
      for (int col = m - 2; col >= 0; col--){
        solution->cost[start][col] = min(solution->cost[start][col], solution->cost[start][col + 1] + H[row][col]);
      }
    }
  }
  return solution;
}

int A[M][M];
int B[M][M];

Node* join(Node* lft, Node* rgh) {
  Node* solution = new Node;
  solution->l = lft->l;
  solution->r = rgh->r;
  solution->lft = lft;
  solution->rgh = rgh;
  assert(lft->r + 1 == rgh->l);
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < m; j++) {
      A[i][j] = lft->cost[i][j] + V[lft->r][j];
      B[i][j] = rgh->cost[i][j];
    }
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < m; j++) {
      for (int k = 0; k < m; k++) {
        solution->cost[i][k] = min(solution->cost[i][k], A[i][j] + B[j][k]);
      }
    }
  }
  return solution;
}

const int SMALL_LEN = 10;

Node* update(Node* node, int pos) {
  if (node->r < pos || pos < node->l) assert(0);
  int LEN = node->r - node->l + 1;
  if (LEN <= SMALL_LEN) {
    return getSmall(node->l, node->r);
  } else {
    int m = (node->l + node->r) / 2;
    if (pos <= m) {
      return join(update(node->lft, pos), node->rgh);
    } else {
      return join(node->lft, update(node->rgh, pos));
    }
  }
}

Node* build(int l, int r) {
  int LEN = r - l + 1;
  if (LEN <= SMALL_LEN) {
    return getSmall(l, r);
  } else {
    int m = (l + r) / 2;
    return join(build(l, m), build(m + 1, r));
  }
}

Node* root;

void print(Node* guy) {
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < m; j++) {
      cout << guy->cost[i][j] << " ";
    }
    cout << "\n";
  }

}

void init(int R, int C, int Hinit[5000][200], int Vinit[5000][200]) {
  n = R;
  m = C;
  root = new Node;
  root->l = 1;
  for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) H[i][j] = Hinit[i][j], V[i][j] = Vinit[i][j];


  if (0) {
    Node* guy01 = getSmall(0, 1);
    Node* a = getSmall(0, 0);
    Node* b = getSmall(1, 1);
    Node* ret = join(a, b);

    cout << "expected:\n"; print(guy01);
    cout << "a:\n"; print(a);
    cout << "b:\n"; print(b);
    cout << "ret:\n"; print(ret);
    exit(0);
  }

  root = build(0, n - 1);


  /* ... */
}

void changeH(int P, int Q, int W) {
  /* ... */
  H[P][Q] = W;
  root = update(root, P);
}

void changeV(int P, int Q, int W) {
  /* ... */
  V[P][Q] = W;
  root = update(root, P);
}

int escape(int V1, int V2) {
  return root->cost[V1][V2];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 38368 KB Output is correct
2 Correct 20 ms 38388 KB Output is correct
3 Correct 83 ms 39964 KB Output is correct
4 Correct 19 ms 38300 KB Output is correct
5 Correct 19 ms 38348 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 68 ms 1400 KB Output is correct
12 Correct 1 ms 460 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 45720 KB Output is correct
2 Correct 521 ms 43460 KB Output is correct
3 Correct 465 ms 45628 KB Output is correct
4 Correct 498 ms 45592 KB Output is correct
5 Correct 452 ms 43504 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 2273 ms 214284 KB Output is correct
10 Correct 0 ms 332 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 42232 KB Output is correct
2 Correct 21 ms 42216 KB Output is correct
3 Correct 21 ms 42292 KB Output is correct
4 Correct 52 ms 42996 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 45656 KB Output is correct
2 Correct 445 ms 43528 KB Output is correct
3 Correct 460 ms 45620 KB Output is correct
4 Correct 461 ms 45584 KB Output is correct
5 Correct 469 ms 43460 KB Output is correct
6 Correct 27 ms 42308 KB Output is correct
7 Correct 24 ms 42220 KB Output is correct
8 Correct 22 ms 42288 KB Output is correct
9 Correct 53 ms 43100 KB Output is correct
10 Correct 19 ms 38348 KB Output is correct
11 Correct 20 ms 38308 KB Output is correct
12 Correct 105 ms 39912 KB Output is correct
13 Correct 21 ms 38380 KB Output is correct
14 Correct 19 ms 38340 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 64 ms 1444 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Correct 2218 ms 214288 KB Output is correct
28 Runtime error 2785 ms 262148 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 45640 KB Output is correct
2 Correct 448 ms 43488 KB Output is correct
3 Correct 483 ms 45636 KB Output is correct
4 Correct 471 ms 45692 KB Output is correct
5 Correct 438 ms 43492 KB Output is correct
6 Correct 23 ms 42208 KB Output is correct
7 Correct 24 ms 42216 KB Output is correct
8 Correct 23 ms 42300 KB Output is correct
9 Correct 53 ms 43068 KB Output is correct
10 Correct 20 ms 38368 KB Output is correct
11 Correct 19 ms 38380 KB Output is correct
12 Correct 81 ms 39932 KB Output is correct
13 Correct 19 ms 38348 KB Output is correct
14 Correct 19 ms 38348 KB Output is correct
15 Correct 5570 ms 191384 KB Output is correct
16 Runtime error 8352 ms 262148 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -