oj.uz

Submission #886341

# Submission time Handle Problem Language Result Execution time Memory
886341 2023-12-11T22:27:41 Z stefanneagu Furniture (JOI20_furniture) C++17
5 / 100
 147 ms 10688 KB 
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e3 + 5;
int jd[nmax][nmax], ss[nmax][nmax], diag[nmax], n, m;
bool f[nmax][nmax];
bool in(int a, int b) {
  if(a > n || b > m || min(a, b) < 0) {
    return 0;
  }
  return 1;
}
void dfs(int i, int j) {
  if(!in(i, j) || f[i][j] == 1) {
    return;
  }
  f[i][j] = 1;
  diag[i + j] --;
  if(--jd[i + 1][j] == 0) {
    dfs(i + 1, j);
  }
  if(--jd[i][j + 1] == 0) {
    dfs(i, j + 1);
  }
  if(--ss[i - 1][j] == 0) {
    dfs(i - 1, j);
  }
  if(--ss[i][j - 1] == 0) {
    dfs(i, j - 1);
  }
}
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; f[i][0] = f[i][m+1] = 1, i++) {
    for (int j = 1; j <= m; f[0][j] = f[n+1][j] = 1, j++) {
      diag[i+j]++;
      jd[i+1][j]++, jd[i][j+1]++;
      ss[i-1][j]++, ss[i][j-1]++;
    }
  }
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= m; j ++) {
      int a;
      cin >> a;
      if(a == 1) {
        dfs(i, j);
        //cout << i << " " << j << endl;
      }
    }
  }
  int q;
  cin >> q;
  for(int i = 1; i <= q; i ++) {
    int a, b;
    cin >> a >> b;
    if(f[a][b] == 1 || diag[a + b] != 1) {
      cout << "1\n";
      dfs(a, b);
    } else {
      cout << "0\n";
    }
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4680 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4680 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 7 ms 4700 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 96 ms 10096 KB Output is correct
13 Correct 41 ms 9224 KB Output is correct
14 Incorrect 147 ms 10688 KB Output isn't correct
15 Halted 0 ms 0 KB -