#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
ll N,M;
cin>>N>>M;
ll cnt[N + M + 5];
memset(cnt,0,sizeof(cnt));
bool R[N][M];
vector<pair<pair<ll,ll>,bool> > updates;
for(ll i = 0;i < N;i++){
for(ll j = 0;j < M;j++){
cin>>R[i][j];
cnt[i + j]++;
if(R[i][j] == 1){
updates.push_back({{i,j},0});
}
}
}
ll Q;
cin>>Q;
int Hy[] = {0,-1};
int Wx[] = {-1,0};
for(ll i = 0;i < Q;i++){
ll A,B;
cin>>A>>B;
A--, B--;
updates.push_back({{A,B},1});
}
for(auto u : updates){
ll A = u.first.first;
ll B = u.first.second;
bool notoriginal = u.second;
if(R[A][B] == 1 || cnt[A + B] == 1){
if(notoriginal) cout<<0<<'\n';
}else{
queue<pair<ll,ll> > q;
R[A][B] = 1;
q.push({A,B});
bool ok = 1;
while(!q.empty()){
ll y = q.front().first;
ll x = q.front().second;
q.pop();
if(cnt[y + x] == 1){
ok = 0;
break; //all paths pass through (A,B) so cannot cover (A,B), can prove that leaving at least 1 path that pass through (A,B) will not affect future queries (so no need to undo)
}
cnt[y + x]--;
for(ll i = 0;i < 2;i++){
ll r = y + Hy[i];
ll c = x + Wx[i];
if(r < 0 || r >= N || c < 0 || c >= M || R[r][c] == 1){
continue;
}
bool blocked1 = 1; //no path from (r,c) to (N-1,M-1)
if(r < N - 1 && R[r + 1][c] == 0){
blocked1 = 0;
}
if(c < M - 1 && R[r][c + 1] == 0){
blocked1 = 0;
}
bool blocked2 = 1; //no path from (0,0) to (r,c)
if(r >= 1 && R[r - 1][c] == 0){
blocked2 = 0;
}
if(c >= 1 && R[r][c - 1] == 0){
blocked2 = 0;
}
if(blocked1 || blocked2){
R[r][c] = 1;
q.push({r,c});
}
}
}
if(ok){
if(notoriginal) cout<<1<<'\n';
}else{
if(notoriginal) cout<<0<<'\n';
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
