Submission #1253978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253978		LucaLucaM	Maze (JOI23_ho_t3)	C++20	27 / 100	2093 ms	271088 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

const int INF = 1e9;
const int dx[4] = {-1, 0, +1, 0};
const int dy[4] = {0, -1, 0, +1};

struct Fenwick2D {
  std::vector<std::vector<int>> aib;
  int n, m;
  void init(int _n, int _m) {
    n = _n + 2;
    m = _m + 2;
    aib = std::vector<std::vector<int>>(n + 3, std::vector<int>(m + 3, 0));
  }

  void update(int x, int y, int v) {
    x++, y++;
    for (int i = x; i < n; i += i & -i) {
      for (int j = y; j < m; j += j & -j) {
        aib[i][j] += v;
      }
    }
  }

  int query(int x, int y) {
    x++, y++;
    int ret = 0;
    for (int i = x; i > 0; i -= i & -i) {
      for (int j = y; j > 0; j -= j & -j) {
        ret += aib[i][j];
      }
    }
    return ret;
  }

  int pointQuery(int i, int j) {
    return query(i, j) - query(i, j - 1) - query(i - 1, j) + query(i - 1, j - 1);
  }

  std::vector<std::pair<int, int>> findAll(int x1, int y1, int x2, int y2) {
    x1++, y1++, x2++, y2++;
    assert(1 <= x1 && x1 <= x2 && x2 < n);
    assert(1 <= y1 && y1 <= y2 && y2 < m);
    std::vector<std::pair<int, int>> ret;
    for (int i = x1; i <= x2; i++) {
      for (int j = y1; j <= y2; j++) {
        int me = pointQuery(i - 1, j - 1); 
        if (me == 1) {
          ret.push_back({i, j});
        }
      }
    }
    return ret;
    for (int i = x1; i <= x2; i++) {
      int p = y1;
      int steps = query(i, y2) - query(i, y1 - 1);
      while (p <= y2 && steps--) {
        int l = p, r = y2;
        while (l < r) {
          int mid = (l + r) / 2;
          if (query(i, mid) - query(i, p - 1)) {
            r = mid;
          } else {
            l = mid + 1;
          }
        }
        ret.push_back({i, r});
        p = r + 1;
      } 
      return ret;
    }
  }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n, m, k;
  std::cin >> n >> m >> k;

  int x1, y1, x2, y2;
  std::cin >> x1 >> y1 >> x2 >> y2;
  x1--, y1--, x2--, y2--;

  std::vector<std::vector<int>> a(n, std::vector<int>(m));

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      char c;
      std::cin >> c;
      if (c == '.')  {
        a[i][j] = 0;
      } else {
        a[i][j] = 1;
      }
    }
  }

  std::vector<std::set<std::pair<int, int>>> thisDistance(n * m + 2);

  std::vector<std::vector<int>> dist(n, std::vector<int>(m, +INF));

  dist[x1][y1] = 0;

  thisDistance[0].insert({x1, y1});

  Fenwick2D DS;
  DS.init(n, m);

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      DS.update(i, j, +1);
    }
  }

  auto removeSubmatrix = [&](int x1, int y1, int x2, int y2, int d) {
    x1 = std::max(x1, 0);
    y1 = std::max(y1, 0);
    x2 = std::min(x2, n - 1);
    y2 = std::min(y2, m - 1);
    if (x1 > x2 || y1 > y2) {
      return;
    }
    assert(0 <= x1 && x1 <= x2 && x2 <= n - 1);
    assert(0 <= y1 && y1 <= y2 && y2 <= m - 1);
    auto ret = DS.findAll(x1, y1, x2, y2);
    // std::cout << " \n ! \n";
    // std::cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << d << ' ' << DS.pointQuery(0, 0) << '\n';
    for (auto [x, y] : ret) {
      x--, y--;
      // std::cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << d << ' ' << x << ' ' << y << '\n';
      DS.update(x, y, -1);
      dist[x][y] = d + 1;
      thisDistance[d + 1].insert({x, y});
    }
  };

  for (int d = 0; d <= n * m; d++) {
    std::set<std::pair<int, int>> st;

    auto dfs = [&](auto &&self, int x, int y) -> void {
      st.insert({x, y});
      for (int dir = 0; dir < 4; dir++) {
        int xx = x + dx[dir], yy = y + dy[dir];
        if (0 <= xx && xx < n && 0 <= yy && yy < m && dist[xx][yy] > d && !a[xx][yy]) {
          dist[xx][yy] = d;
          self(self, xx, yy);
        }
      }
    };

    for (const auto &[x, y] : thisDistance[d]) {
      if (dist[x][y] < d) {
        continue;
      }
      dfs(dfs, x, y);
      st.insert({x, y});
    }

    if (st.count({x2, y2})) {
      std::cout << d;
      return 0;
    }

    for (const auto &[x, y] : st) {
      if (DS.pointQuery(x, y) == 1) {
        DS.update(x, y, -1);
      }
      assert(DS.pointQuery(x, y) == 0);
    }

    for (const auto &[x, y] : st) {
      removeSubmatrix(x - (k - 1), y - k, x + (k - 1), y + k, d);
      removeSubmatrix(x - k, y - (k - 1), x - k, y + (k - 1), d);
      removeSubmatrix(x + k, y - (k - 1), x + k, y + (k - 1), d);
    }
  }

  std::cout << dist[x2][y2];
  
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 0 / 16
• Subtask 4: 0 / 19
• Subtask 5: 0 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6