Submission #292618

#	Time	Username	Problem	Language	Result	Execution time	Memory
292618		kdh9949	Furniture (JOI20_furniture)	C++17	100 / 100	597 ms	22392 KiB

furniture

#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 / 5
• Subtask 2: 95 / 95