Submission #838006

#	Time	Username	Problem	Language	Result	Execution time	Memory
838006		gun_gan	Maze (JOI23_ho_t3)	C++17	51 / 100	2063 ms	553756 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];

set<int> st[MX];

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--;

      for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                  st[i].insert(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;
      st[sr].erase(sc);
      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(st[r].count(c)) st[r].erase(c);
                  }
            }

            for(int r = max(0, x - N); r <= min(R - 1, x + N); r++) {
                  int b = abs(x - r) == N;
                  auto c = st[r].lower_bound(max(0, y - N + b));
                  while(c != st[r].end() && *c <= min(C - 1, y + N - b)) {
                        dist[r][*c] = dist[x][y] + 1;
                        dq.push_back({r, *c});
                        c = st[r].erase(c);
                  }
            }
      }

      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