oj.uz

Submission #791904

# Submission time Handle Problem Language Result Execution time Memory
791904 2023-07-24T12:25:57 Z cig32 Maze (JOI23_ho_t3) C++17
19 / 100
 14 ms 10352 KB 
#include "bits/stdc++.h"
using namespace std;
//#define int long long
#ifdef ONLINE_JUDGE
const int MAXN = 5.4e7 + 10;
#endif
#ifndef ONLINE_JUDGE
const int MAXN = 1e5 + 10;
#endif
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
int r,c,n,sr,sc,gr,gc;
vector<vector<char>>a;
vector<int>adj[MAXN];
int dist[MAXN];
bool vis[MAXN];
int nxt;
int f(int i, int j) {
  return i*c+j;
}
void solve(int tc) {
  for(int i=0; i<MAXN; i++) dist[i] = 1e9;
  cin>>r>>c>>n;
  cin>>sr>>sc;
  cin>>gr>>gc;
  sr--,sc--,gr--,gc--;
  a.resize(r);
  for(int i=0;i<r;i++){
    a[i].resize(c);
    for(int j=0;j<c;j++){
      cin>>a[i][j];
    }
  }
  for(int i=0;i<r;i++){
    for(int j=0;j+1<c;j++){
      if(a[i][j]=='.'&&a[i][j+1]=='.'){
        adj[f(i,j)].push_back(f(i,j+1));
        adj[f(i,j+1)].push_back(f(i,j));
      }
    }
  }
  for(int i=0;i+1<r;i++){
    for(int j=0;j<c;j++){
      if(a[i][j]=='.'&&a[i+1][j]=='.'){
        adj[f(i,j)].push_back(f(i+1,j));
        adj[f(i+1,j)].push_back(f(i,j));
      }
    }
  }
  //pt3
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      if(i%n != n-1 && i+1 < r) {
        adj[f(2*r+i, j)].push_back(f(2*r+i+1, j));
        adj[f(6*r+i, j)].push_back(f(6*r+i+1, j));
      }
      if(j%n != n-1 && j+1 < c) {
        adj[f(2*r+i, j)].push_back(f(2*r+i, j+1));
        adj[f(6*r+i, j)].push_back(f(6*r+i, j+1));
      }
    }
  }
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      if(i%n != n-1 && i+1 < r) {
        adj[f(3*r+i, j)].push_back(f(3*r+i+1, j));
        adj[f(7*r+i, j)].push_back(f(7*r+i+1, j));
      }
      if(j%n != 0 && j-1 >= 0) {
        adj[f(3*r+i, j)].push_back(f(3*r+i, j-1));
        adj[f(7*r+i, j)].push_back(f(7*r+i, j-1));
      }
    }
  }
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      if(i%n != 0 && i-1 >= 0) {
        adj[f(4*r+i, j)].push_back(f(4*r+i-1, j));
        adj[f(8*r+i, j)].push_back(f(8*r+i-1, j));
      }
      if(j%n != 0 && j-1 >= 0) {
        adj[f(4*r+i, j)].push_back(f(4*r+i, j-1));
        adj[f(8*r+i, j)].push_back(f(8*r+i, j-1));
      }
    }
  }
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      if(i%n != 0 && i-1 >= 0) {
        adj[f(5*r+i, j)].push_back(f(5*r+i-1, j));
        adj[f(9*r+i, j)].push_back(f(9*r+i-1, j));
      }
      if(j%n != n-1 && j+1 < c) {
        adj[f(5*r+i, j)].push_back(f(5*r+i, j+1));
        adj[f(9*r+i, j)].push_back(f(9*r+i, j+1));
      }
    }
  }
  for(int i=2;i<6;i++){
    for(int j=0;j<r*c;j++){
      adj[j].push_back(i*r*c+j);
    }
  }
  for(int i=6;i<10;i++){
    for(int j=0;j<r*c;j++){
      adj[i*r*c+j].push_back(j);
    }
  }
  for(int i=0;i+n-1<r;i++){
    for(int j=0;j+n-1<c;j++){
      adj[f(r+i,j)].push_back(f(6*r+i,j));
      adj[f(4*r+i,j)].push_back(f(r+i,j));
      if(j%n!=0) {
        adj[f(r+i,j)].push_back(f(7*r+i,j+n-1));
        adj[f(5*r+i,j+n-1)].push_back(f(r+i,j));
      }
      if(i%n!=0) {
        adj[f(r+i,j)].push_back(f(9*r+i+n-1,j));
        adj[f(3*r+i+n-1,j)].push_back(f(r+i,j));
      }
      if(i%n!=0 && j%n!=0) {
        adj[f(r+i,j)].push_back(f(8*r+i+n-1,j+n-1));
        adj[f(2*r+i+n-1,j+n-1)].push_back(f(r+i,j));
      }
    }
  }
  //pt2
  for(int i=0;i+n-1<r;i++){
    for(int j=0;j+n-1<c;j++){
      for(int k=-n+1;k<n;k+=n-1){
        if(i+k>=0 && i+k<r && j>=n) adj[f(r+i,j)].push_back(f(r+i+k,j-n));
        if(i+k>=0 && i+k<r && j+n<c) adj[f(r+i,j)].push_back(f(r+i+k,j+n));
        if(j+k>=0 && i>=n && j+k<c) adj[f(r+i,j)].push_back(f(r+i-n,j+k));
        if(j+k>=0 && i+n<r && j+k<c) adj[f(r+i,j)].push_back(f(r+i+n,j+k));
        if(k==n-1)break;
      }
    }
  }
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      if(j%n!=n-1 && j+1<c) {
        adj[f(10*r+i,j)].push_back(f(10*r+i,j+1));
        adj[f(11*r+i,j+1)].push_back(f(11*r+i,j));
        adj[f(14*r+i,j)].push_back(f(14*r+i,j+1));
        adj[f(15*r+i,j+1)].push_back(f(15*r+i,j));
      }
      if(i%n!=n-1 && i+1<r){
        adj[f(12*r+i,j)].push_back(f(12*r+i+1,j));
        adj[f(13*r+i+1,j)].push_back(f(13*r+i,j));
        adj[f(16*r+i,j)].push_back(f(16*r+i+1,j));
        adj[f(17*r+i+1,j)].push_back(f(17*r+i,j));
      }
      if(a[i][j]=='.') {
        adj[f(14*r+i,j)].push_back(f(i,j));
        adj[f(15*r+i,j)].push_back(f(i,j));
        adj[f(16*r+i,j)].push_back(f(i,j));
        adj[f(17*r+i,j)].push_back(f(i,j));
        adj[f(i,j)].push_back(f(10*r+i,j));
        adj[f(i,j)].push_back(f(11*r+i,j));
        adj[f(i,j)].push_back(f(12*r+i,j));
        adj[f(i,j)].push_back(f(13*r+i,j));
      }
    }
  }
  for(int i=0;i+n-1<r;i++){
    for(int j=0;j+n-1<c;j++){
      if(j>0) {
        adj[f(r+i,j)].push_back(f(16*r+i,j-1));
        adj[f(r+i,j)].push_back(f(17*r+i+n-1,j-1));
        adj[f(12*r+i+n-1,j-1)].push_back(f(r+i,j));
        adj[f(13*r+i,j-1)].push_back(f(r+i,j));
      }
      if(j+n<c) {
        adj[f(r+i,j)].push_back(f(16*r+i,j+n));
        adj[f(r+i,j)].push_back(f(17*r+i+n-1,j+n));
        adj[f(12*r+i+n-1,j+n)].push_back(f(r+i,j));
        adj[f(13*r+i,j+n)].push_back(f(r+i,j));
      }
      if(i>0) {
        adj[f(r+i,j)].push_back(f(14*r+i-1,j));
        adj[f(r+i,j)].push_back(f(15*r+i-1,j+n-1));
        adj[f(10*r+i-1,j+n-1)].push_back(f(r+i,j));
        adj[f(11*r+i-1,j)].push_back(f(r+i,j));
      }
      if(i+n<r) {
        adj[f(r+i,j)].push_back(f(14*r+i+n,j));
        adj[f(r+i,j)].push_back(f(15*r+i+n,j+n-1));
        adj[f(10*r+i+n,j+n-1)].push_back(f(r+i,j));
        adj[f(11*r+i+n,j)].push_back(f(r+i,j));
      }
    }
  }
  
  queue<int> q[2];
  q[0].push(f(sr, sc));
  int tar = f(gr, gc);
  dist[f(sr, sc)]=0;
  //unordered_map<int, int> prv;
  while(q[0].size() || q[1].size()) {
    for(int i=0; i<2; i++) {
      if(q[i].size()) {
        int f = q[i].front(); q[i].pop();
        if(f == tar) {
          /*
          int bruh = f;
          stack<int>stk;
          while(bruh != sr*c+sc) {
            stk.push(bruh);
            bruh=prv[bruh];
          }
          stk.push(sr*c+sc);
          while(stk.size()){
            int x=stk.top();
            cout<<x/(r*c)<<' '<<(x%(r*c))/c<<' '<<(x%(r*c))%c<<'\n';
            stk.pop();
          }
          cout<<'\n';
          */
          cout << dist[f] << '\n'; return;
        }
        if(!vis[f]) {
          vis[f] = 1;
          for(int x: adj[f]) {
            if(!vis[x] && dist[x] > dist[f] + (x >= r*c && x < 2*r*c)) {
              dist[x] = dist[f] + (x >= r*c && x < 2*r*c);
             // prv[x] = f;
              if(x >= r*c && x < 2*r*c) q[1].push(x);
              else q[0].push(x);
            }
          }
        }
        break;
      }
    }
  }
  
  

}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// 勿忘初衷
/*
8 9 5
3 1
2 9
.#..###.#
##..#.##.
.###..#.#
#.....##.
..###....
#......##
.##.#.###
#.##.###.
*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 3 ms 3540 KB Output is correct
5 Correct 3 ms 3476 KB Output is correct
6 Correct 3 ms 3432 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 2 ms 3324 KB Output is correct
9 Correct 2 ms 3028 KB Output is correct
10 Correct 2 ms 3028 KB Output is correct
11 Correct 2 ms 3028 KB Output is correct
12 Correct 2 ms 3028 KB Output is correct
13 Correct 2 ms 3072 KB Output is correct
14 Correct 3 ms 3156 KB Output is correct
15 Correct 2 ms 3028 KB Output is correct
16 Correct 4 ms 3460 KB Output is correct
17 Correct 3 ms 3460 KB Output is correct
18 Correct 3 ms 3412 KB Output is correct
19 Runtime error 14 ms 10248 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3068 KB Output is correct
5 Correct 3 ms 3412 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3068 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 3 ms 3584 KB Output is correct
10 Correct 3 ms 3452 KB Output is correct
11 Correct 3 ms 3460 KB Output is correct
12 Correct 3 ms 3668 KB Output is correct
13 Correct 3 ms 3540 KB Output is correct
14 Correct 3 ms 3540 KB Output is correct
15 Correct 3 ms 3456 KB Output is correct
16 Correct 2 ms 3284 KB Output is correct
17 Correct 3 ms 3540 KB Output is correct
18 Correct 2 ms 3028 KB Output is correct
19 Correct 3 ms 3540 KB Output is correct
20 Correct 2 ms 3156 KB Output is correct
21 Correct 2 ms 3028 KB Output is correct
22 Correct 3 ms 3412 KB Output is correct
23 Correct 2 ms 3204 KB Output is correct
24 Correct 2 ms 3028 KB Output is correct
25 Correct 2 ms 3028 KB Output is correct
26 Correct 2 ms 3076 KB Output is correct
27 Correct 3 ms 3156 KB Output is correct
28 Correct 4 ms 3540 KB Output is correct
29 Correct 2 ms 3072 KB Output is correct
30 Correct 3 ms 3540 KB Output is correct
31 Correct 3 ms 3456 KB Output is correct
32 Correct 3 ms 3460 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3072 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3072 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 2 ms 3072 KB Output is correct
7 Correct 3 ms 3668 KB Output is correct
8 Correct 3 ms 3456 KB Output is correct
9 Correct 3 ms 3580 KB Output is correct
10 Correct 3 ms 3540 KB Output is correct
11 Correct 3 ms 3580 KB Output is correct
12 Correct 2 ms 3540 KB Output is correct
13 Correct 2 ms 3028 KB Output is correct
14 Correct 3 ms 3476 KB Output is correct
15 Correct 2 ms 3028 KB Output is correct
16 Correct 2 ms 3412 KB Output is correct
17 Correct 2 ms 3196 KB Output is correct
18 Correct 2 ms 3028 KB Output is correct
19 Correct 2 ms 3028 KB Output is correct
20 Correct 2 ms 3028 KB Output is correct
21 Correct 3 ms 3540 KB Output is correct
22 Correct 3 ms 3540 KB Output is correct
23 Correct 3 ms 3540 KB Output is correct
24 Correct 5 ms 4308 KB Output is correct
25 Runtime error 6 ms 6752 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3068 KB Output is correct
5 Correct 3 ms 3412 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3068 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 3 ms 3584 KB Output is correct
10 Correct 3 ms 3452 KB Output is correct
11 Correct 3 ms 3460 KB Output is correct
12 Correct 3 ms 3668 KB Output is correct
13 Correct 3 ms 3540 KB Output is correct
14 Correct 3 ms 3540 KB Output is correct
15 Correct 3 ms 3456 KB Output is correct
16 Correct 2 ms 3284 KB Output is correct
17 Correct 3 ms 3540 KB Output is correct
18 Correct 2 ms 3028 KB Output is correct
19 Correct 3 ms 3540 KB Output is correct
20 Correct 2 ms 3156 KB Output is correct
21 Correct 2 ms 3028 KB Output is correct
22 Correct 3 ms 3412 KB Output is correct
23 Correct 2 ms 3204 KB Output is correct
24 Correct 2 ms 3028 KB Output is correct
25 Correct 2 ms 3028 KB Output is correct
26 Correct 2 ms 3076 KB Output is correct
27 Correct 3 ms 3156 KB Output is correct
28 Correct 4 ms 3540 KB Output is correct
29 Correct 2 ms 3072 KB Output is correct
30 Correct 3 ms 3540 KB Output is correct
31 Correct 3 ms 3456 KB Output is correct
32 Correct 3 ms 3460 KB Output is correct
33 Runtime error 14 ms 10352 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3068 KB Output is correct
5 Correct 3 ms 3412 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3068 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 3 ms 3584 KB Output is correct
10 Correct 3 ms 3452 KB Output is correct
11 Correct 3 ms 3460 KB Output is correct
12 Correct 3 ms 3668 KB Output is correct
13 Correct 3 ms 3540 KB Output is correct
14 Correct 3 ms 3540 KB Output is correct
15 Correct 3 ms 3456 KB Output is correct
16 Correct 2 ms 3284 KB Output is correct
17 Correct 3 ms 3540 KB Output is correct
18 Correct 2 ms 3028 KB Output is correct
19 Correct 3 ms 3540 KB Output is correct
20 Correct 2 ms 3156 KB Output is correct
21 Correct 2 ms 3028 KB Output is correct
22 Correct 3 ms 3412 KB Output is correct
23 Correct 2 ms 3204 KB Output is correct
24 Correct 2 ms 3028 KB Output is correct
25 Correct 2 ms 3028 KB Output is correct
26 Correct 2 ms 3076 KB Output is correct
27 Correct 3 ms 3156 KB Output is correct
28 Correct 4 ms 3540 KB Output is correct
29 Correct 2 ms 3072 KB Output is correct
30 Correct 3 ms 3540 KB Output is correct
31 Correct 3 ms 3456 KB Output is correct
32 Correct 3 ms 3460 KB Output is correct
33 Runtime error 14 ms 10352 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 3 ms 3540 KB Output is correct
5 Correct 3 ms 3476 KB Output is correct
6 Correct 3 ms 3432 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 2 ms 3324 KB Output is correct
9 Correct 2 ms 3028 KB Output is correct
10 Correct 2 ms 3028 KB Output is correct
11 Correct 2 ms 3028 KB Output is correct
12 Correct 2 ms 3028 KB Output is correct
13 Correct 2 ms 3072 KB Output is correct
14 Correct 3 ms 3156 KB Output is correct
15 Correct 2 ms 3028 KB Output is correct
16 Correct 4 ms 3460 KB Output is correct
17 Correct 3 ms 3460 KB Output is correct
18 Correct 3 ms 3412 KB Output is correct
19 Runtime error 14 ms 10248 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 3 ms 3540 KB Output is correct
5 Correct 3 ms 3476 KB Output is correct
6 Correct 3 ms 3432 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 2 ms 3324 KB Output is correct
9 Correct 2 ms 3028 KB Output is correct
10 Correct 2 ms 3028 KB Output is correct
11 Correct 2 ms 3028 KB Output is correct
12 Correct 2 ms 3028 KB Output is correct
13 Correct 2 ms 3072 KB Output is correct
14 Correct 3 ms 3156 KB Output is correct
15 Correct 2 ms 3028 KB Output is correct
16 Correct 4 ms 3460 KB Output is correct
17 Correct 3 ms 3460 KB Output is correct
18 Correct 3 ms 3412 KB Output is correct
19 Runtime error 14 ms 10248 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 3 ms 3540 KB Output is correct
5 Correct 3 ms 3476 KB Output is correct
6 Correct 3 ms 3432 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 2 ms 3324 KB Output is correct
9 Correct 2 ms 3028 KB Output is correct
10 Correct 2 ms 3028 KB Output is correct
11 Correct 2 ms 3028 KB Output is correct
12 Correct 2 ms 3028 KB Output is correct
13 Correct 2 ms 3072 KB Output is correct
14 Correct 3 ms 3156 KB Output is correct
15 Correct 2 ms 3028 KB Output is correct
16 Correct 4 ms 3460 KB Output is correct
17 Correct 3 ms 3460 KB Output is correct
18 Correct 3 ms 3412 KB Output is correct
19 Runtime error 14 ms 10248 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -