oj.uz

답안 #488531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
488531 2021-11-19T13:28:48 Z AdamGS Furniture (JOI20_furniture) C++14
100 / 100
 338 ms 23728 KB 
#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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 2 ms 1356 KB Output is correct
4 Correct 3 ms 1484 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 4 ms 1524 KB Output is correct
7 Correct 3 ms 1612 KB Output is correct
8 Correct 3 ms 1612 KB Output is correct
9 Correct 3 ms 1608 KB Output is correct

Subtask #2
95.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 2 ms 1356 KB Output is correct
4 Correct 3 ms 1484 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 4 ms 1524 KB Output is correct
7 Correct 3 ms 1612 KB Output is correct
8 Correct 3 ms 1612 KB Output is correct
9 Correct 3 ms 1608 KB Output is correct
10 Correct 8 ms 1356 KB Output is correct
11 Correct 2 ms 972 KB Output is correct
12 Correct 163 ms 16624 KB Output is correct
13 Correct 52 ms 13420 KB Output is correct
14 Correct 279 ms 20916 KB Output is correct
15 Correct 279 ms 21116 KB Output is correct
16 Correct 333 ms 22336 KB Output is correct
17 Correct 326 ms 23380 KB Output is correct
18 Correct 291 ms 22596 KB Output is correct
19 Correct 338 ms 23728 KB Output is correct
20 Correct 255 ms 23700 KB Output is correct
21 Correct 303 ms 23708 KB Output is correct