oj.uz

Submission #102861

# Submission time Handle Problem Language Result Execution time Memory
102861 2019-03-28T03:23:43 Z wxh010910 Wombats (IOI13_wombats) C++17
100 / 100
 9726 ms 138424 KB 
#include <bits/stdc++.h>
#include "wombats.h"

using namespace std;

const int B = 15;
const int inf = 0x3f3f3f3f;

vector<vector<vector<int>>> tree;
vector<vector<int>> ver, hor;
int n, m, q;

vector<vector<int>> brute(int l, int r) {
  vector<vector<int>> ans;
  r = min(r, n);
  for (int i = 0; i < m; ++i) {
    vector<int> dist(m, inf);
    dist[i] = 0;
    for (int j = l; j < r; ++j) {
      for (int k = 0; k + 1 < m; ++k) {
        dist[k + 1] = min(dist[k + 1], dist[k] + hor[j][k]);
      }
      for (int k = m - 1; k; --k) {
        dist[k - 1] = min(dist[k - 1], dist[k] + hor[j][k - 1]);
      }
      for (int k = 0; k < m; ++k) {
        dist[k] += ver[j][k];
      }
    }
    ans.push_back(dist);
  }
  return ans;
}

vector<vector<int>> unite(const vector<vector<int>> &foo, const vector<vector<int>> &bar) {
  vector<vector<int>> ans(m, vector<int>(m, inf));
  for (int i = 0; i < m; ++i) {
    function<void(int, int, int, int)> solve = [&](int l, int r, int ll, int rr) {
      if (l > r) {
        return;
      }
      int mid = (l + r) >> 1;
      int pos = -1;
      for (int j = ll; j <= rr; ++j) {
        if (ans[i][mid] > foo[i][j] + bar[j][mid]) {
          ans[i][mid] = foo[i][j] + bar[j][mid];
          pos = j;
        }
      }
      solve(l, mid - 1, ll, pos);
      solve(mid + 1, r, pos, rr);
    };
    solve(0, m - 1, 0, m - 1);
  }
  return ans;
}

void build(int x, int l, int r) {
  if (l == r) {
    tree[x] = brute(l * B, (l + 1) * B);
  } else {
    int y = (l + r) >> 1, z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    tree[x] = unite(tree[x + 1], tree[z]);
  }
}

void modify(int x, int l, int r, int p) {
  if (l == r) {
    tree[x] = brute(l * B, (l + 1) * B);
  } else {
    int y = (l + r) >> 1, z = x + ((y - l + 1) << 1);
    if (p <= y) {
      modify(x + 1, l, y, p);
    } else {
      modify(z, y + 1, r, p);
    }
    tree[x] = unite(tree[x + 1], tree[z]);
  }
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
  n = R;
  m = C;
  hor = vector<vector<int>>(n, vector<int>(m - 1, 0));
  ver = vector<vector<int>>(n, vector<int>(m, 0));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m - 1; ++j) {
      hor[i][j] = H[i][j];
    }
  }
  for (int i = 0; i < n - 1; ++i) {
    for (int j = 0; j < m; ++j) {
      ver[i][j] = V[i][j];
    }
  }
  q = (R + B - 1) / B;
  tree.resize(q * 2 - 1);
  build(0, 0, q - 1);
}

void changeH(int P, int Q, int W) {
  hor[P][Q] = W;
  modify(0, 0, q - 1, P / B);
}

void changeV(int P, int Q, int W) {
  ver[P][Q] = W;
  modify(0, 0, q - 1, P / B);
}

int escape(int V1, int V2) {
  return tree[0][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]
  int res;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4736 KB Output is correct
2 Correct 7 ms 4736 KB Output is correct
3 Correct 68 ms 7416 KB Output is correct
4 Correct 8 ms 4652 KB Output is correct
5 Correct 8 ms 4736 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 67 ms 2680 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 1256 KB Output is correct
2 Correct 138 ms 1280 KB Output is correct
3 Correct 196 ms 1400 KB Output is correct
4 Correct 162 ms 1408 KB Output is correct
5 Correct 172 ms 1280 KB Output is correct
6 Correct 2 ms 360 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 280 KB Output is correct
9 Correct 762 ms 1328 KB Output is correct
10 Correct 3 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8832 KB Output is correct
2 Correct 15 ms 8832 KB Output is correct
3 Correct 14 ms 8960 KB Output is correct
4 Correct 57 ms 10192 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 1244 KB Output is correct
2 Correct 138 ms 1400 KB Output is correct
3 Correct 167 ms 1572 KB Output is correct
4 Correct 172 ms 1316 KB Output is correct
5 Correct 157 ms 1528 KB Output is correct
6 Correct 20 ms 8952 KB Output is correct
7 Correct 13 ms 8960 KB Output is correct
8 Correct 15 ms 8960 KB Output is correct
9 Correct 44 ms 10232 KB Output is correct
10 Correct 9 ms 4736 KB Output is correct
11 Correct 8 ms 4736 KB Output is correct
12 Correct 73 ms 7444 KB Output is correct
13 Correct 9 ms 4736 KB Output is correct
14 Correct 9 ms 4736 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 356 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 3 ms 356 KB Output is correct
25 Correct 79 ms 2780 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 763 ms 1400 KB Output is correct
28 Correct 2219 ms 46200 KB Output is correct
29 Correct 2241 ms 38364 KB Output is correct
30 Correct 2302 ms 38444 KB Output is correct
31 Correct 2123 ms 47796 KB Output is correct
32 Correct 2 ms 384 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 1244 KB Output is correct
2 Correct 148 ms 1280 KB Output is correct
3 Correct 166 ms 1352 KB Output is correct
4 Correct 180 ms 1500 KB Output is correct
5 Correct 176 ms 1280 KB Output is correct
6 Correct 15 ms 8960 KB Output is correct
7 Correct 14 ms 8832 KB Output is correct
8 Correct 17 ms 8952 KB Output is correct
9 Correct 83 ms 10232 KB Output is correct
10 Correct 9 ms 4736 KB Output is correct
11 Correct 9 ms 4736 KB Output is correct
12 Correct 73 ms 7544 KB Output is correct
13 Correct 8 ms 4736 KB Output is correct
14 Correct 8 ms 4736 KB Output is correct
15 Correct 1502 ms 137080 KB Output is correct
16 Correct 9537 ms 138424 KB Output is correct
17 Correct 3 ms 256 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 256 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 80 ms 2808 KB Output is correct
28 Correct 3 ms 384 KB Output is correct
29 Correct 746 ms 1372 KB Output is correct
30 Correct 2416 ms 46032 KB Output is correct
31 Correct 8713 ms 135972 KB Output is correct
32 Correct 8294 ms 135980 KB Output is correct
33 Correct 1966 ms 38320 KB Output is correct
34 Correct 8720 ms 112308 KB Output is correct
35 Correct 2082 ms 38424 KB Output is correct
36 Correct 8712 ms 112472 KB Output is correct
37 Correct 2323 ms 47824 KB Output is correct
38 Correct 9027 ms 136408 KB Output is correct
39 Correct 2 ms 384 KB Output is correct
40 Correct 9726 ms 112672 KB Output is correct