제출 #947851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
947851		NeroZein	Furniture (JOI20_furniture)	C++17	100 / 100	273 ms	33912 KiB

furniture

#include "bits/stdc++.h"
using namespace std;
 
#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif
 
const int N = 1003;
 
int n, m;
bool c[N][N];
int id[3][N][N];
bool blocked[N][N];
int adjblocked[2][N][N];
vector<vector<int>> dx, dy;
pair<int, int> cell[3][N + N];
 
void dfs(int s, int x, int y) {
  //if (id[s][x][y] == -1) {
    //exit(0); 
  //}
  assert(id[s][x][y] != -1);
  for (int k = 0; k < 2; ++k) {
    int nx = x + dx[s][k], ny = y + dy[s][k];
    if (id[s][nx][ny] != -1) return; 
    if (nx > n || ny > m) {
      continue; 
    }
    if (!blocked[nx][ny]) {
      id[s][nx][ny] = id[s][x][y] + 1; 
      cell[s][id[s][nx][ny]] = {nx, ny}; 
      return dfs(s, nx, ny);
    }
  }
}

pair<int, int> bfs(int s, int sx, int sy) {
  if (blocked[sx][sy]) return {n + m, 0};
  queue<pair<int, int>> que; 
  que.emplace(sx, sy);
  int mn = n + m, mx = 0;
  while (!que.empty()) {
    auto [x, y] = que.front();
    que.pop();
    if (id[s][x][y] != -1) {
      mx = max(mx, id[s][x][y]);
      mn = min(mn, id[s][x][y]);
      id[s][x][y] = -1;
    }
    blocked[x][y] = true; 
    for (int k = 0; k < 4; ++k) {
      int nx = x + dx[2][k], ny = y + dy[2][k];
      if (nx <= 0 || ny <= 0 || nx > n || ny > m) continue; 
      adjblocked[(k / 2) ^ 1][nx][ny]++;
      if (adjblocked[(k / 2) ^ 1][nx][ny] == 2 && !blocked[nx][ny]) {
        que.emplace(nx, ny); 
      }
    }
  }
  return make_pair(mn, mx);
}

bool edit(int x, int y) {
  if (blocked[x][y]) return true; 
  if (id[0][x][y] != -1 && id[1][x][y] != -1) return false; 
  int s = (id[0][x][y] != -1 ? 0 : id[1][x][y] != -1 ? 1 : 2);
  auto [mn, mx] = bfs(s, x, y);
  if (s == 2) {
    return true;
  }
  auto [sx, sy] = cell[s][mn - 1];
  dfs(s, sx, sy);
  return true; 
}

void init() {
  dx.resize(3);
  dy.resize(3);
  dx[0] = {1, 0}; dy[0] = {0, 1};
  dx[1] = {0, 1}; dy[1] = {1, 0};
  dx[2] = {1, 0, -1, 0}; dy[2] = {0, 1, 0, -1};
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if ((i == 1 && j == 1) || (i == n && j == m)) continue; 
      for (int k = 0; k < 4; ++k) {
        int ni = i + dx[2][k], nj = j + dy[2][k];
        if (ni < 1 || ni > n || nj < 1 || nj > m) {
          adjblocked[k / 2][i][j]++;
        }
      }
    }
  }
  memset(id, -1, sizeof id);
  id[0][1][1] = id[1][1][1] = 1;
  id[0][n][m] = id[1][n][m] = n + m - 1;
  cell[0][1] = cell[1][1] = {1, 1};
  cell[0][n + m - 1] = cell[1][n + m - 1] = {n, m};
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (c[i][j] == 1) {
        bfs(2, i, j);
      }
    }
  }
  dfs(0, 1, 1);
  dfs(1, 1, 1);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cin >> c[i][j];
    }
  }
  init();
  int q;
  cin >> q; 
  while (q--) {
    int x, y;
    cin >> x >> y;
    bool ok = edit(x, y);
    cout << ok << '\n'; 
  }
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95