oj.uz

Submission #513001

# Submission time Handle Problem Language Result Execution time Memory
513001 2022-01-17T00:34:39 Z czhang2718 Furniture (JOI20_furniture) C++17
100 / 100
 334 ms 17776 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 2 ms 840 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 4 ms 972 KB Output is correct
6 Correct 4 ms 944 KB Output is correct
7 Correct 4 ms 1100 KB Output is correct
8 Correct 3 ms 952 KB Output is correct
9 Correct 4 ms 972 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 2 ms 840 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 4 ms 972 KB Output is correct
6 Correct 4 ms 944 KB Output is correct
7 Correct 4 ms 1100 KB Output is correct
8 Correct 3 ms 952 KB Output is correct
9 Correct 4 ms 972 KB Output is correct
10 Correct 10 ms 972 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 176 ms 10624 KB Output is correct
13 Correct 75 ms 7720 KB Output is correct
14 Correct 284 ms 15248 KB Output is correct
15 Correct 290 ms 15484 KB Output is correct
16 Correct 308 ms 16484 KB Output is correct
17 Correct 334 ms 17440 KB Output is correct
18 Correct 321 ms 16904 KB Output is correct
19 Correct 320 ms 17728 KB Output is correct
20 Correct 318 ms 17776 KB Output is correct
21 Correct 331 ms 17700 KB Output is correct