Submission #299994

#	Time	Username	Problem	Language	Result	Execution time	Memory
299994		quocnguyen1012	Furniture (JOI20_furniture)	C++14	100 / 100	329 ms	15864 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 gogo(int x, int y);

void go(int x, int y){
    if((x == 1 && y == 1) || (x == N && y == M)) return;
    if(a[x][y] == 1) return;
    if((a[x - 1][y] && a[x][y - 1]) || (a[x + 1][y] && a[x][y + 1])){
        gogo(x, y);
    }
}
void gogo(int x, int y){
    if(a[x][y] == 1) return;
    a[x][y] = 1;
    rem[x + y]--;
    go(x - 1, y);
    go(x, y - 1);
    go(x + 1, y);
    go(x, y + 1);
}

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][y] && 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) gogo(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";
        gogo(x, y);
      }
    }
  }
}

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