oj.uz

Submission #419010

# Submission time Handle Problem Language Result Execution time Memory
419010 2021-06-06T10:22:51 Z maximath_1 Furniture (JOI20_furniture) C++11
100 / 100
 438 ms 15928 KB 
#include <iostream>
using namespace std;

const int MX = 1005;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int n, m, q, a[MX][MX], diag[MX + MX];

void dfs(int i, int j){
	a[i][j] = 1; diag[i + j] --;
	for(int ni, nj, d = 0; d < 4; d ++){
		ni = i + dx[d];
		nj = j + dy[d];
		if(!(ni == 1 && nj == 1) && !(ni == n && nj == m) && !a[ni][nj])
			if((a[ni - 1][nj] && a[ni][nj - 1]) || (a[ni + 1][nj] && a[ni][nj + 1]))
				dfs(ni, nj);
	}
}

int main(){
	cin.tie(0) -> sync_with_stdio(0);

	cin >> n >> m;
	for(int i = 0; i <= n + 1; i ++)
		for(int j = 0; j <= m + 1; j ++){
			if(i == 0 || j == 0 || i == n + 1 || j == m + 1) a[i][j] = 1;
			else diag[i + j] ++;
		}

	for(int x, i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++){
			cin >> x;
			if(x && !a[i][j]) dfs(i, j);
		}

	cin >> q;
	for(int x, y, i = 0; i < q; i ++){
		cin >> x >> y;
		if(a[x][y]) cout << "1\n";
		else if(diag[x + y] > 1 && !a[x][y]){
			dfs(x, y); cout << "1\n";
		}else cout << "0\n";
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 5 ms 792 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 4 ms 716 KB Output is correct
8 Correct 4 ms 716 KB Output is correct
9 Correct 4 ms 716 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 5 ms 792 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 4 ms 716 KB Output is correct
8 Correct 4 ms 716 KB Output is correct
9 Correct 4 ms 716 KB Output is correct
10 Correct 10 ms 976 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 161 ms 8880 KB Output is correct
13 Correct 75 ms 5828 KB Output is correct
14 Correct 282 ms 13436 KB Output is correct
15 Correct 363 ms 13740 KB Output is correct
16 Correct 328 ms 14848 KB Output is correct
17 Correct 313 ms 15480 KB Output is correct
18 Correct 299 ms 15028 KB Output is correct
19 Correct 354 ms 15792 KB Output is correct
20 Correct 298 ms 15888 KB Output is correct
21 Correct 438 ms 15928 KB Output is correct