#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
struct dsu{
int n;
vector<int> sz, p;
dsu(int nn){
n = nn;
sz.resize(n, 1);
p.resize(n);
for(int i = 0; i < n; i++) p[i] = i;
}
int get(int x){
if(p[x] != x) p[x] = get(p[x]);
return p[x];
}
void unite(int a, int b){
a = get(a), b = get(b);
if(a == b) return;
if(sz[b] > sz[a]) swap(a, b);
sz[a]+=sz[b];
sz[b] = 0;
p[b] = a;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
int** s = new int*[n];
for(int i = 0; i < n; i++){
s[i] = new int[m];
fill(s[i], s[i]+m, 0);
}
dsu ds(n*m+4);
auto add = [&](int x, int y){
auto _ds = ds;
if(x == 0) _ds.unite(n*m, x*m+y);
if(x == n-1) _ds.unite(n*m+1, x*m+y);
if(y == 0) _ds.unite(n*m+2, x*m+y);
if(y == m-1) _ds.unite(n*m+3, x*m+y);
for(int i = 0; i < y; i++){
if(s[x][i] == 1){
_ds.unite(x*m+i, x*n+y);
break;
}
}
if(x != 0){
for(int i = 0; i <= min(y+1, m-1); i++){
if(s[x-1][i] == 1){
_ds.unite((x-1)*m+i, x*m+y);
break;
}
}
}
if(x != n-1){
for(int i = max(0, y-1); i < m; i++){
if(s[x+1][i] == 1){
_ds.unite((x+1)*m+i, x*m+y);
break;
}
}
}
if(_ds.get(n*m+0) == _ds.get(n*m+1) || _ds.get(n*m+2) == _ds.get(n*m+3) ||
_ds.get(n*m+0) == _ds.get(n*m+2) || _ds.get(n*m+1) == _ds.get(n*m+3)){
return 0;
}
else{
s[x][y] = 1;
ds = _ds;
return 1;
}
};
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
int x; cin >> x;
if(x) add(i, j);
}
int q; cin >> q;
while(q--){
int a, b; cin >> a >> b; a--, b--;
cout << add(a, b) << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
