#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);
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
25180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
25180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
