Submission #293427

#	Time	Username	Problem	Language	Result	Execution time	Memory
293427		rama_pang	Furniture (JOI20_furniture)	C++14	100 / 100	938 ms	144356 KiB

furniture

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

int N, M;
int A[MAXN * MAXN];
int vis[MAXN * MAXN];

int adjptr[2][MAXN * MAXN];
array<pair<int, int>, 8> adj[2][MAXN * MAXN];

queue<pair<int, int>> q, qr;

void Bfs() {
  for (int r = 0; r < 2; r++) {
    while (!q.empty()) {
      int x = q.front().first;
      int y = q.front().second;
      q.pop();
      for (int id = 0; id < adjptr[r][x * MAXN + y]; id++) {
        auto i = adj[r][x * MAXN + y][id];
        int nx = i.first;
        int ny = i.second;
        if (vis[nx * MAXN + ny] & (1 << r)) {
          continue;
        }
        vis[nx * MAXN + ny] |= 1 << r;
        q.emplace(nx, ny);
      }
    }
    swap(q, qr);
  }
}

int AddEdge(int x, int y, int w, int z) {
  adj[0][x * MAXN + y][adjptr[0][x * MAXN + y]++] = {w, z};
  adj[1][w * MAXN + z][adjptr[1][w * MAXN + z]++] = {x, y};
  return 1;
}

int Query(int x, int y) {
  int meet = 0;
  meet += (vis[(x - 1) * MAXN + y] == 1) && (vis[x * MAXN + y] == 2);
  meet += (vis[x * MAXN + y + 1] == 1) && (vis[x * MAXN + y] == 2);
  meet += (vis[(x - 1) * MAXN + y + 1] == 1) && (vis[x * MAXN + y] == 2);

  if (meet != 0) return 0;

  AddEdge(x - 1, y, x, y);
  AddEdge(x, y + 1, x, y);
  AddEdge(x - 1, y + 1, x, y);

  if (vis[(x - 1) * MAXN + y] == 1) {
    q.emplace(x - 1, y);
  }
  if (vis[x * MAXN + y + 1] == 1) {
    q.emplace(x, y + 1);
  }
  if (vis[(x - 1) * MAXN + y + 1] == 1) {
    q.emplace(x - 1, y + 1);
  }
  if (vis[x * MAXN + y] == 2) {
    qr.emplace(x, y);
  }
  Bfs();
  return 1;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> M;
  vector<pair<int, int>> place;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      cin >> A[i * MAXN + j];
      if (A[i * MAXN + j] == 1) {
        A[i * MAXN + j] = 0;
        place.emplace_back(i, j);
      }
    }
  }
  for (int i = 0; i <= N + 1; i++) {
    for (int j = 0; j <= M + 1; j++) {
      int s = 0, t = 0;
      if (i == 0 || j == M + 1) {
        s = 1;
      }
      if (i == N + 1 || j == 0) {
        t = 1;
      }
      if (s + t == 1) {
        if (s) {
          q.emplace(i, j);
        } else if (t) {
          A[i * MAXN + j] = 1;
          qr.emplace(i, j);
          if (i - 1 >= 1) {
            AddEdge(i - 1, j, i, j);
          }
          if (j + 1 <= M) {
            AddEdge(i, j + 1, i, j);
          }
          if (i - 1 >= 1 && j + 1 <= M) {
            AddEdge(i - 1, j + 1, i, j);
          }
        }
      }
      if (1 <= i) {
        AddEdge(i, j, i - 1, j);
      }
      if (j <= M) {
        AddEdge(i, j, i, j + 1);
      }
    }
  }
  Bfs();
  for (auto i : place) {
    assert(Query(i.first, i.second) == 1);
  }
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    int x, y;
    cin >> x >> y;
    cout << Query(x, y) << "\n";
  }
  return 0;
}

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