제출 #488531

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
488531		AdamGS	Furniture (JOI20_furniture)	C++14	100 / 100	338 ms	23728 KiB

furniture

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e3+7;
int T[LIM][LIM], A[LIM][LIM], B[LIM][LIM], sum[2*LIM], n, m;
void DFS(int a, int b) {
	A[a][b]=0;
	if(B[a][b]) --sum[a+b];
	if(b<m && !A[a-1][b+1] && A[a][b+1]) DFS(a, b+1);
	if(a<n && !A[a+1][b-1] && A[a+1][b]) DFS(a+1, b);
}
void DFS2(int a, int b) {
	B[a][b]=0;
	if(A[a][b]) --sum[a+b];
	if(a>1 && !B[a-1][b+1] && B[a-1][b]) DFS2(a-1, b);
	if(b>1 && !B[a+1][b-1] && B[a][b-1]) DFS2(a, b-1);
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	rep(i, n) rep(j, m) cin >> T[i+1][j+1];
	A[1][1]=1;
	rep(i, n) rep(j, m) {
		if((A[i+1][j] || A[i][j+1]) && !T[i+1][j+1]) A[i+1][j+1]=1;
	}
	B[n][m]=1;
	for(int i=n; i; --i) {
		for(int j=m; j; --j) {
			if((B[i+1][j] || B[i][j+1]) && !T[i][j]) B[i][j]=1;
			if(A[i][j] && B[i][j]) ++sum[i+j];
		}
	}
	int q;
	cin >> q;
	while(q--) {
		int a, b;
		cin >> a >> b;
		if(sum[a+b]>1 || !A[a][b] || !B[a][b]) {
			cout << 1 << '\n';
			if(A[a][b]) DFS(a, b);
			if(B[a][b]) DFS2(a, b);
		} else {
			cout << 0 << '\n';
		}
	}
}

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