Submission #294030

#	Time	Username	Problem	Language	Result	Execution time	Memory
294030		Mlxa	Furniture (JOI20_furniture)	C++14	5 / 100	5038 ms	3956 KiB

furniture

#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif

using namespace std;
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple

const int N = 1010;
int n, m, q;
bool lu[N][N];
bool rd[N][N];
bool dp[N][N];

bool rec(int a, int b, int c, int d) {
	for (int i = a; i <= b; ++i) {
		for (int j = c; j <= d; ++j) {
			if (dp[i][j]) {
				return true;
			}
		}
	}
	return false;
}
bool can_off(int i, int j) {
	if (!dp[i][j]) {
		return true;
	}
	return rec(1, i - 1, j + 1, m) || rec(i + 1, n, 1, j - 1);
}
void lu_dfs(int i, int j) {
	if (i < 1 || j < 1) {
		return;
	}
	if (dp[i][j] && !dp[i + 1][j] && !dp[i][j + 1]) {
		dp[i][j] = false;
		lu_dfs(i - 1, j);
		lu_dfs(i, j - 1);
	}
}
void rd_dfs(int i, int j) {
	if (i > n || j > m) {
		return;
	}
	if (dp[i][j] && !dp[i - 1][j] && !dp[i][j - 1]) {
		dp[i][j] = false;
		rd_dfs(i + 1, j);
		rd_dfs(i, j + 1);
	}
}
void print() {
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cout << dp[i][j] << " ";
		}
		cout << "\n";
	}
}

signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> dp[i][j];
			dp[i][j] ^= 1;
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			lu[i][j] = dp[i][j] && (lu[i - 1][j] || lu[i][j - 1]);
			lu[1][1] = true;
		}
	}
	for (int i = n; i >= 1; --i) {
		for (int j = m; j >= 1; --j) {
			rd[i][j] = dp[i][j] && (rd[i + 1][j] || rd[i][j + 1]);
			rd[n][m] = true;
			dp[i][j] = lu[i][j] & rd[i][j];
		}
	}
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		if (can_off(x, y)) {
			dp[x][y] = false;
			lu_dfs(x - 1, y);
			lu_dfs(x, y - 1);
			rd_dfs(x + 1, y);
			rd_dfs(x, y + 1);
			cout << "1\n";
		} else {
			cout << "0\n";
		}
	}
	return 0;
}

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