// 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 H = [&](int r, int c) { return r * M + c; };
vector<vector<int>> A(N, vector<int>(M));
DSU d; d.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) {
// cout << "MORE: ";
// for(auto y : S) cout << y << " ";
// cout << "X: " << x << endl;
auto it = S.upper_bound(x);
if (it == end(S)) return -1;
return *it;
};
auto less = [&](const set<int> &S, int x) {
// cout << "LESS: ";
// for(auto y : S) cout << y << " ";
// cout << "X: " << x << endl;
auto it = S.lower_bound(x);
if (it == begin(S)) return -1;
return *prev(it);
};
auto add = [&](int r, int c) {
int E = 0;
if (!A[r][c]) return E;
// cout << "ADD: " << endl;
// cout << 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;
d.unite(H(r, c), H(nr, nc)); ++E;
}
for(int cx = c; cx >= max(c-1, 0); cx--) {
int rx = less(COL[cx], r);
if (rx != -1) {
// cout << rx << " " << cx << endl;
++E; d.unite(H(r, c), H(rx, cx));
}
}
for(int cx = c; cx <= min(c+1, M-1); cx++) {
int rx = more(COL[cx], r);
if (rx != -1) {
// cout << rx << " " << cx << endl;
++E; d.unite(H(r, c), H(rx, cx));
}
}
for(int rx = r; rx >= max(r-1, 0); rx--) {
int cx = less(ROW[rx], c);
if (cx != -1) {
// cout << rx << " " << cx << endl;
++E; d.unite(H(r, c), H(rx, cx));
}
}
for(int rx = r; rx <= min(r+1, N-1); rx++) {
int cx = more(ROW[rx], c);
if (cx != -1) {
// cout << rx << " " << cx << endl;
++E; d.unite(H(r, c), H(rx, cx));
}
}
if (r == 0) { d.unite(H(r, c), U); ++E; }
if (r == N-1) { d.unite(H(r, c), D); ++E; }
if (c == 0) { d.unite(H(r, c), L); ++E; }
if (c == M-1) { d.unite(H(r, c), R); ++E; }
return E;
};
for(int r = 0; r < N; r++) {
for(int c = 0; c < M; c++) {
cin >> A[r][c];
add(r, c);
}
}
auto check = [&]() {
for(auto x : {L, D}) for(auto y : {U, R}) if (d.sameSet(x, y)) return 0;
return 1;
};
int Q; cin >> Q;
for(int q = 0; q < Q; q++) {
int r, c; cin >> r >> c; --r, --c; A[r][c] = 1;
int e = add(r, c);
int res = check();
// cout << "ANS: ";
cout << res << nl;
if (!res) {
A[r][c] = 0;
for(int _ = 0; _ < e; _++) d.rollback();
ROW[r].erase(c); COL[c].erase(r);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
