oj.uz

Submission #293427

# Submission time Handle Problem Language Result Execution time Memory
293427 2020-09-08T05:03:56 Z rama_pang Furniture (JOI20_furniture) C++14
100 / 100
 938 ms 144356 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2944 KB Output is correct
2 Correct 4 ms 3584 KB Output is correct
3 Correct 5 ms 3712 KB Output is correct
4 Correct 6 ms 3840 KB Output is correct
5 Correct 7 ms 4096 KB Output is correct
6 Correct 7 ms 4096 KB Output is correct
7 Correct 7 ms 4096 KB Output is correct
8 Correct 7 ms 4096 KB Output is correct
9 Correct 7 ms 4096 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2944 KB Output is correct
2 Correct 4 ms 3584 KB Output is correct
3 Correct 5 ms 3712 KB Output is correct
4 Correct 6 ms 3840 KB Output is correct
5 Correct 7 ms 4096 KB Output is correct
6 Correct 7 ms 4096 KB Output is correct
7 Correct 7 ms 4096 KB Output is correct
8 Correct 7 ms 4096 KB Output is correct
9 Correct 7 ms 4096 KB Output is correct
10 Correct 25 ms 9160 KB Output is correct
11 Correct 6 ms 2944 KB Output is correct
12 Correct 409 ms 142440 KB Output is correct
13 Correct 187 ms 133988 KB Output is correct
14 Correct 774 ms 135652 KB Output is correct
15 Correct 773 ms 130424 KB Output is correct
16 Correct 865 ms 137464 KB Output is correct
17 Correct 938 ms 143800 KB Output is correct
18 Correct 863 ms 139208 KB Output is correct
19 Correct 904 ms 144356 KB Output is correct
20 Correct 658 ms 144248 KB Output is correct
21 Correct 914 ms 144324 KB Output is correct