oj.uz

Submission #1031751

# Submission time Handle Problem Language Result Execution time Memory
1031751 2024-07-23T06:33:48 Z 정민찬(#10962) Furniture (JOI20_furniture) C++17
0 / 100
 12 ms 25180 KB 
#include <bits/stdc++.h>

using namespace std;

vector<int> g[1000010];
int par[1000010];
int l[1000010], r[1000010];

int Find(int x) {
	if (par[x] == x) return x;
	return par[x] = Find(par[x]);
}

void update_l(int x, int y);
void update_r(int x, int y);

int n, m;

void Union(int x, int y) {
	x = Find(x);
	y = Find(y);
	if (x == y) return;
	if (l[x] && !l[y]) {
		for (auto &i : g[y]) update_l(i/m, i%m);
	}
	if (!l[x] && l[y]) {
		for (auto &i : g[x]) update_l(i/m, i%m);
	}
	if (r[x] && !r[y]) {
		for (auto &i : g[y]) update_r(i/m, i%m);
	}
	if (!r[x] && r[y]) {
		for (auto &i : g[x]) update_r(i/m, i%m);
	}
	if (g[x].size() < g[y].size()) swap(x, y);
	for (auto &i : g[y]) g[x].push_back(y);
	l[x] |= l[y];
	r[x] |= r[y];
	par[y] = x;
}

int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};

int le[1010], re[1010], ue[1010], de[1010];
int C[1010][1010];

int check_l(int x, int y) {
	if (le[x] == y || de[y] == x) return 1;
	if (le[x] > y && de[y] < x) return -1;
	return 0;
}

int check_r(int x, int y) {
	if (re[x] == y || ue[y] == x) return 1;
	if (re[x] < y && ue[y] > x) return -1;
	return 0;
}

bool Check(int x, int y) {
	if (C[x][y]) return true;
	bool lf = false, rf = false;
	if (x == n || y == 1) lf = true;
	if (x == 1 || y == m) rf = true;
	for (int k=0; k<8; k++) {
		int nx = x + dx[k];
		int ny = y + dy[k];
		if (check_l(nx, ny) == -1 || check_r(nx, ny) == -1) continue;
		if (!C[nx][ny]) continue;
		int p = Find((nx-1) * m + ny-1);
		if (l[p]) lf = true;
		if (r[p]) rf = true;
	}
	if (lf && rf) return false;
	return true;
}

int chk[1010][1010];

void Update(int x, int y) {
	assert(C[x][y] == 0);
	C[x][y] = 1;
	chk[x][y] = 1;
	int p = Find((x-1) * m + y - 1);
	if (x == n || y == 1) l[p] = 1, update_l(x, y);
	if (x == 1 || y == m) r[p] = 1, update_r(x, y);
	for (int k=0; k<8; k++) {
		int nx = x + dx[k];
		int ny = y + dy[k];
		if (C[nx][ny] == 1) {
			Union((nx-1) * m + ny-1, (x-1) * m + y-1);
		}
	}
}

vector<pair<int,int>> st;

void update_l(int x, int y) {
	for (int i=x; i<=n; i++) {
		if (le[i] >= y) break;
		for (int j=y; j>le[i]; j--) {
			if (!C[i][j]) {
				st.push_back({i, j});
			}
		}
		le[i] = y;
	}
	for (int j=y; j>=1; j--) {
		if (de[j] <= x) break;
		
		for (int i=x; i<de[j]; i++) {
			if (!C[i][j]) {
				st.push_back({i, j});
			}
		}
		de[j] = x;
	}
}

void update_r(int x, int y) {
	for (int i=x; i>=1; i--) {
		if (re[i] <= y) break;
		for (int j=y; j<re[i]; j++) {
			if (!C[i][j]) {
				st.push_back({i, j});
			}
		}
		re[i] = y;
	}
	for (int j=y; j<=m; j++) {
		if (ue[j] >= x) break;
		for (int i=x; i>ue[j]; i--) {
			if (!C[i][j]) {
				st.push_back({i, j});
			}
		}
		ue[j] = x;
	}
}

void cl_st() {
	while (!st.empty()) {
		int x = st.back().first;
		int y = st.back().second;
		st.pop_back();
		if (!chk[x][y]) Update(x, y);
	}
}

int T[1010][1010];

int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			int num = (i-1)*m + j-1;
			g[num].push_back(num);
			par[num] = num;
		}
	}
	for (int i=1; i<=m; i++) {
		ue[i] = 0;
		de[i] = n + 1;
	}
	for (int i=1; i<=n; i++) {
		le[i] = 0;
		re[i] = m + 1;
	}
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			cin >> T[i][j];
		}
	}
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			if (!C[i][j] && T[i][j]) {
				st.push_back({i, j});
				cl_st();
			}
		}
	}
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			cout << C[i][j] << ' ';
		}
		cout << '\n';
	}
	int q;
	cin >> q;
	while (q --) {
		int x, y;
		cin >> x >> y;
		if (C[x][y] == 1) {
			cout << "1\n";
			continue;
		}
		bool ret = Check(x, y);
		cout << ret << '\n';
		if (ret) {
			st.push_back({x, y});
			cl_st();
		}
	}
}

Compilation message

furniture.cpp: In function 'void Union(int, int)':
furniture.cpp:36:13: warning: unused variable 'i' [-Wunused-variable]
   36 |  for (auto &i : g[y]) g[x].push_back(y);
      |             ^

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 25180 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 12 ms 25180 KB Output isn't correct
2 Halted 0 ms 0 KB -