#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef uint64_t u64;
typedef int64_t i64;
int n, m;
struct DSU {
vi parent;
DSU(int n = 0) {
parent = vi(n, -1);
}
int get(int a) {
if (parent[a] == -1) return a;
return parent[a] = get(parent[a]);
}
void merge(int r1, int c1, int r2, int c2) {
merge(r1 * (m + 2) + c1, r2 * (m + 2) + c2);
}
void merge(int a, int b) {
a = get(a);
b = get(b);
if (a == b) return;
parent[a] = b;
}
};
bool isValid(int r, int c) {
return r >= 0 && r < n + 2 && c >= 0 && c < m + 2;
}
vvi isWall;
// void dfs(int r, int c) {
// if (!isValid(r, c) || isFurniture[r][c] || isWall[r][c] == 1) return;
// isWall[r][c]--;
// dfs(r + 1, c);
// dfs(r, c + 1);
// }
// void dfs2(int r, int c) {
// if (!isValid(r, c) || isFurniture[r][c] || isWall[r][c] == 0 || isWall[r][c] == 2) return;
// isWall[r][c]--;
// dfs2(r - 1, c);
// dfs2(r, c - 1);
// }
DSU dsu;
void dfsFill(int r, int c, int pr, int pc) {
if (!isValid(r, c) || !isWall[r - 1][c] || !isWall[r][c - 1]) return;
if (isWall[r][c]) {
dsu.merge(r, c, pr, pc);
return;
}
isWall[r][c] = true;
dsu.merge(r, c, pr, pc);
dfsFill(r + 1, c, r, c);
dfsFill(r, c + 1, r, c);
}
void dfsFill2(int r, int c, int pr, int pc) {
if (!isValid(r, c) || !isWall[r + 1][c] || !isWall[r][c + 1]) return;
if (isWall[r][c]) {
dsu.merge(r, c, pr, pc);
return;
}
isWall[r][c] = true;
dsu.merge(r, c, pr, pc);
dfsFill2(r - 1, c, r, c);
dfsFill2(r, c - 1, r, c);
}
signed main() {
cin >> n >> m;
isWall = vvi(n + 2, vi(m + 2, true));
isWall[0][0] = false;
isWall[0][1] = false;
isWall[1][1] = false;
isWall[n + 1][m + 1] = false;
isWall[n + 1][m] = false;
isWall[n][m] = false;
loop(i, n) {
loop(j, m) {
int x;
cin >> x;
isWall[i + 1][j + 1] = x;
}
}
dsu = DSU((n + 2) * (m + 2));
loop(i, n) {
loop(j, m) {
if (isWall[i + 1][j]) dfsFill(i + 1, j + 1, i + 1, j);
if (isWall[i][j + 1]) dfsFill(i + 1, j + 1, i, j + 1);
if (isWall[i + 2][j + 1]) dfsFill2(i + 1, j + 1, i + 2, j + 1);
if (isWall[i + 1][j + 2]) dfsFill2(i + 1, j + 1, i + 1, j + 2);
}
}
/*
2 5
0 0 0 0 0
0 0 0 0 0
2
2 4
1 2
*/
loop(i, n + 2) {
loop(j, m + 2) {
if (!isWall[i][j]) continue;
if (isValid(i - 1, j) && isWall[i - 1][j])
dsu.merge(i - 1, j, i, j);
if (isValid(i, j - 1) && isWall[i][j - 1])
dsu.merge(i, j - 1, i, j);
}
}
// loop(i, n + 2) {
// loop(j, m + 2) {
// cout << isWall[i][j] << " ";
// }
// cout << endl;
// }
// loop(i, n + 2) {
// loop(j, m + 2) {
// cout << dsu.get(i * (m + 2) + j) / 10 << dsu.get(i * (m + 2) + j) % 10 << ' ';
// }
// cout << endl;
// }
int q;
cin >> q;
loop(i, q) {
int x, y;
cin >> x >> y;
int topRight = dsu.get(m + 1);
int bottomLeft = dsu.get((n + 1) * (m + 2));
bool contains1 = dsu.get((x - 1) * (m + 2) + y) == topRight || dsu.get((x - 1) * (m + 2) + y + 1) == topRight || dsu.get(x * (m + 2) + y + 1) == topRight;
bool contains2 = dsu.get((x + 1) * (m + 2) + y) == bottomLeft || dsu.get((x + 1) * (m + 2) + y - 1) == bottomLeft || dsu.get(x * (m + 2) + y - 1) == bottomLeft;
if (isWall[x][y]) {
cout << '1' << endl;
}
else if (contains1 && contains2) {
cout << '0' << endl;
}
else {
cout << '1' << endl;
isWall[x][y] = true;
if (isWall[x + 1][y]) dsu.merge(x + 1, y, x, y);
if (isWall[x][y + 1]) dsu.merge(x, y + 1, x, y);
if (isWall[x + 1][y + 1]) dsu.merge(x + 1, y + 1, x, y);
if (isWall[x - 1][y]) dsu.merge(x - 1, y, x, y);
if (isWall[x][y - 1]) dsu.merge(x, y - 1, x, y);
if (isWall[x - 1][y - 1]) dsu.merge(x - 1, y - 1, x, y);
dfsFill(x + 1, y, x, y);
dfsFill(x, y + 1, x, y);
dfsFill2(x - 1, y, x, y);
dfsFill2(x, y - 1, x, y);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
