oj.uz

Submission #992610

# Submission time Handle Problem Language Result Execution time Memory
992610 2024-06-04T19:54:25 Z vyshniak_n Furniture (JOI20_furniture) C++17
100 / 100
 1550 ms 15952 KB 
#include <iostream>
#include <stack>
#include <utility>
#include <vector>
 
int main() {
  int N, M;
  std::cin >> N >> M;
 
  std::vector<std::vector<int>> R(N + 2, std::vector<int>(M + 2, 1));
  std::vector<int> L(N + M + 1, 0);
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= M; ++j) {
      R[i][j] = 0;
      ++L[i + j];
    }
  }
 
  const auto set = [&](const int X, const int Y) -> int {
    if (R[X][Y] == 1) {
      return 1;
    }
    if (L[X + Y] == 1) {
      return 0;
    }
    std::stack<std::pair<int, int>> st;
    const auto push = [&](const int x, const int y) {
      if (R[x][y] == 0) {
        R[x][y] = 1;
        --L[x + y];
        st.emplace(x, y);
      }
    };
    push(X, Y);
    while (!st.empty()) {
      const int x = st.top().first;
      const int y = st.top().second;
      st.pop();
      if (R[x - 1][y + 1] == 1) {
        push(x - 1, y);
        push(x, y + 1);
      }
      if (R[x + 1][y - 1] == 1) {
        push(x, y - 1);
        push(x + 1, y);
      }
    }
    return 1;
  };
 
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= M; ++j) {
      int C;
      std::cin >> C;
      if (C == 1) {
        set(i, j);
      }
    }
  }
 
  int Q;
  std::cin >> Q;
  for (int k = 1; k <= Q; ++k) {
    int X, Y;
    std::cin >> X >> Y;
    std::cout << set(X, Y) << "\n";
  }
 
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 5 ms 444 KB Output is correct
3 Correct 6 ms 508 KB Output is correct
4 Correct 17 ms 344 KB Output is correct
5 Correct 12 ms 556 KB Output is correct
6 Correct 14 ms 584 KB Output is correct
7 Correct 14 ms 348 KB Output is correct
8 Correct 14 ms 344 KB Output is correct
9 Correct 14 ms 556 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 5 ms 444 KB Output is correct
3 Correct 6 ms 508 KB Output is correct
4 Correct 17 ms 344 KB Output is correct
5 Correct 12 ms 556 KB Output is correct
6 Correct 14 ms 584 KB Output is correct
7 Correct 14 ms 348 KB Output is correct
8 Correct 14 ms 344 KB Output is correct
9 Correct 14 ms 556 KB Output is correct
10 Correct 41 ms 860 KB Output is correct
11 Correct 9 ms 348 KB Output is correct
12 Correct 527 ms 8632 KB Output is correct
13 Correct 96 ms 5712 KB Output is correct
14 Correct 1213 ms 13420 KB Output is correct
15 Correct 1261 ms 13396 KB Output is correct
16 Correct 1378 ms 14644 KB Output is correct
17 Correct 1415 ms 15328 KB Output is correct
18 Correct 1434 ms 14896 KB Output is correct
19 Correct 1469 ms 15952 KB Output is correct
20 Correct 1435 ms 15952 KB Output is correct
21 Correct 1550 ms 15892 KB Output is correct