제출 #1156855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156855		fryingduc	Furniture (JOI20_furniture)	C++20	100 / 100	146 ms	3376 KiB

furniture

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e3 + 3;
const int Q = 1e6 + 6;
int n, m, q;
bool a[maxn][maxn];
bool vis[maxn][maxn];
int diag[maxn * 2];

void del(int x, int y) {
  queue<pair<int, int>> qu;
  qu.push(make_pair(x, y));
  a[x][y] = 1;
  --diag[x + y];
  while (!qu.empty()) {
    int x = qu.front().first, y = qu.front().second;
    qu.pop();
    int r = x + 1, c = y;
    if (r >= 1 and r <= n and !a[r][c]) {
      if (a[r - 1][c] and a[r][c - 1]) {
        a[r][c] = 1;
        --diag[r + c];
        qu.push(make_pair(r, c));
      }
    }
    r = x, c = y + 1;
    if (c >= 1 and c <= m and !a[r][c]) {
      if (a[r - 1][c] and a[r][c - 1]) {
        a[r][c] = 1;
        --diag[r + c];
        qu.push(make_pair(r, c));
      }
    }
  }
  qu.push(make_pair(x, y));
  while (!qu.empty()) {
    int x = qu.front().first, y = qu.front().second;
    qu.pop();
    int r = x - 1, c = y;
    if (r >= 1 and r <= n and !a[r][c]) {
      if (a[r + 1][c] and a[r][c + 1]) {
        a[r][c] = 1;
        --diag[r + c];
        qu.push(make_pair(r, c));
      }
    }
    r = x, c = y - 1;
    if (c >= 1 and c <= m and !a[r][c]) {
      if (a[r + 1][c] and a[r][c + 1]) {
        a[r][c] = 1;
        --diag[r + c];
        qu.push(make_pair(r, c));
      }
    }
  }
}

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    a[i][0] = a[i][m + 1] = 1;
  }
  for (int i = 1; i <= m; ++i) {
    a[0][i] = a[n + 1][i] = 1;
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      ++diag[i + j];
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      int t; cin >> t;
      if (t and !a[i][j]) {
        del(i, j);
      }
    }
  }
  cin >> q;
  while (q--) {
    int x, y; cin >> x >> y;
    if (a[x][y]) {
      cout << 1 << '\n';
    } else {
      if (diag[x + y] == 1) {
        cout << 0 << '\n';
      } else {
        cout << 1 << '\n';
        del(x, y);
      }
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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