Submission #371448

#	Time	Username	Problem	Language	Result	Execution time	Memory
371448		S920105123	Furniture (JOI20_furniture)	C++14	0 / 100	11 ms	9964 KiB

furniture

#include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define all_of(v) (v).begin(), (v).end()
#define sort_unique(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define fi first
#define se second
const int MAXN = 1005;
const int MAXV = MAXN * MAXN;
//const LL INF = (LL) 1e9 + 8763;
//const LL MOD = (LL) 1e9 + 7;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m, C[MAXN][MAXN], vis[MAXN][MAXN];
int ind[MAXN][MAXN], outd[MAXN][MAXN], crit[MAXN][MAXN], diag[2*MAXN];

void dfs(int r, int c, int rev) {
	crit[r][c]++;
	vis[r][c] = 1;
	for (int i = 0; i < 2; i++) {
		int nr = r + (i == 0) * (rev ? -1 : 1), nc = c + (i == 1) * (rev ? -1 : 1);
		if (nr < n && nc < m && !C[nr][nc] && !vis[nr][nc]) {
			dfs(nr, nc, rev);
		}
	}
}

void remove(int r, int c) {
	crit[r][c] = 0;
	diag[r + c]--;
	for (int i = 0; i < 2; i++) {
		int nr = r + (i == 0), nc = c + (i == 1);
		if (nr < n && nc < m && crit[nr][nc]) {
			ind[nr][nc]--;
			if (ind[nr][nc] == 0) {
				remove(nr, nc);
			}
		}
	}
	for (int i = 0; i < 2; i++) {
		int pr = r - (i == 0), pc = c - (i == 1);
		if (pr >= 0 && pc >= 0 && crit[pr][pc]) {
			outd[pr][pc]--;
			if (outd[pr][pc] == 0) {
				remove(pr, pc);
			}
		}
	}
}

void solve() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> C[i][j];
		}
	}
	
	dfs(0, 0, 0);
	memset(vis, 0, sizeof(vis));
	dfs(n - 1, m - 1, 1);
	
	for (int r = 0; r < n; r++) {
		for (int c = 0; c < m; c++) {
			crit[r][c] = (crit[r][c] == 2);
			if (!crit[r][c]) continue;
			diag[r + c]++;
		}
	}
	for (int r = 0; r < n; r++) {
		for (int c = 0; c < m; c++) {
			if (!crit[r][c]) continue;
			for (int i = 0; i < 2; i++) {
				int nr = r + (i == 0), nc = c + (i == 1);
				if (nr < n && nc < m && crit[nr][nc]) {
					outd[r][c]++;
					ind[nr][nc]++;
				}
			}
		}
	}
	
	int qn;
	cin >> qn;
	for (int i = 0; i < qn; i++) {
		int x, y, ans = 0;
		cin >> x >> y;
		x--; y--;
		if (!crit[x][y]) {
			ans = 1;
		}
		else if (diag[x + y] > 1) {
			ans = 1;
			remove(x, y);
		}
		else {
			ans = 0;
		}
		cout << ans << '\n';
	}
}

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

	int tc = 1;
//	cin >> tc;
	for (int i = 1; i <= tc; i++) {
		solve();
	}

	return 0;
} 

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