oj.uz

Submission #947851

# Submission time Handle Problem Language Result Execution time Memory
947851 2024-03-17T06:38:02 Z NeroZein Furniture (JOI20_furniture) C++17
100 / 100
 273 ms 33912 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 4 ms 19292 KB Output is correct
3 Correct 4 ms 19292 KB Output is correct
4 Correct 5 ms 19288 KB Output is correct
5 Correct 5 ms 19360 KB Output is correct
6 Correct 5 ms 19292 KB Output is correct
7 Correct 5 ms 19292 KB Output is correct
8 Correct 5 ms 19288 KB Output is correct
9 Correct 5 ms 19292 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 4 ms 19292 KB Output is correct
3 Correct 4 ms 19292 KB Output is correct
4 Correct 5 ms 19288 KB Output is correct
5 Correct 5 ms 19360 KB Output is correct
6 Correct 5 ms 19292 KB Output is correct
7 Correct 5 ms 19292 KB Output is correct
8 Correct 5 ms 19288 KB Output is correct
9 Correct 5 ms 19292 KB Output is correct
10 Correct 10 ms 17500 KB Output is correct
11 Correct 4 ms 16988 KB Output is correct
12 Correct 160 ms 26580 KB Output is correct
13 Correct 74 ms 23892 KB Output is correct
14 Correct 223 ms 31532 KB Output is correct
15 Correct 273 ms 31584 KB Output is correct
16 Correct 211 ms 32484 KB Output is correct
17 Correct 239 ms 33336 KB Output is correct
18 Correct 253 ms 33156 KB Output is correct
19 Correct 234 ms 33676 KB Output is correct
20 Correct 230 ms 33912 KB Output is correct
21 Correct 257 ms 33524 KB Output is correct