Submission #683926

#	Time	Username	Problem	Language	Result	Execution time	Memory
683926		abc864197532	Furniture (JOI20_furniture)	C++17	100 / 100	836 ms	66324 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(), x.end()

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m, q;
	cin >> n >> m;
	vector <vector <int>> a(n, vector <int> (m));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
		}
	}
	vector <vector <int>> dp1(n, vector <int> (m));
	vector <vector <int>> dp2(n, vector <int> (m));
	dp1[0][0] = 1, dp2.back().back() = 1;
	for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (dp1[i][j]) {
		if (i + 1 < n && !a[i + 1][j]) {
			dp1[i + 1][j] = true;
		}
		if (j + 1 < m && !a[i][j + 1]) {
			dp1[i][j + 1] = true;
		}
	}
	for (int i = n - 1; ~i; --i) for (int j = m - 1; ~j; --j) if (dp2[i][j]) {
		if (i && !a[i - 1][j]) {
			dp2[i - 1][j] = true;
		}
		if (j && !a[i][j - 1]) {
			dp2[i][j - 1] = true;
		}
	}
	vector <vector <int>> ok(n, vector <int>(m));
	vector <set <int>> cut(n + m);
	for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (dp1[i][j] && dp2[i][j]) {
		ok[i][j] = 1;
		cut[i + j].insert(i);
	}
	vector <int> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
	function <void(int, int)> dfs = [&](int x, int y) {
		ok[x][y] = 0;
		cut[x + y].erase(x);
		for (int i = 0; i < 4; ++i) {
			int nx = x + dx[i], ny = y + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && ok[nx][ny]) {
				int nnx = nx + dx[i ^ 3], nny = ny + dy[i ^ 3];
				if (nnx < 0 || nnx >= n || nny < 0 || nny >= m || !ok[nnx][nny]) {
					dfs(nx, ny);
				}
			}
		}
	};
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y, --x, --y;
		if (!ok[x][y]) {
			cout << "1\n";
			dfs(x, y);
		} else if (cut[x + y].size() == 1) {
			cout << "0\n";
		} else {
			cout << "1\n";
			dfs(x, y);
		}
	}
}

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