Submission #914015

#	Time	Username	Problem	Language	Result	Execution time	Memory
914015		mychecksedad	Maze (JOI23_ho_t3)	C++17	8 / 100	441 ms	450972 KiB

Main

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 6e6+100, M = 1e5+10, K = 52, MX = 30;

int r, c, n, sx, sy, ex, ey, arr[4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; 
string s[N];
vector<vector<int>> dp, dist;
vector<array<int, 2>> g[N];

int calc(int x, int y, int ax, int ay){
  if(x==ax) return dp[0][abs(y-ay)-1];
  if(y==ay) return dp[abs(x-ax)-1][0];
  return min(dp[abs(x-ax)][abs(y-ay)-1], dp[abs(x-ax)-1][abs(y-ay)]);
}

void solve(){
  cin >> r >> c >> n >> sx >> sy >> ex >> ey;
  sx--, sy--, ex--, ey--;
  for(int i = 0; i < r; ++i) cin >> s[i];
  dp.resize(r + 5);
  dist.resize(r + 5);
  for(int i = 0; i < r + 5; ++i){
    dp[i].resize(c + 5);
    dist[i].resize(c + 5);
    for(int j = 0; j < c + 5; ++j){
      if(i==j && i==0) dp[i][j] = 0;
      else{
        if(i < n || j < n) dp[i][j] = max((i+n-1)/n, (j+n-1)/n);
        else dp[i][j] = min({dp[i-n][j-n+1], dp[i-n+1][j-n], dp[i-n][j], dp[i][j-n]}) + 1;
      }
    }
  }
  // for(int i = 0; i <= r; ++i){
  //   for(int j = 0; j <= c; ++j){
  //     cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
  //   }
  //   en;
  // }
  vector<vector<pair<int, int>>> C;
  vector<vector<int>> vis(r, vector<int>(c));
  for(int i = 0; i < r; ++i){
    for(int j = 0; j < c; ++j){
      if(s[i][j] == '#' || vis[i][j]) continue;
      queue<pair<int, int>> q;
      q.push({i, j});
      vis[i][j] = C.size() + 1;
      C.pb({});
      while(!q.empty()){
        int x = q.front().first, y = q.front().second;
        q.pop();
        C.back().pb({x, y});
        for(int l = 0; l < 4; ++l){
          int x1 = x + arr[l][0], x2 = y + arr[l][1];
          if(x1 >= 0 && x2 >= 0 && x1 < r && x2 < c && s[x1][x2] != '#' && !vis[x1][x2]){
            q.push({x1, x2});
            vis[x1][x2] = C.size();
          }
        }
      }
    }
  }
  for(int i = 0; i < r; ++i){
    int last = -1;
    for(int j = c - 1; j >= 0; --j){
      if(s[i][j] == '.') last = j;
      dist[i][j] = last; 
    }
  }
  for(int i = 0; i < r; ++i){
    for(int j = 0; j < c; ++j){
      if(s[i][j] == '#') continue;
      int x = i;
      int v = vis[i][j];
      if(j < c - 1){
        if(dist[i][j + 1] != -1){
          int u = vis[i][dist[i][j + 1]];
          if(u != v){
            g[v].pb({u, calc(i, j, i, dist[i][j+1])});
            g[u].pb({v, calc(i, j, i, dist[i][j+1])});
          }
        }
      }
      for(int l = x - 1; l >= 0; --l){
        if(s[l][j] != '#'){
          int u = vis[l][j];
          if(u==v) break;
          g[v].pb({u, calc(i, j, l, j)});
          g[u].pb({v, calc(i, j, l, j)});
          break;
        }
        if(dist[l][j] != -1){
          int u = vis[l][dist[l][j]];
          g[v].pb({u, calc(i, j, l, dist[l][j])});
          g[u].pb({v, calc(i, j, l, dist[l][j])});
        }
      }
      for(int l = x + 1; l < r; ++l){
        if(s[l][j] != '#'){
          int u = vis[l][j];
          if(u==v) break;
          g[v].pb({u, calc(i, j, l, j)});
          g[u].pb({v, calc(i, j, l, j)});
          break;
        }
        if(dist[l][j] != -1){
          int u = vis[l][dist[l][j]];
          g[v].pb({u, calc(i, j, l, dist[l][j])});
          g[u].pb({v, calc(i, j, l, dist[l][j])});
        }
      }
    }
  }
  priority_queue<pair<int, int>> Q;
  Q.push({0, vis[sx][sy]});
  vector<int> D(N, MOD);
  vector<bool> used(N);
  D[vis[sx][sy]] = 0;
  while(!Q.empty()){
    int v = Q.top().second; Q.pop();
    if(used[v]) continue;
    used[v] = 1;
    for(auto U: g[v]){
      int u = U[0];
      if(!used[u] && D[u] > D[v] + U[1]){
        D[u] = D[v] + U[1];
        Q.push({-D[u], u});
      }
    }
  }
  // int c = 0;
  // for(auto v: C){
  //   cout << c+1 << '\n';
  //   ++c;
  //   for(auto p: v) cout << p.first << ' ' << p.second << '\n';
  //   en;
  // }
  // en;
  // en;
  // for(int i = 1; i <= C.size(); ++i){
  //   cout << i << '\n';
  //   for(auto u: g[i]){
  //     cout << u[0] << ' ' << u[1] << '\n';
  //   }
  //   en;
  // }

  cout << min(D[vis[ex][ey]], calc(sx, sy, ex, ey));
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:160:15: warning: unused variable 'aa' [-Wunused-variable]
  160 |   int tt = 1, aa;
      |               ^~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 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