oj.uz

Submission #361285

# Submission time Handle Problem Language Result Execution time Memory
361285 2021-01-29T07:23:58 Z 8e7 Furniture (JOI20_furniture) C++14
0 / 100
 4 ms 4588 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define maxn 1005
#define mp 1005*1005
#define ll long long
using namespace std;
int a[maxn][maxn], par[mp + 1];
int find(int x) {
	//cout << x << endl;
	return x == par[x] ? x : par[x] = find(par[x]);
}
void Union(int x, int y) {
	x = find(x), y = find(y);
	if (x > y) swap(x, y);
	par[find(x)] = find(y);
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0;i < mp;i++) par[i] = -1;
	for (int i = 0;i < 4;i++) par[mp - i] = mp -i;
	for (int i = 0;i <= m;i++) par[i] = mp;
	for (int i = 0;i < (n + 1) * (m + 2);i+=m + 2) par[i] = mp - 1;
	for (int i = m + 1;i < (n + 2) * (m + 2);i += m + 2) par[i] = mp - 3;
	for (int i = (n + 1) * (m + 2) + 1;i <= (n + 2) * (m + 2);i++) par[i] = mp - 2;

	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= m;j++) {
			cin >> a[i][j];
			if (a[i][j] == 1) {
				par[i * (m + 2) + j] = i * (m + 2) + j;
				for (int x = -1;x <= 1;x++) {
					for (int y = -1;y <= 1;y++) {

						int nx = x + i, ny = y + j;
						//cout << nx << " " << ny << endl;
						int num = par[nx * (m + 2) + ny];
						//cout << num << endl;
						if (num != -1) {
							Union(i * (m + 2) + j, nx * (m + 2) + ny);
						}
					}
				}
			}
		}
	}
	/*
	for (int i = 0;i <= n + 1;i++) {
		for (int j= 0;j <= m + 1;j++) cout << par[i * (m + 2) + j] << " ";
		cout << endl;
	}
	*/
	int q;
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		bool b[4], c[4];
		for (int i = 0;i < 4;i++) b[i] = c[i] = false;
		for (int i = -1;i <= 1;i++) {
			for (int j = -1;j <= 1;j++) {
				int nx = x + i, ny = y + j, num = find(nx * (m + 2) + ny);
				if (num <= mp && num > mp - 4) c[mp - num] = 1;
			}
		}
		for (int i = 0;i < 4;i++) {
			//cout << mp - find(mp - i) << endl;
			b[i] = c[mp - find(mp - i)];
			//cout << c[i];
		}
		//cout << endl;
		if ((b[0] && b[2]) || (b[1] && b[3]) || (b[0] && b[1]) || (b[2] && b[3])) {
			cout << 0 << "\n";
		} else {
			cout << 1 << "\n";
			par[x * (m + 2) + y] = x * (m + 2) + y;
			for (int i = -1;i <= 1;i++) {
				for (int j = -1;j <= 1;j++) {
					int nx = x + i, ny = y + j, num = par[nx * (m + 2) + ny];
					if (num != -1) {
						Union(x * (m + 2) + y, num);
					}
				}
			}
		}
	}
}
/*
23 001 000 3
22 21 12

2 3
0 0 1
0 0 0
3
2 2
2 1
1 2


4 3
0 0 1
0 0 0
0 0 0
1 0 0
5
3 2
3 1
2 3
4 2
3 3
 */

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4588 KB Output isn't correct
2 Halted 0 ms 0 KB -