#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=1007;
const ll LG=25;
ll n,m,k;
bool a[N][N];
bool b[N][N];
bool bl[N][N];
bool ur[N][N];
int sz[N*N];
int p[N*N];
bool urutox[N*N];
bool blutox[N*N];
int value(int i, int j){
return i*(m+1)+j;
}
void make_set(int v){
p[v]=v;
sz[v]=1;
}
int find_set(int v){
// cout<<v<<endl;
if(p[v]==v)return v;
return p[v]=find_set(p[v]);
}
void union_sets(int v, int u){
v=find_set(v);
u=find_set(u);
if(u!=v){
if(sz[v]<sz[u])swap(v,u);
sz[v]+=sz[u];
p[u]=v;
sz[u]=0;
urutox[v]|=urutox[u];
blutox[v]|=blutox[u];
}
}
void kpcruBL(int i, int j){
bl[i][j]=true;
a[i][j]=true;
for(int jj=1;jj<=j;jj++){
a[i][jj]=true;
bl[i][jj]=true;
}
for(int ii=i;ii<=n;ii++){
a[ii][j]=true;
bl[ii][j]=true;
}
}
void gnaBL(int i, int j){
kpcruBL(i,j);
for(int ii=i-1;ii<=i+1;ii++){
for(int jj=j-1;jj<=j+1;jj++){
if(a[ii][jj]&&!(ii==i&&jj==j)&&!bl[ii][jj]){
gnaBL(ii,jj);
}
}
}
}
void kpcruUR(int i, int j){
ur[i][j]=true;
a[i][j]=true;
for(int jj=j;jj<=m;jj++){
a[i][jj]=true;
ur[i][jj]=true;
}
for(int ii=1;ii<=i;ii++){
a[ii][j]=true;
ur[ii][j]=true;
}
}
void gnaUR(int i, int j){
kpcruUR(i,j);
for(int ii=i-1;ii<=i+1;ii++){
for(int jj=j-1;jj<=j+1;jj++){
if(a[ii][jj]&&!(ii==i&&jj==j)&&!ur[ii][jj]){
gnaUR(ii,jj);
}
}
}
}
int query(int i, int j){
bool urka=false;
bool blka=false;
for(int ii=i-1;ii<=i+1;ii++){
for(int jj=j-1;jj<=j+1;jj++){
if(a[ii][jj]&&!(ii==i&&jj==j)){
if(ur[ii][jj])urka=true;
if(bl[ii][jj])blka=true;
}
}
}
if(urka&&blka)return 0;
if(urka){
for(int ii=i-1;ii<=i+1;ii++){
for(int jj=j-1;jj<=j+1;jj++){
if(a[ii][jj]&&!(ii==i&&jj==j)&&!ur[ii][jj]){
if(urutox[find_set(value(ii,jj))])return false;
}
}
}
// cout<<"KPAV UR-in\n";
gnaUR(i,j);
// cout<<"TAZA UR:\n";
// for(int i=0;i<=n+1;i++){
// for(int j=0;j<=m+1;j++){
// cout<<ur[i][j]<<" ";
// }
// cout<<endl;
// }
// cout<<endl;
}
if(blka){
for(int ii=i-1;ii<=i+1;ii++){
for(int jj=j-1;jj<=j+1;jj++){
if(a[ii][jj]&&!(ii==i&&jj==j)&&!bl[ii][jj]){
if(blutox[find_set(value(ii,jj))])return false;
}
}
}
// cout<<"KPAV BL-in\n";
gnaBL(i,j);
// cout<<"TAZA BL:\n";
// for(int i=0;i<=n+1;i++){
// for(int j=0;j<=m+1;j++){
// cout<<bl[i][j]<<" ";
// }
// cout<<endl;
// }
// cout<<endl;
}
a[i][j]=true;
for(int ii=i-1;ii<=i+1;ii++){
for(int jj=j-1;jj<=j+1;jj++){
if(a[ii][jj]&&!(ii==i&&jj==j)){
union_sets(value(i,j),value(ii,jj));
}
}
}
return 1;
}
bool used[N][N];
void dfs(int i, int j, int pi, int pj){
used[i][j]=true;
union_sets(value(i,j),value(pi,pj));
for(int ii=i-1;ii<=i+1;ii++){
for(int jj=j-1;jj<=j+1;jj++){
if(a[ii][jj]&&!(ii==i&&jj==j)&&!used[ii][jj]){
dfs(ii,jj,i,j);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=0;i<=n+1;i++){
for(int j=0;j<=m+1;j++){
if(i==0||i==n+1||j==0||j==m+1){
a[i][j]=true;
if(i==0||j==m+1)ur[i][j]=true;
else bl[i][j]=true;
continue;
}
cin>>b[i][j];
}
}
for(int i=0;i<=n+1;i++){
for(int j=0;j<=m+1;j++){
make_set(value(i,j));
if(j==1){
urutox[find_set(value(i,j))]=true;
}
if(j==m){
blutox[find_set(value(i,j))]=true;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(b[i][j])query(i,j);
}
}
// cout<<"OK"<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!used[i][j]&&a[i][j]){
dfs(i,j,i,j);
}
}
}
cin>>k;
for(int c=0;c<k;c++){
int i,j;
cin>>i>>j;
cout<<query(i,j)<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
852 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
1108 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
852 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
1108 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
