Submission #513001

#	Time	Username	Problem	Language	Result	Execution time	Memory
513001		czhang2718	Furniture (JOI20_furniture)	C++17	100 / 100	334 ms	17776 KiB

furniture

#include "bits/stdc++.h"
using namespace std;

#define f first
#define s second

const int N=1000;
int n, m, Q;
int c[N][N];
int cnt[2*N];
bool st[N][N], nd[N][N];

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;
  for(int i=0; i<n; i++) for(int j=0; j<m; j++){
    cin >> c[i][j];
  }
  auto in_range=[&](int x, int y)->bool{ return x>=0 && x<n && y>=0 && y<m; };

  queue<pair<int, int>> q;
  q.push({n-1, m-1});
  while(!q.empty()){
    auto p=q.front(); q.pop();
    int x=p.f, y=p.s;
    if(nd[x][y]) continue;
    nd[x][y]=1;
    if(in_range(x-1, y) && !c[x-1][y]) q.push({x-1, y});
    if(in_range(x, y-1) && !c[x][y-1]) q.push({x, y-1});
  }

  q.push({0, 0});
  while(!q.empty()){
    auto p=q.front(); q.pop();
    int x=p.f, y=p.s;
    if(st[x][y]) continue;
    st[x][y]=1;
    cnt[x+y]+=(st[x][y] && nd[x][y]);
    // cout << "cnt " << x+y << "++\n";
    if(in_range(x+1, y) && !c[x+1][y]) q.push({x+1, y});
    if(in_range(x, y+1) && !c[x][y+1]) q.push({x, y+1});
  }

  cin >> Q;
  while(Q--){
    int a, b; cin >> a >> b;
    a--; b--;
    // cout << a << " " << b << " " << st[a][b] << " " << nd[a][b] << "\n";
    if(st[a][b] && nd[a][b] && cnt[a+b]==1){
      cout << "0\n"; continue;
    }
    cout << "1\n";
    
    queue<pair<int, int>> q;
    q.push({a, b});
    while(!q.empty()){
      auto p=q.front(); q.pop();
      int x=p.f, y=p.s;
      if(!nd[x][y]) continue;
      nd[x][y]=0;
      // cout << "make bad " << x << " " << y << "\n";
      if(st[x][y]) cnt[x+y]--;
      if(in_range(x-1, y) && (!in_range(x-1, y+1) || !nd[x-1][y+1])) q.push({x-1, y});
      if(in_range(x, y-1) && (!in_range(x+1, y-1) || !nd[x+1][y-1])) q.push({x, y-1});
    }

    q.push({a, b});
    while(!q.empty()){
      auto p=q.front(); q.pop();
      int x=p.f, y=p.s;
      if(!st[x][y]) continue;
      st[x][y]=0;
      if(nd[x][y]) cnt[x+y]--;
      // cout << "make bad nd " << x << " " << y << "\n";
      if(in_range(x+1, y) && (!in_range(x+1, y-1) || !st[x+1][y-1])) q.push({x+1, y});
      if(in_range(x, y+1) && (!in_range(x-1, y+1) || !st[x-1][y+1])) q.push({x, y+1});
    }
  }
}
// do you hate the song on the radio?

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