oj.uz

Submission #1035273

# Submission time Handle Problem Language Result Execution time Memory
1035273 2024-07-26T08:34:56 Z juicy Furniture (JOI20_furniture) C++17
100 / 100
 200 ms 16724 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e3 + 5;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int n, m, q;
int C[N][N], cnt[N * 2];
bool R[N][N];

bool inside(int i, int j) {
  return 1 <= i && i <= n && 1 <= j && j <= m;
}

bool get(int i, int j) {
  if (!inside(i, j)) {
    return 0;
  }
  return !R[i][j];
}

bool check(int i, int j) {
  if (i == 1 && j == 1) {
    return 1;
  }
  if (i == n && j == m) {
    return 1;
  }
  return (get(i - 1, j) || get(i, j - 1)) && (get(i, j + 1) || get(i + 1, j));
}

void bfs(int sr, int sc) {
  queue<array<int, 2>> q;
  R[sr][sc] = 1;
  q.push({sr, sc});
  --cnt[sr + sc];
  while (q.size()) {
    auto [u, v] = q.front(); q.pop();
    for (int dr = 0; dr < 4; ++dr) {
      int i = u + dx[dr], j = v + dy[dr];
      if (inside(i, j) && !R[i][j] && !check(i, j)) {
        R[i][j] = 1;
        --cnt[i + j];
        q.push({i, j});
      }
    }
  }
}

bool tog(int i, int j) {
  if (R[i][j]) {
    return 1;
  }
  if (cnt[i + j] == 1) {
    return 0;
  }
  bfs(i, j);
  return 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) {
      ++cnt[i + j];
      cin >> C[i][j];
    }
  }  
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (C[i][j]) {
        assert(tog(i, j));
      }
    }
  }
  cin >> q;
  while (q--) {
    int x, y; cin >> x >> y;
    cout << tog(x, y) << "\n";
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 7 ms 856 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 105 ms 9888 KB Output is correct
13 Correct 47 ms 6956 KB Output is correct
14 Correct 170 ms 14420 KB Output is correct
15 Correct 171 ms 14620 KB Output is correct
16 Correct 171 ms 15700 KB Output is correct
17 Correct 184 ms 16352 KB Output is correct
18 Correct 173 ms 15956 KB Output is correct
19 Correct 178 ms 16724 KB Output is correct
20 Correct 172 ms 16720 KB Output is correct
21 Correct 200 ms 16724 KB Output is correct