Submission #838047

#	Time	Username	Problem	Language	Result	Execution time	Memory
838047		gun_gan	Maze (JOI23_ho_t3)	C++17	51 / 100	2078 ms	216844 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int MX = 6e6 + 5;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int N, R, C;
int sc, sr, gc, gr;
string s[MX];

vector<vector<int>> par;

int nxt(int r, int c) { // row, column
      return par[r][c] == c ? c : par[r][c] = nxt(r, par[r][c]);
}

void merge(int r, int c, int cc) {
      if(cc >= C) return;
      c = nxt(r, c); cc = nxt(r, cc);
      if(c == cc) return;
      par[r][c] = cc;
}

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

      cin >> R >> C >> N;
      cin >> sr >> sc >> gr >> gc;
      for(int i = 0; i < R; i++) cin >> s[i];
      sc--, sr--, gc--, gr--;

      par = vector<vector<int>>(R, vector<int>(C));

      for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                  par[i][j] = j;
            }
      }

      vector<vector<int>> dist(R, vector<int>(C, 1e9));
      vector<vector<bool>> vis(R, vector<bool>(C));

      deque<pair<int,int>> dq;
      dq.push_back({sr, sc});
      dist[sr][sc] = 0;
      while(!dq.empty()) {
            auto [x, y] = dq.front(); dq.pop_front();
            if(vis[x][y]) continue;
            vis[x][y] = 1;
            for(int k = 0; k < 4; k++) {
                  int r = x + dx[k], c = y + dy[k];
                  if(r >= 0 && r < R && c >= 0 && c < C && dist[r][c] > dist[x][y] && s[r][c] == '.') {
                        dist[r][c] = dist[x][y];
                        dq.push_front({r, c});
                        if(x == r && nxt(r, y) != nxt(r, c)) merge(r, min(y, c), max(y, c)); 
                  }
            }

            for(int r = max(0, x - N); r <= min(R - 1, x + N); r++) {
                  int b = abs(x - r) == N;
                  int c = nxt(r, max(0, y - N + b)), prv = -1;
                  while(c <= min(C - 1, y + N - b)) {
                        if(dist[r][c] > dist[x][y] + 1) {
                              dist[r][c] = dist[x][y] + 1;
                              dq.push_back({r, c});
                        }
                        if(prv != -1)
                              merge(r, prv, c);

                        prv = c;
                        if(nxt(r, c) + 1 < C)
                              c = nxt(r, nxt(r, c) + 1);
                        else
                              break;
                  }
            }
      }

      cout << dist[gr][gc] << '\n';
}

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