Submission #729013

#	Time	Username	Problem	Language	Result	Execution time	Memory
729013		MilosMilutinovic	Maze (JOI23_ho_t3)	C++14	100 / 100	1136 ms	177740 KiB

Main

/**
 *    author:  wxhtzdy
 *    created: 12.02.2023 12:30:41
**/
#include <bits/stdc++.h>

using namespace std;

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

int n, m;

vector<vector<int>> fenw;

void modify(int i, int j, int v) {
  int x = i;
  while (x < n) {
    int y = j;
    while (y < m) {
      fenw[x][y] += v;
      y |= (y + 1);
    }
    x |= (x + 1);
  }
}

int get(int i, int j) {
  int v = 0;
  int x = i;
  while (x >= 0) {
    int y = j;
    while (y >= 0) {
      v += fenw[x][y];
      y = (y & (y + 1)) - 1;
    }
    x = (x & (x + 1)) - 1;
  }
  return v;
}        

int GetSum(int x1, int y1, int x2, int y2) {
  x1 = max(x1, 0);
  y1 = max(y1, 0);
  x2 = min(x2, n - 1);
  y2 = min(y2, m - 1);
  return get(x2, y2) - get(x2, y1 - 1) - get(x1 - 1, y2) + get(x1 - 1, y1 - 1);
}

bool Valid(int x, int y) {
  return 0 <= x && x < n && 0 <= y && y < m;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);                      
  int k;
  cin >> n >> m >> k;
  int sx, sy;
  cin >> sx >> sy;
  --sx; --sy;
  int fx, fy;
  cin >> fx >> fy;
  --fx; --fy;
  vector<string> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }                                         
  if (n > m) {
    swap(sx, sy);
    swap(fx, fy);
    vector<string> t(m, string(n, '.'));
    for (int j = 0; j < m; j++) {
      for (int i = 0; i < n; i++) {
        t[j][i] = s[i][j];
      }
    }
    swap(s, t);
    swap(n, m);
  }
  fenw.resize(n);
  for (int i = 0; i < n; i++) {
    fenw[i].resize(m);
    for (int j = 0; j < m; j++) {
      fenw[i][j] = 0;
    }
  }
  vector<pair<int, int>> que;
  que.emplace_back(sx, sy);
  vector<vector<bool>> was(n, vector<bool>(m));
  was[sx][sy] = true;
  vector<vector<bool>> rem(n, vector<bool>(m));
  vector<vector<bool>> qq(n, vector<bool>(m));
  vector<pair<int, int>> ff;
  vector<pair<int, int>> pp;
  vector<vector<pair<int, int>>> cl(n, vector<pair<int, int>>(m, {-1e9, -1e9}));
  for (int d = 0; d <= n * m; d++) {
    for (int b = 0; b < (int) que.size(); b++) {
      int x = que[b].first;
      int y = que[b].second;
      if (x == fx && y == fy) {
        printf("%d\n", d);
        return 0;
      }
      for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (Valid(nx, ny) && s[nx][ny] == '.' && !was[nx][ny]) {
          was[nx][ny] = true;
          que.emplace_back(nx, ny);    
        }
      }
    } 
    auto Update = [&](int x, int y, int px, int py) {
      int my = max(abs(x - cl[x][y].first), abs(y - cl[x][y].second)) + 1;
      int his = max(abs(x - px), abs(y - py)) + 1;
      if (his < my) {
        cl[x][y] = make_pair(px, py);
      }
    };
    for (auto& p : que) {
      int x = p.first;
      int y = p.second;
      for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (Valid(nx, ny) && !was[nx][ny] && !rem[nx][ny]) {
          rem[nx][ny] = true;
      //    cout << "updatovo" << " " << nx + 1 << " " << ny + 1 << '\n';
          Update(nx, ny, nx, ny);
          ff.emplace_back(nx, ny);
        }
      }
    }       
    for (int b = 0; b < (int) ff.size(); b++) {
      int x = ff[b].first;
      int y = ff[b].second;
      was[x][y] = true;
      //cells.emplace_back(p.first, p.second);
      for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (Valid(nx, ny) && !was[nx][ny]) {
          Update(nx, ny, cl[x][y].first, cl[x][y].second);
        }
        if (Valid(nx, ny) && !was[nx][ny] && max(abs(nx - cl[nx][ny].first), abs(ny - cl[nx][ny].second)) + 1 <= k) {
          was[nx][ny] = true;
          ff.emplace_back(nx, ny);  
        }
      }
    }
    for (auto& p : pp) {
      qq[p.first][p.second] = false;  
    }
    pp.clear();
    que = ff;
    ff.clear();
  }
  return 0;
}

• 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