Submission #1105482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105482		duckindog	Maze (JOI23_ho_t3)	C++17	100 / 100	1780 ms	1623952 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
const int dx[] = {1, 0, -1, 0},
          dy[] = {0, 1, 0, -1};
 
struct DSU { 
  vector<int> id;
  DSU(int n) : id(n, -1) {}
  int root(int u) { return id[u] < 0 ? u : id[u] = root(id[u]); }
  void add(int u, int v) { 
    u = root(u); v = root(v);
    if (u == v) return;
    id[v] = u;
  }
};
 
int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);
 
  int r, c, n; cin >> r >> c >> n;
  int Sr, Sc; cin >> Sr >> Sc;
  int Gr, Gc; cin >> Gr >> Gc;
 
  bool reverse = false;
  if (r < c) { 
    swap(r, c);
    swap(Sr, Sc);
    swap(Gr, Gc);
    reverse = true;
  }
 
  vector<vector<char>> a(r + 10, vector<char>(c + 10));
  if (!reverse) { 
    for (int i = 1; i <= r; ++i) { 
      for (int j = 1; j <= c; ++j) cin >> a[i][j];
    }
  } else { 
    for (int i = 1; i <= c; ++i) { 
      for (int j = 1; j <= r; ++j) cin >> a[j][i];
    }
  } 
 
  auto in = [&](int x, int y) { return 1 <= x && x <= r && 1 <= y && y <= c; };
  
  vector<DSU> R(r + 10, DSU(c + 10));
  vector<DSU> C(c + 10, DSU(r + 10));
     
  vector<vector<int>> f(r + 10, vector<int>(c + 10, 1'000'000'000));
  using T = tuple<int, int, int>;
  deque<T> q({tie(f[Sr][Sc] = 0, Sr, Sc)});
  while (q.size()) { 
    auto [d, x, y] = q.front(); q.pop_front();
    if (d != f[x][y]) continue;
 
    auto add = [&](int nX, int nY, int w) { 
      if (f[nX][nY] > d + w) { 
        if (w) q.emplace_back(f[nX][nY] = d + w, nX, nY);
        else q.emplace_front(f[nX][nY] = d + w, nX, nY);
      }
    };
 
    for (int t = 0; t < 4; ++t) { 
      int nX = x + dx[t], nY = y + dy[t];
      if (!in(nX, nY) || a[nX][nY] == '#') continue;
      add(nX, nY, 0);
    }
 
    { //add a fricking regtangle
      int stX = max(1, x - n + 1), edX = min(r, x + n - 1);
      int stY = max(1, y - n), edY = min(c, y + n);
      
      for (int h = stX; h <= edX; h = C[stY].root(h)) {
        add(h, stY, 1);  
        for (int i = R[h].root(stY); i < edY; i = R[h].root(i)) {
          R[h].add(R[h].root(i) + 1, R[h].root(i));
          add(h, R[h].root(i), 1);
        }
        if (R[h].root(stY) - stY >= 2 * n + 1 || R[h].root(stY) == c) C[stY].add(h + 1, h);
        h += 1;
      }
    }
 
    { //add 2 fricking strips due to the rectangle is not the fucking square
      int stX = max(1, x - n), edX = min(r, x + n);
      int stY = max(1, y - n + 1), edY = min(c, y + n - 1);
      
      for (int type = 0; type < 2; ++type) { 
        int h = (!type ? stX : edX);
        
        add(h, stY, 1);
        for (int i = R[h].root(stY); i < edY; i = R[h].root(i)) {
          R[h].add(R[h].root(i) + 1, R[h].root(i));
          add(h, R[h].root(i), 1);
        }
        if (R[h].root(stY) - stY >= 2 * n + 1 || R[h].root(stY) == c) C[stY].add(h + 1, h);
      }
    }
  }
 
  cout << f[Gr][Gc] << "\n";
  cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
}

• 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