# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
536353 | Monarchuwu | Furniture (JOI20_furniture) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define ff first
#define ss second
const int N = 1111;
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
int m, n;
int c[N][N], id[N][N];
int par[N * N];
int root(int u) { return par[u] < 0 ? u : par[u] = root(par[u]); }
void Union(int u, int v) {
if ((u = root(u)) == (v = root(v))) return;
if (par[u] > par[v]) swap(u, v);
par[u] += par[v];
par[v] = u;
}
void Join(int i, int j) {
for (int k = 0, x, y; k < 4; ++k) {
x = i + dx[k], y = j + dy[k];
if (c[x][y]) Union(id[i][j], id[x][y]);
}
}
queue<pii> q;
void bfs() {
while (!q.empty()) {
pii x = q.front(); q.pop();
if (c[x.ff][x.ss]) continue;
c[x.ff][x.ss] = 1;
Join(x.ff, x.ss);
if (c[x.ff - 1][x.ss + 1]) {
if (!c[x.ff][x.ss + 1])
q.emplace(x.ff, x.ss + 1);
if (!c[x.ff - 1][x.ss])
q.emplace(x.ff - 1, x.ss);
}
if (c[x.ff + 1][x.ss - 1]) {
if (!c[x.ff][x.ss - 1])
q.emplace(x.ff, x.ss - 1);
if (!c[x.ff + 1][x.ss])
q.emplace(x.ff + 1, x.ss);
}
}
}
void build() {
memset(par, -1, sizeof(par));
for (int i = 1; i <= m; ++i) {
c[i][0] = c[i + 1][0] = c[i - 1][n + 1] = c[i][n + 1] = 1;
Union(id[i][0], id[i + 1][0]);
Union(id[i - 1][n + 1], id[i][n + 1]);
}
for (int j = 1; j <= n; ++j) {
c[0][j] = c[0][j + 1] = c[m + 1][j - 1] = c[m + 1][j] = 1;
Union(id[0][j], id[0][j + 1]);
Union(id[m + 1][j - 1], id[m + 1][j]);
}
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j) {
cin >> c[i][j];
if (c[i][j]) q.emplace(i, j), c[i][j] = 0;
}
bfs();
}
bool check(int i, int j) {
return (root(id[m + 1][0]) == root(id[i + 1][j - 1]) && root(id[0][n + 1]) == root(id[i - 1][j + 1]));
}
int main() {
cin.tie(NULL)->sync_with_stdio(false);
cin >> m >> n;
for (int i = 0; i <= m + 1; ++i)
for (int j = 0; j <= n + 1; ++j) id[i][j] = i * (n + 2) + j;
build();
int qq, i, j; cin >> qq; while (qq--) {
cin >> i >> j;
if (!c[i][j]) {
if (check(i, j)) cout << "0\n";
else {
cout << "1\n";
q.emplace(i, j);
bfs();
}
}
else cout << "1\n";
}
}
/** /\_/\
* (= ._.)
* / >0 \>1
**/