oj.uz

Submission #316926

# Submission time Handle Problem Language Result Execution time Memory
316926 2020-10-28T15:35:11 Z manh9203 Furniture (JOI20_furniture) C++17
100 / 100
 452 ms 24016 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1005;

int n, m, q;
int a[N][N];
int dp[N][N][2], cntGood[2 * N];

bool check1(int x, int y) {
	if (dp[x][y][0] == 1 && dp[x - 1][y][0] == 0 && dp[x][y - 1][0] == 0) {
		return 1;
	} else {
		return 0;
	}
}
void dfs1(int x, int y) {
	if ((dp[x][y][0] & dp[x][y][1]) == 1) cntGood[x + y]--;
	dp[x][y][0] = 0;
	if (x + 1 <= n && check1(x + 1, y)) dfs1(x + 1, y);
	if (y + 1 <= m && check1(x, y + 1)) dfs1(x, y + 1);
}


bool check2(int x, int y) {
	if (dp[x][y][1] == 1 && dp[x + 1][y][1] == 0 && dp[x][y + 1][1] == 0) {
		return 1;
	} else {
		return 0;
	}
}
void dfs2(int x, int y) {
	if ((dp[x][y][0] & dp[x][y][1]) == 1) cntGood[x + y]--;
	dp[x][y][1] = 0;
	if (x - 1 >= 1 && check2(x - 1, y)) dfs2(x - 1, y);
	if (y - 1 >= 1 && check2(x, y - 1)) dfs2(x, y - 1);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

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

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (i == 1 && j == 1) {
				dp[i][j][0] = 1;
				continue;
			}
			if (a[i][j] == 0) dp[i][j][0] |= (dp[i - 1][j][0] | dp[i][j - 1][0]);
		}
	}
	for (int i = n; i >= 1; i--) {
		for (int j = m; j >= 1; j--) {
			if (i == n && j == m) {
				dp[i][j][1] = 1;
				continue;
			}
			if (a[i][j] == 0) dp[i][j][1] |= (dp[i + 1][j][1] | dp[i][j + 1][1]);
			if ((dp[i][j][0] & dp[i][j][1]) == 1) cntGood[i + j]++;
		}
	}

	cin >> q;
	while (q--) {
		int x, y; cin >> x >> y;
		if (a[x][y] == 1) {
			cout << 0 << "\n";
			continue;
		}
		if ((dp[x][y][0] & dp[x][y][1]) == 0) {
			a[x][y] = 1;
			cout << 1 << "\n";
			continue;
		}
		if (cntGood[x + y] == 1) {
			cout << 0 << "\n";
			continue;
		}
		a[x][y] = 1;
		dfs1(x, y); dfs2(x, y);
		cout << 1 << "\n";
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1024 KB Output is correct
2 Correct 2 ms 1280 KB Output is correct
3 Correct 3 ms 1152 KB Output is correct
4 Correct 4 ms 1280 KB Output is correct
5 Correct 4 ms 1280 KB Output is correct
6 Correct 4 ms 1280 KB Output is correct
7 Correct 4 ms 1408 KB Output is correct
8 Correct 4 ms 1280 KB Output is correct
9 Correct 4 ms 1280 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1024 KB Output is correct
2 Correct 2 ms 1280 KB Output is correct
3 Correct 3 ms 1152 KB Output is correct
4 Correct 4 ms 1280 KB Output is correct
5 Correct 4 ms 1280 KB Output is correct
6 Correct 4 ms 1280 KB Output is correct
7 Correct 4 ms 1408 KB Output is correct
8 Correct 4 ms 1280 KB Output is correct
9 Correct 4 ms 1280 KB Output is correct
10 Correct 13 ms 1408 KB Output is correct
11 Correct 3 ms 896 KB Output is correct
12 Correct 217 ms 16764 KB Output is correct
13 Correct 85 ms 13560 KB Output is correct
14 Correct 386 ms 20984 KB Output is correct
15 Correct 405 ms 21112 KB Output is correct
16 Correct 405 ms 22264 KB Output is correct
17 Correct 431 ms 23532 KB Output is correct
18 Correct 417 ms 22648 KB Output is correct
19 Correct 451 ms 23928 KB Output is correct
20 Correct 342 ms 24016 KB Output is correct
21 Correct 452 ms 23800 KB Output is correct