제출 #411492

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
411492		nichke	Furniture (JOI20_furniture)	C++14	100 / 100	453 ms	19776 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int n, m, q;

int ar[1005][1005];

void push(stack<pair<int, int>>& st, int x, int y, vector<vector<int>>& val, vector<int>& cnt) {
	if (val[x][y] == 0) {
		val[x][y] = 1;
		--cnt[x + y];
		st.push({x, y});
	}
}

int change(int x, int y, vector<vector<int>>& val, vector<int>& cnt) {
	if (val[x][y] == 1) {
		return 1;
	}
	if (cnt[x + y] == 1) {
		return 0;
	}
	stack<pair<int, int>> st;
	push(st, x, y, val, cnt);
	while (!st.empty()) {
		int x = st.top().first;
		int y = st.top().second;
		st.pop();
		if (val[x - 1][y + 1] == 1) {
			push(st, x - 1, y, val, cnt);
			push(st, x, y + 1, val, cnt);
		}
		if (val[x + 1][y - 1] == 1) {
			push(st, x, y - 1, val, cnt);
			push(st, x + 1, y, val, cnt);
		}
	}
	return 1;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	vector<vector<int>> val(n + 2, vector<int>(m + 2, 1));
	vector<int> cnt(n + m + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			val[i][j] = 0;
			cnt[i + j]++;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> ar[i][j];
			if (ar[i][j] == 1) {
				change(i, j, val, cnt);
			}
		}
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		int x, y; cin >> x >> y;
		cout << change(x, y, val, cnt) << '\n';
	}
	return 0;
}

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