#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif
using namespace std;
#define all(x) x.begin(), x.end()
const int S = 1000;
const int N = 1 << 20;
const int H = 5e7;
int val[H];
int *ptr[H];
int saved = 0;
void save(int &x) {
assert(saved < H);
val[saved] = x;
ptr[saved] = &x;
++saved;
}
void rollback(int savepoint) {
while (saved > savepoint) {
--saved;
*ptr[saved] = val[saved];
}
}
int n, m, q;
bool ok(int i, int j) {
return 0 <= i && i < n && 0 <= j && j < m;
}
int id(int i, int j) {
return S * i + j;
}
int dx[] = {-1, 0, +1, 0};
int dy[] = {0, -1, 0, +1};
vector<int> nei(int v) {
int i = v / S, j = v % S;
vector<int> ans;
for (int d = 0; d < 4; ++d) {
int x = i + dx[d], y = j + dy[d];
if (ok(x, y)) {
ans.push_back(id(x, y));
}
}
return ans;
}
int state[N];
int par[N];
int siz[N];
int dsu(int v) {
while (par[v] != v) {
v = par[v];
}
return v;
}
void merge(int x, int y) {
x = dsu(x);
y = dsu(y);
if (x == y) {
return;
}
if (siz[x] > siz[y]) {
swap(x, y);
}
save(par[x]);
save(siz[y]);
par[x] = y;
siz[y] += siz[x];
}
void on(int v) {
save(state[v]);
state[v] = 1;
for (int u : nei(v)) {
if (state[u]) {
merge(v, u);
}
}
}
bool is_connected() {
return dsu(id(0, 0)) == dsu(id(n - 1, m - 1));
}
vector<int> tree[2 * N];
void add_vertex(int l, int r, int v) {
for (l += N, r += N; l <= r; l /= 2, r /= 2) {
if (l % 2 == 1) {
tree[l++].push_back(v);
}
if (r % 2 == 0) {
tree[r--].push_back(v);
}
}
}
int query[N];
int first[N];
int answer[N];
void umin(int &a, int b) {
a = min(a, b);
}
void solve(int v) {
int savepoint = saved;
for (int u : tree[v]) {
on(u);
}
if (v >= N) {
if (!(answer[v - N] = is_connected())) {
int u = query[v - N];
add_vertex(v - N + 1, N - 1, u);
}
} else {
solve(v + v);
solve(v + v + 1);
}
rollback(savepoint);
}
signed main() {
#ifdef LC
assert(freopen("input.txt", "r", stdin));
#endif
ios::sync_with_stdio(0);
cin.tie(0);
iota(par, par + N, 0);
fill_n(siz, N, 1);
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
char c;
cin >> c;
int v = id(i, j);
if (c == '0') {
first[v] = N;
} else {
first[v] = -1;
}
}
}
cin >> q;
for (int i = 0; i < q; ++i) {
int x, y;
cin >> x >> y;
query[i] = id(x - 1, y - 1);
assert(first[query[i]] > i);
first[query[i]] = i;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int v = id(i, j);
//cerr << first[v] << " ";
add_vertex(0, first[v] - 1, v);
}
//cerr << endl;
}
solve(1);
for (int i = 0; i < q; ++i) {
cout << answer[i] << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
62712 KB |
Output is correct |
| 2 |
Incorrect |
65 ms |
63008 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
62712 KB |
Output is correct |
| 2 |
Incorrect |
65 ms |
63008 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
