oj.uz

Submission #1031785

# Submission time Handle Problem Language Result Execution time Memory
1031785 2024-07-23T07:10:30 Z 정민찬(#10962) Furniture (JOI20_furniture) C++17
100 / 100
 344 ms 97132 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;
}

int dp[110][110];

bool Check2() {
    memset(dp, 0, sizeof(dp));
    dp[1][1] = 1;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            if (C[i][j]) continue;
            dp[i][j] |= dp[i-1][j];
            dp[i][j] |= dp[i][j-1];
        }
    }
    return dp[n][m];
}

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++) {
		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();
			}
		}
	}
	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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24672 KB Output is correct
2 Correct 11 ms 24860 KB Output is correct
3 Correct 12 ms 24924 KB Output is correct
4 Correct 12 ms 25180 KB Output is correct
5 Correct 13 ms 25180 KB Output is correct
6 Correct 19 ms 25180 KB Output is correct
7 Correct 12 ms 25176 KB Output is correct
8 Correct 12 ms 25180 KB Output is correct
9 Correct 12 ms 25364 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24672 KB Output is correct
2 Correct 11 ms 24860 KB Output is correct
3 Correct 12 ms 24924 KB Output is correct
4 Correct 12 ms 25180 KB Output is correct
5 Correct 13 ms 25180 KB Output is correct
6 Correct 19 ms 25180 KB Output is correct
7 Correct 12 ms 25176 KB Output is correct
8 Correct 12 ms 25180 KB Output is correct
9 Correct 12 ms 25364 KB Output is correct
10 Correct 30 ms 27052 KB Output is correct
11 Correct 13 ms 24924 KB Output is correct
12 Correct 283 ms 81064 KB Output is correct
13 Correct 115 ms 72456 KB Output is correct
14 Correct 344 ms 83480 KB Output is correct
15 Correct 324 ms 81496 KB Output is correct
16 Correct 242 ms 85228 KB Output is correct
17 Correct 276 ms 88496 KB Output is correct
18 Correct 307 ms 87704 KB Output is correct
19 Correct 293 ms 93332 KB Output is correct
20 Correct 291 ms 97132 KB Output is correct
21 Correct 285 ms 91956 KB Output is correct