oj.uz

Submission #1031771

# Submission time Handle Problem Language Result Execution time Memory
1031771 2024-07-23T06:57:29 Z 정민찬(#10962) Furniture (JOI20_furniture) C++17
0 / 100
 12 ms 24924 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+1, i%m+1);
	}
	if (!l[x] && l[y]) {
		for (auto &i : g[x]) update_l(i/m+1, i%m+1);
	}
	if (r[x] && !r[y]) {
		for (auto &i : g[y]) update_r(i/m+1, i%m+1);
	}
	if (!r[x] && r[y]) {
		for (auto &i : g[x]) update_r(i/m+1, i%m+1);
	}
	if (g[x].size() < g[y].size()) swap(x, y);
	for (auto &i : g[y]) g[x].push_back(i);
	l[x] |= l[y];
	r[x] |= r[y];
	par[y] = x;
	//assert(!l[x] || !r[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];
int C[1010][1010];

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 (!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;
}


void Update(int x, int y) {
	assert(C[x][y] == 0);
	C[x][y] = 1;
	int p = Find((x-1) * m + y - 1);
	assert(p == (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;
	}
}

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;
	}
}

void cl_st() {
	while (!st.empty()) {
		int x = st.back().first;
		int y = st.back().second;
		st.pop_back();
		if (!C[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<=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();
			}
		}
	}
	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();
		}
	}
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24664 KB Output is correct
2 Incorrect 12 ms 24924 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24664 KB Output is correct
2 Incorrect 12 ms 24924 KB Output isn't correct
3 Halted 0 ms 0 KB -