#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
mt19937 rnd(234);
const ll inf = 1e18;
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m, 0));
for (int i = 0; i < n; i += 1) {
for (int j = 0; j < m; j += 1) {
cin >> a[i][j];
}
}
vector<int> cnt_gd(n + m, 0);
for (int i = 0; i < n; i += 1) {
for (int j = 0; j < m; j += 1) {
if (a[i][j] == 0) {
cnt_gd[i + j] += 1;
}
}
}
int qrs;
cin >> qrs;
auto is_ok = [&](int i, int j) {
return 0 <= i && i < n && 0 <= j && j < m;
};
auto is_bad = [&](int nx, int ny) {
if (nx == 0 && ny == 0) {
return false;
}
if (nx == n - 1 && ny == m - 1) {
return false;
}
if (((!is_ok(nx - 1, ny) || a[nx - 1][ny]) && (!is_ok(nx, ny - 1) || a[nx][ny - 1])) ||
((!is_ok(nx + 1, ny) || a[nx + 1][ny]) && (!is_ok(nx, ny + 1) || a[nx][ny + 1]))) {
return true;
}
return false;
};
queue<pair<int, int>> q;
vector<pair<int, int>> go = {make_pair(1, 0), make_pair(-1, 0), make_pair(0, 1), make_pair(0, -1)};
for (int i = 0; i < n; i += 1) {
for (int j = 0; j < m; j += 1) {
if (a[i][j]) {
continue;
}
if (is_bad(i, j)) {
q.push(make_pair(i, j));
}
}
};
auto serve_queue = [&] {
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
cnt_gd[x + y] -= 1;
a[x][y] = 1;
for (auto [dx, dy] : go) {
int nx = x + dx;
int ny = y + dy;
if (!is_ok(nx, ny) || a[nx][ny]) {
continue;
}
if (is_bad(nx, ny)) {
q.push(make_pair(nx, ny));
}
}
}
};
serve_queue();
vector<int> rs(qrs);
for (int itr = 0; itr < qrs; itr += 1) {
int x, y;
cin >> x >> y;
--x;
--y;
if (a[x][y]) {
rs[itr] = 1;
continue;
}
if (cnt_gd[x + y] == 1) {
rs[itr] = 0;
continue;
}
rs[itr] = 1;
q.push(make_pair(x, y));
serve_queue();
}
for (int i = 0; i < qrs; i += 1) {
cout << rs[i] << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
3280 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
3280 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
