제출 #299996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
299996		quocnguyen1012	Furniture (JOI20_furniture)	C++14	100 / 100	344 ms	6444 KiB

furniture

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1005;

int N, M;
int a[maxn][maxn], rem[2 * maxn];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

bool inside(int x, int y) {
  return 1 <= x && x <= N && 1 <= y && y <= M;
}


void band(int x, int y) {
  if (a[x][y] == 1)
    return;
  a[x][y] = 1;
  rem[x + y]--;
  for (int i = 0; i < 4; ++i) {
    int nx = x + dx[i], ny = y + dy[i];
    if (mp(nx, ny) == mp(1, 1) || mp(nx, ny) == mp(N, M)) continue;
    if (a[nx][ny]) continue;
    if ((a[nx - 1][ny] && a[nx][ny - 1]) || (a[nx + 1][ny] && a[nx][ny + 1])) {
      band(nx, ny);
    }
  }
}

signed main(void) {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N >> M;
  for (int i = 0; i <= N + 1; ++i) {
    a[i][0] = a[i][M + 1] = 1;
  }
  for (int j = 0; j <= M + 1; ++j) {
    a[0][j] = a[N + 1][j] = 1;
  }
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= M; ++j) {
      rem[i + j]++;
    }
  }
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= M; ++j) {
      int x; cin >> x;
      if (x) band(i, j);
    }
  }
  int Q; cin >> Q;
  while (Q--) {
    int x, y; cin >> x >> y;
    if (a[x][y]) cout << "1\n";
    else {
      if (rem[x + y] == 1) {
        cout << "0\n";
      } else {
        cout << "1\n";
        band(x, y);
      }
    }
  }
#ifdef LOCAL
  for (int i = 1; i <= N; ++i)
    for (int j = 1; j <= M; ++j)
      cerr << a[i][j] << " \n"[j == M];
#endif // LOCAL
}

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