Submission #102861

#	Time	Username	Problem	Language	Result	Execution time	Memory
102861		wxh010910	Wombats (IOI13_wombats)	C++17	100 / 100	9726 ms	138424 KiB

wombats

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24