Submission #512995

#	Time	Username	Problem	Language	Result	Execution time	Memory
512995		czhang2718	Furniture (JOI20_furniture)	C++17	0 / 100	2 ms	844 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 alive[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(alive[x][y]) continue;
    alive[x][y]=1;
    cnt[x+y]++;
    // cout << x<< " " <<  y << " alive\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});
  }
  assert(alive[0][0]);

  cin >> Q;
  while(Q--){
    int a, b; cin >> a >> b;
    a--; b--;
    if(alive[a][b] && cnt[a+b]==1){
      cout << "0\n"; continue;
    }
    cout << "1\n";
    if(!alive[a+b]) continue;
    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(!alive[x][y]) continue;
      alive[x][y]=0;
      cnt[x+y]--;
      if(in_range(x-1, y) && alive[x-1][y] && (!in_range(x-1, y+1) || !alive[x-1][y+1])) q.push({x-1, y});
      if(in_range(x, y-1) && alive[x][y-1] && (!in_range(x+1, y-1) || !alive[x+1][y-1])) q.push({x, y-1});
    }
    c[a][b]=1;
  }
}
// do you hate the song on the radio?

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