/**
* Author : Nguyen Tuan Vu
* Created : 08.02.2023
**/
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1ll)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long Rand(long long l, long long r) {return l + rng() % (r - l + 1);}
void file(){
#define TASK "TASK"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
}
const int N = 1e3 + 5;
int n, m, a[N][N], nquery, cur, dd[N][N];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
file();
cin >> n >> m;
FOR(i, 1, n) FOR(j, 1, m) cin >> a[i][j];
const int Dx[] = {0, 1};
const int Dy[] = {1, 0};
int nquery; cin >> nquery;
while (nquery--) {
int u, v; cin >> u >> v;
if (a[u][v] == 1) cout << 0 << '\n';
else {
a[u][v] = 1;
++cur;
auto bfs = [&] (int u, int v) {
queue <pair <int, int>> q;
q.push({u, v});
dd[u][v] = cur;
while (q.size()) {
int u = q.front().first;
int v = q.front().second;
q.pop();
if (u == n && v == m) break;
REP(i, 2) {
int x = u + Dx[i];
int y = v + Dy[i];
if (x >= 1 && x <= n && y >= 1 && y <= m && dd[x][y] != cur && a[x][y] == 0) {
dd[x][y] = cur;
q.push({x, y});
}
}
}
};
bfs(1, 1);
if (dd[n][m] == cur) {
cout << 1 << '\n';
}
else {
a[u][v] = 0;
cout << 0 << '\n';
}
}
}
cerr << "Time elapsed: " << TIME << " s.\n";
return 0;
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
Compilation message
furniture.cpp: In function 'void file()':
furniture.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | freopen(TASK".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
furniture.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | freopen(TASK".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
852 KB |
Output is correct |
| 2 |
Correct |
28 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
115 ms |
1084 KB |
Output is correct |
| 4 |
Correct |
180 ms |
1080 KB |
Output is correct |
| 5 |
Correct |
200 ms |
1228 KB |
Output is correct |
| 6 |
Correct |
352 ms |
1200 KB |
Output is correct |
| 7 |
Correct |
116 ms |
1196 KB |
Output is correct |
| 8 |
Correct |
173 ms |
1336 KB |
Output is correct |
| 9 |
Correct |
485 ms |
1332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
852 KB |
Output is correct |
| 2 |
Correct |
28 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
115 ms |
1084 KB |
Output is correct |
| 4 |
Correct |
180 ms |
1080 KB |
Output is correct |
| 5 |
Correct |
200 ms |
1228 KB |
Output is correct |
| 6 |
Correct |
352 ms |
1200 KB |
Output is correct |
| 7 |
Correct |
116 ms |
1196 KB |
Output is correct |
| 8 |
Correct |
173 ms |
1336 KB |
Output is correct |
| 9 |
Correct |
485 ms |
1332 KB |
Output is correct |
| 10 |
Execution timed out |
5056 ms |
1208 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
