Submission #423979

#	Time	Username	Problem	Language	Result	Execution time	Memory
423979		DanerZein	Furniture (JOI20_furniture)	C++14	0 / 100	7 ms	4812 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
int ma[1010][1010];
int X[5]={0,1,0,-1};
int Y[5]={1,0,-1,0};
int n,m;
bool ar[1010][1010],ab[1010][1010],path[1010][1010];
int num[1000010];

void arriba(){
  ar[0][0]=1;
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
      if(ar[i][j]){
	for(int k=0;k<2;k++){
	  int xi,yi;
	  xi=i+X[k]; yi=j+Y[k];
	  if(xi<n && yi<m && !ma[xi][yi]) ar[xi][yi]=1;
	}
      }
}
void abajo(){
  ab[n-1][m-1]=2;
  for(int i=n-1;i>=0;i--)
    for(int j=m-1;j>=0;j--)
      if(ab[i][j]){
	for(int k=2;k<4;k++){
	  int xi,yi;
	  xi=i+X[k]; yi=j+Y[k];
	  if(xi>=0 && yi>=0 && !ma[xi][yi]) ab[xi][yi]=1;
	}
      }
}
bool check(int a,int b){
  if(!path[a][b]) return 1;
  if(num[a+b]>1){
    path[a][b]=0;
    num[a+b]--;
    queue<ii> q;
    for(int i=0;i<4;i++){
      int xi=a+X[i];
      int yi=b+Y[i];
      if(xi>=0 && xi<n && yi>=0 && yi<m && path[xi][yi]){
	q.push(ii(xi,yi));
	//cout<<xi<<" "<<yi<<endl;
      }
    }
    while(!q.empty()){
      int x=q.front().first;
      int y=q.front().second;
      q.pop();
      if((x==0 && y==0) || (x==n-1 && y==m-1)) continue;
      bool s1=0,s2=0;
      for(int i=0;i<2;i++){
	int xi,yi;
	xi=x+X[i]; yi=y+Y[i];
	if(xi<n && yi<m) s1|=path[xi][yi];
      }
      for(int i=2;i<4;i++){
	int xi,yi;
	xi=x+X[i]; yi=y+Y[i];
	if(xi>=0 && yi>=0) s2|=path[xi][yi];
      }
      //cout<<x<<" "<<y<<" "<<s1<<" "<<s2<<endl;
      if(!s1 || !s2){
	//cout<<x<<" "<<y<<endl;
	num[x+y]--;
	path[x][y]=0;
	for(int i=0;i<4;i++){
	  int xi,yi;
	  xi=x+X[i]; yi=y+Y[i];
	  if(xi>=0 && xi<n && yi>=0 && yi<m && path[xi][yi]) q.push(ii(xi,yi));
	}
      }
    }
    return 1;
  }
  else return 0;
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  memset(num,0,sizeof num);
  cin>>n>>m;
  for(int i=0;i<n;i++) for(int j=0;j<m;j++)  cin>>ma[i][j];
  arriba();
  abajo();
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      path[i][j]=(ar[i][j] && ab[i][j]);
    }
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(path[i][j]) num[i+j]++;
    }
  }
  int q;
  cin>>q;
  /*  for(int j=0;j<n;j++){
    for(int k=0;k<m;k++) cout<<path[j][k]<<" ";
    cout<<endl;
  }*/
  for(int i=0;i<q;i++){
    int a,b;
    cin>>a>>b;
    a--; b--;
    if(check(a,b)){
      cout<<"1\n";
    }
    else cout<<"0\n";
    /*for(int j=0;j<n;j++){
      for(int k=0;k<m;k++) cout<<path[j][k]<<" ";
      cout<<endl;
      }*/
  }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95