Submission #839451

#	Time	Username	Problem	Language	Result	Execution time	Memory
839451		dong_liu	Maze (JOI23_ho_t3)	C++17	100 / 100	1642 ms	300120 KiB

Main

#pragma GCC optimize("O3,unroll-loops")

#include "bits/stdc++.h"

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

const int NM = 6e6;

typedef pair<int, int> pi;

struct Range {
  int p[NM], n, m;
  bool rem[NM];

  Range(int n, int m) : n(n), m(m) {
    for (int i = 0; i < n*m; i++) p[i] = i, rem[i] = false;
  }
  int dsf(int i) {
    return p[i] == i ? i : p[i] = dsf(p[i]);
  }
  void dsj(int i, int j) { p[dsf(i)] = dsf(j); }
  bool has(int i) { return !rem[i]; }
  void remove(int i) {
    if (i > 0 && rem[i-1]) dsj(i-1, i);
    if (i+1 < n && rem[i+1]) dsj(i, i+1);
    rem[i] = 1;
  }
  int next(int i) { return i == n ? n : !rem[i] ? i : dsf(i)+1; }
  int next(int i, int j) { return min(m,next(i*m+j)-i*m); }
  void remove(int i, int j) { remove(i*m+j); }
  bool has(int i, int j) { return has(i*m+j); }
};

int main() {
  ios::sync_with_stdio(false);
  cin.exceptions(cin.failbit);
  cin.tie(NULL);
  int k, n, m;
  cin >> n >> m >> k;
  int i1, j1, i2, j2;
  cin >> i1 >> j1 >> i2 >> j2, i1--, j1--, i2--, j2--;
  static char g[NM+1];
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < m; j++) g[i*m+j] = s[j];
  }
  Range row(n, m), col(m, n);
  static int d[NM];
  for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) d[i*m+j] = -1;
  static bool fl[NM];
  vector<pi> f;
  d[i1*m+j1] = 0, f.push_back({i1, j1}), row.remove(i1,j1), col.remove(j1,i1);
  for (int x = 0; ; x++) {
    for (int p = 0; p < int(f.size()); p++) {
      auto [i,j] = f[p];
      fl[i*m+j] = true;
      if (i == i2 && j == j2) {
        cout << x << '\n';
        return 0;
      }
      if (i > 0 && g[(i-1)*m+j] == '.' && d[(i-1)*m+j] == -1)
        d[(i-1)*m+j] = x, f.push_back({i-1,j}), row.remove(i-1,j), col.remove(j,i-1);
      if (i+1 < n && g[(i+1)*m+j] == '.' && d[(i+1)*m+j] == -1)
        d[(i+1)*m+j] = x, f.push_back({i+1,j}), row.remove(i+1,j), col.remove(j,i+1);
      if (j > 0 && g[i*m+j-1] == '.' && d[i*m+j-1] == -1)
        d[i*m+j-1] = x, f.push_back({i,j-1}), row.remove(i,j-1), col.remove(j-1,i);
      if (j+1 < m && g[i*m+j+1] == '.' && d[i*m+j+1] == -1)
        d[i*m+j+1] = x, f.push_back({i,j+1}), row.remove(i,j+1), col.remove(j+1,i);
    }
    vector<pi> half = f, g;
    for (auto [i,j] : f) {
      int p = row.next(i,max(0,j-k));
      while (p < m && p <= j+k) {
        d[i*m+p] = x+1;
        if (abs(p-j) != k) {
          row.remove(i,p), col.remove(p,i);
          fl[i*m+p] = true;
        }
        half.push_back({i,p}), g.push_back({i,p});
        p = row.next(i,p+1);
      }
    }
    for (auto [i,j] : half) if (row.has(i,j))
      row.remove(i,j), col.remove(j,i);
    for (auto [i,j] : half) {
      int bound = k - (fl[i*m+j]?0:1);
      int p = col.next(j,max(0,i-bound));
      while (p < n && p <= i+bound) {
        d[p*m+j] = x+1;
        g.push_back({p,j});
        row.remove(p,j), col.remove(j,p);
        p = col.next(j,p+1);
      }
    }
    f = move(g);
  }
}

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