oj.uz

Submission #647727

# Submission time Handle Problem Language Result Execution time Memory
647727 2022-10-03T21:24:36 Z Markomafko972 Furniture (JOI20_furniture) C++14
100 / 100
 319 ms 15900 KB 
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

int n, m, p, t, r, s;
int a[1005][1005];
int kol[2005];
queue< pair<int, int> > q;

void bfs(int w) {
	
	while (!q.empty()) {
		int x = q.front().X;
		int y = q.front().Y;
		q.pop();
		
		if (x == 0 && y == 0) continue;
		if (x == n-1 && y == m-1) continue;
		if (a[x][y] == 0) continue;
		
		if ((x-1 >= 0 && a[x-1][y] == 1) || (y-1 >= 0 && a[x][y-1] == 1)) {
			if ((x+1 < n && a[x+1][y] == 1) || (y+1 < m && a[x][y+1] == 1)) continue;
		}
		
		a[x][y] = 0;
		kol[x+y]--;
		
		if (x+1 < n && w == 0) q.push({x+1, y});
		if (y+1 < m && w == 0) q.push({x, y+1});
		if (x-1 >= 0 && w == 1) q.push({x-1, y});
		if (y-1 >= 0 && w == 1) q.push({x, y-1});
	}
	
}

int query(int x, int y) {
	if (a[x][y] == 0) {
		return 1;
	}
	else {
		if (kol[x+y] == 1) {
			return 0;
		}
		else {
			a[x][y] = 0;
			kol[x+y]--;
			
			//postavit sve
			if (x+1 < n) q.push({x+1, y});
			if (y+1 < m) q.push({x, y+1});
			bfs(0);
			if (x-1 >= 0) q.push({x-1, y});
			if (y-1 >= 0) q.push({x, y-1});
			bfs(1);
			
			return 1;
		}
	}
}

int main () {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			a[i][j] = 1;
			kol[i+j]++;
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> t;	
			if (t == 1) query(i, j);
		}
	}
	
	cin >> p;
	for (int i = 0; i < p; i++) {
		cin >> r >> s;
		r--, s--;
		cout << query(r, s) << "\n";
	}

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 740 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 728 KB Output is correct
9 Correct 4 ms 820 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 740 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 728 KB Output is correct
9 Correct 4 ms 820 KB Output is correct
10 Correct 10 ms 852 KB Output is correct
11 Correct 4 ms 584 KB Output is correct
12 Correct 140 ms 8912 KB Output is correct
13 Correct 61 ms 5832 KB Output is correct
14 Correct 247 ms 13432 KB Output is correct
15 Correct 240 ms 13704 KB Output is correct
16 Correct 285 ms 14616 KB Output is correct
17 Correct 297 ms 15436 KB Output is correct
18 Correct 319 ms 15012 KB Output is correct
19 Correct 290 ms 15900 KB Output is correct
20 Correct 246 ms 15828 KB Output is correct
21 Correct 319 ms 15884 KB Output is correct