#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 1e3 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, m, q;
char c[N][N];
int sz[N * N], rt[N * N];
int root(int x){
return (x == rt[x] ? x : rt[x] = root(rt[x]));
}
void merge(int x, int y){
x = root(x);
y = root(y);
if(x == y) return;
if(sz[x] < sz[y]) swap(x, y);
if(y > n * m) swap(x, y);
rt[y] = x;
sz[x] += sz[y];
}
int xx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int yy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
bool upd(int x, int y){
//cout << "BEGIN\n";
set<int> se;
for(int i = 0; i < 8; i++){
int tempx = x + xx[i], tempy = y + yy[i];
//cout << tempx << " " << tempy << "\n";
if(!c[tempx][tempy]) continue;
//cout << i << "\n";
if(root((tempx - 1) * m + tempy) > n * m) se.insert(root((tempx - 1) * m + tempy));
}
//cout << se.size() << "\n";
if(x == 1) se.insert(n * m + 1);
if(y == m) se.insert(n * m + 2);
if(x == n) se.insert(n * m + 3);
if(y == 1) se.insert(n * m + 4);
//cout << se.size() << "\n";
//for(auto it : se) cout << it << " ";
//cout << "\n";
//cout << "END1\n";
if(se.size() > 1){
if(se.size() > 2) return 0;
//cout << (*se.begin()) << " " << (*se.rbegin()) << "\n";
if((*se.begin()) == (n * m + 1) && (*se.rbegin()) == (n * m + 2)){}
else if((*se.begin()) == (n * m + 3) && (*se.rbegin()) == (n * m + 4)){}
else return 0;
}
//cout << "OK\n";
if(x == 1){
rt[y] = root(n * m + 1);
sz[root(n * m + 1)]++;
if(y == m) merge(n * m + 1, n * m + 2);
}
else if(x == n){
rt[(x - 1) * m + y] = root(n * m + 3);
sz[root(n * m + 3)]++;
if(y == 1) merge(n * m + 3, n * m + 4);
}
else if(y == 1){
rt[(x - 1) * m + y] = n * m + 4;
sz[n * m + 4]++;
}
else if(y == m){
rt[(x - 1) * m + y] = n * m + 2;
sz[n * m + 2]++;
}
else{
rt[(x - 1) * m + y] = (x - 1) * m + y;
sz[(x - 1) * m + y] = 1;
}
for(int i = 0; i < 8; i++){
int tempx = x + xx[i], tempy = y + yy[i];
if(!c[tempx][tempy]) continue;
merge((tempx - 1) * m + tempy, (x - 1) * m + y);
}
c[x][y] = 1;
return 1;
}
void process(){
cin >> n >> m;
for(int i = 1; i <= 4; i++){
rt[n * m + i] = n * m + i;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
int x;
cin >> x;
if(x) upd(i, j);
}
}
cin >> q;
while(q--){
int x, y;
cin >> x >> y;
cout << upd(x, y) << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
process();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
