// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
struct DSU {
vector<int> e; void init(int n) { e = vector<int>(n, -1); }
int get(int x) { return e[x] < 0 ? x : get(e[x]); }
int sameSet(int x, int y) { return get(x) == get(y); }
vector<array<int, 4>> R;
bool unite(int x, int y) {
x = get(x), y = get(y); if (x == y) {
R.push_back({-1, -1, -1, -1});
return 0;
}
if (e[x] > e[y]) swap(x, y);
R.push_back({x, e[x], y, e[y]});
e[x] += e[y]; e[y] = x; return 1;
}
void rollback() {
if (size(R) == 0) return;
auto [x, ex, y, ey] = R.back(); R.pop_back();
if (x == -1) return;
e[x] = ex, e[y] = ey;
}
};
int dx[8] = {1, 1, 1, 0, 0, -1, -1, -1};
int dy[8] = {1, 0, -1, 1, -1, 1, 0, -1};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, M; cin >> N >> M;
auto HSH = [&](int r, int c) { return r * M + c; };
vector<vector<int>> A(N, vector<int>(M));
DSU G, H, V; G.init(N * M + 5), H.init(N * M + 5), V.init(N * M + 5);
const int U = N * M, D = N * M + 1, L = N * M + 2, R = N * M + 3;
vector<set<int>> ROW(N), COL(M);
auto more = [&](const set<int> &S, int x) {
auto it = S.upper_bound(x);
if (it == end(S)) return -1;
return *it;
};
auto less = [&](const set<int> &S, int x) {
auto it = S.lower_bound(x);
if (it == begin(S)) return -1;
return *prev(it);
};
auto add = [&](int r, int c) -> array<int, 3> {
int g = 0, h = 0, v = 0;
if (!A[r][c]) return {0, 0, 0};
// cout << "ADD: " << r << " " << c << endl;
ROW[r].insert(c); COL[c].insert(r);
for(int dir = 0; dir < 8; dir++) {
int nr = dx[dir] + r, nc = dy[dir] + c;
if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
if (!A[nr][nc]) continue;
// cout << nr << " = " << nc << endl;
G.unite(HSH(r, c), HSH(nr, nc)); ++g;
H.unite(HSH(r, c), HSH(nr, nc)); ++h;
V.unite(HSH(r, c), HSH(nr, nc)); ++v;
}
if (c-1 >= 0) {
int rx = less(COL[c-1], r);
if (rx != -1) {
// cout << rx << " h " << c-1 << endl;
++h; H.unite(HSH(r, c), HSH(rx, c-1));
}
}
if (c+1 < M) {
int rx = more(COL[c+1], r);
if (rx != -1) {
// cout << rx << " h " << c+1 << endl;
++h; H.unite(HSH(r, c), HSH(rx, c+1));
}
}
if (r-1 >= 0) {
int cx = less(ROW[r-1], c);
if (cx != -1) {
// cout << r-1 << " v " << cx << endl;
++v; V.unite(HSH(r, c), HSH(r-1, cx));
}
}
if (r+1 < N) {
int cx = more(ROW[r+1], c);
if (cx != -1) {
// cout << r+1 << " v " << cx << endl;
++v; V.unite(HSH(r, c), HSH(r+1, cx));
}
}
if (r == 0) {
G.unite(HSH(r, c), U); ++g;
V.unite(HSH(r, c), U); ++v;
}
if (r == N-1) {
G.unite(HSH(r, c), D); ++g;
V.unite(HSH(r, c), D); ++v;
}
if (c == 0) {
G.unite(HSH(r, c), L); ++g;
H.unite(HSH(r, c), L); ++h;
}
if (c == M-1) {
G.unite(HSH(r, c), R); ++g;
H.unite(HSH(r, c), R); ++h;
}
return {g, h, v};
};
auto backup = [&](int g, int h, int v) {
for(int i = 0; i < g; i++) G.rollback();
for(int i = 0; i < h; i++) H.rollback();
for(int i = 0; i < v; i++) V.rollback();
};
for(int r = 0; r < N; r++) {
for(int c = 0; c < M; c++) {
cin >> A[r][c];
add(r, c);
}
}
auto check = [&]() {
// cout << H.sameSet(L, R) << V.sameSet(U, D) << G.sameSet(U, L) << G.sameSet(D, R) << endl;
return !(H.sameSet(L, R) || V.sameSet(U, D) || G.sameSet(U, L) || G.sameSet(D, R));
};
// cout << check()<< endl << endl;
int Q; cin >> Q;
for(int q = 0; q < Q; q++) {
int r, c; cin >> r >> c; --r, --c; A[r][c] = 1;
auto [g, h, v] = add(r, c);
int res = check();
cout << res << nl;
if (!res) {
A[r][c] = 0;
backup(g, h, v);
ROW[r].erase(c); COL[c].erase(r);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
