oj.uz

Submission #424065

# Submission time Handle Problem Language Result Execution time Memory
424065 2021-06-11T16:00:14 Z DanerZein Furniture (JOI20_furniture) C++14
100 / 100
 350 ms 22760 KB 
#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]=1;
  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));
      }
    }
    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;
      if(path[x][y]==0) 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 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;
      }*/
  }
 
}
/*
5 7
0 0 0 0 0 0 0
1 0 1 1 1 1 0
1 0 0 0 0 1 0
1 0 1 1 0 1 0
0 0 0 0 0 0 0
1
5 5*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4684 KB Output is correct
2 Correct 4 ms 4884 KB Output is correct
3 Correct 5 ms 4812 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 6 ms 4940 KB Output is correct
7 Correct 6 ms 4940 KB Output is correct
8 Correct 6 ms 4940 KB Output is correct
9 Correct 6 ms 4940 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4684 KB Output is correct
2 Correct 4 ms 4884 KB Output is correct
3 Correct 5 ms 4812 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 6 ms 4940 KB Output is correct
7 Correct 6 ms 4940 KB Output is correct
8 Correct 6 ms 4940 KB Output is correct
9 Correct 6 ms 4940 KB Output is correct
10 Correct 12 ms 4864 KB Output is correct
11 Correct 5 ms 4556 KB Output is correct
12 Correct 195 ms 15624 KB Output is correct
13 Correct 85 ms 12632 KB Output is correct
14 Correct 304 ms 20160 KB Output is correct
15 Correct 317 ms 20392 KB Output is correct
16 Correct 325 ms 21444 KB Output is correct
17 Correct 348 ms 22228 KB Output is correct
18 Correct 339 ms 21700 KB Output is correct
19 Correct 348 ms 22624 KB Output is correct
20 Correct 339 ms 22760 KB Output is correct
21 Correct 350 ms 22676 KB Output is correct