oj.uz

답안 #529079

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
529079 2022-02-22T05:35:38 Z d2k05 Furniture (JOI20_furniture) C++17
0 / 100
 1 ms 716 KB 
#include <bits/stdc++.h>

#define fastio ios_base :: sync_with_stdio(0), cin.tie(0);

using namespace std;
using ll = long long;

const int mxN = 1e3 + 5, mod = 1e9 + 7;

int n, m, a[mxN][mxN];
bool dp[mxN][mxN], s[mxN][mxN];

bool can(int i, int j) {
	return (dp[i][j] & s[i][j]);
}

int main() {
	fastio;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) cin >> a[i][j];	
	}
	dp[1][1] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1 + (i == 1); j <= m; ++j) {
			if (a[i][j]) continue;
			dp[i][j] = (dp[i - 1][j] | dp[i][j - 1]);	
		} 
	}
	s[n][m] = 1;
	for (int i = n; i > 0; i--) {
		for (int j = m - (i == n); j > 0; j--) {
			if (a[i][j])
				continue;
			s[i][j] = (s[i + 1][j] | s[i][j + 1]);
		}
	}
 	int q;
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		if (can(x + 1, y - 1) || can(x - 1, y + 1)) {
			cout << "1\n";
			a[x][y] = 1;
			if (dp[x][y]) {
				queue <pair <int, int> > q;
				dp[x][y] = 0;
				q.push({x, y});
				vector <pair <int, int> > add;
				while (!q.empty()) {
					int i = q.front().first;
					int j = q.front().second;
					q.pop();
					if (!a[x][y] && (dp[i - 1][j] | dp[i][j - 1])) {
						add.push_back({i, j});
						continue;
					}
					if (i + 1 < n && dp[i + 1][j]) {
						dp[i + 1][j] = 0;
						q.push({i + 1, j});	
					}
					if (j + 1 < m && dp[i][j + 1]) {
						dp[i][j + 1] = 0;
						q.push({i, j + 1});
					}
				}
				for (auto [i, j] : add) {
					if ((dp[i - 1][j] | dp[i][j - 1]))
						dp[i][j] = 1;
				}
			}
			if (s[x][y]) {
				queue <pair <int, int> > q;
				s[x][y] = 0;
				q.push({x, y});
				vector <pair <int, int> > add;
				while (!q.empty()) {
					int i = q.front().first;
					int j = q.front().second;
					q.pop();
					if (!a[x][y] && (s[i + 1][j] | s[i][j + 1])) {
						add.push_back({i, j});
						continue;
					}
					if (i > 1 && s[i - 1][j]) {
						s[i - 1][j] = 0;
						q.push({i - 1, j});
					}
					if (j > 1 && s[i][j - 1]) {
						s[i][j - 1] = 0;
						q.push({i, j - 1});
					}
				}
				for (auto [i, j] : add) {
					if ((s[i + 1][j] | s[i][j + 1]))
						s[i][j] = 1;
				}
			}
		}
		else 
			cout << "0\n";
	}
	return 0;
}

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 716 KB Output isn't correct
2 Halted 0 ms 0 KB -