oj.uz

Submission #292618

# Submission time Handle Problem Language Result Execution time Memory
292618 2020-09-07T10:57:46 Z kdh9949 Furniture (JOI20_furniture) C++17
100 / 100
 597 ms 22392 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define x first
#define y second
#define all(v) v.begin(),v.end()

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;

  vector<vint> c(n + 2, vint(m + 2));
  auto num = c;
  auto id = c;
  auto od = c;

  iota(all(num[0]), 1);
  for(int i = 1; i <= n + 1; i++) iota(all(num[i]), num[i - 1].back() + 1);
  for(int i = 0; i <= n + 1; i++) c[i][0] = c[i][m + 1] = 1;
  for(int i = 0; i <= m + 1; i++) c[0][i] = c[n + 1][i] = 1;
  c[0][0] = c[0][1] = c[1][0] = c[n + 1][m + 1] = c[n][m + 1] = c[n + 1][m] = 0;
  for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) {
    id[i][j] = 2 - c[i - 1][j] - c[i][j - 1];
    od[i][j] = 2 - c[i + 1][j] - c[i][j + 1];
  }

  vint p(num[n + 1][m + 1] + 1);
  iota(all(p), 0);
  function<int(int)> f = [&](int x) { return p[x] = (x == p[x] ? x : f(p[x])); };
  auto u = [&](int x, int y) { p[f(y)] = f(x); };
  for(int i = 0; i <= n; i++) {
    if(c[i][0] && c[i + 1][0]) u(num[i][0], num[i + 1][0]);
    if(c[i][m + 1] && c[i + 1][m + 1]) u(num[i][m + 1], num[i + 1][m + 1]);
  }
  for(int i = 0; i <= m; i++) {
    if(c[0][i] && c[0][i + 1]) u(num[0][i], num[0][i + 1]);
    if(c[n + 1][i] && c[n + 1][i + 1]) u(num[n + 1][i], num[n + 1][i + 1]);
  }

  queue<pii> q;
  const static int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
  auto block = [&](int x, int y) {
    c[x][y] = 1;
    q.emplace(x, y);
    while(!q.empty()) {
      pii t = q.front();
      q.pop();
      for(int i = 0; i < 4; i++) {
        int nx = t.x + dx[i], ny = t.y + dy[i];
        if(c[nx][ny]) u(num[t.x][t.y], num[nx][ny]);
        else {
          if(nx <= 0 || ny <= 0 || nx > n || ny > m) continue;
          if(dx[i] + dy[i] < 0 && !--od[nx][ny]) { c[nx][ny] = 1; q.emplace(nx, ny); }
          if(dx[i] + dy[i] > 0 && !--id[nx][ny]) { c[nx][ny] = 1; q.emplace(nx, ny); }
        }
      }
    }
  };

  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      int x;
      cin >> x;
      if(x && !c[i][j]) block(i, j);
    }
  }

  int qq;
  cin >> qq;
  for(int i = 0; i < qq; i++) {
    int x, y;
    cin >> x >> y;
    int LD = f(num[2][0]), UR = f(num[0][2]);

    if(c[x][y]) cout << "1\n";
    else if(
      (LD == f(num[x + 1][y]) || LD == f(num[x][y - 1]) || LD == f(num[x + 1][y - 1]))
      && (UR == f(num[x - 1][y]) || UR == f(num[x][y + 1]) || UR == f(num[x - 1][y + 1]))
    ) cout << "0\n";
    else {
      cout << "1\n";
      block(x, y);
    }
  }
  

  return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 20 ms 1664 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 420 ms 19704 KB Output is correct
13 Correct 134 ms 17664 KB Output is correct
14 Correct 557 ms 19768 KB Output is correct
15 Correct 555 ms 18808 KB Output is correct
16 Correct 469 ms 20472 KB Output is correct
17 Correct 500 ms 21752 KB Output is correct
18 Correct 597 ms 21112 KB Output is correct
19 Correct 595 ms 22216 KB Output is correct
20 Correct 494 ms 22392 KB Output is correct
21 Correct 586 ms 22264 KB Output is correct