#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define debug if(0)
const int N = 1e3 + 4;
int n, m;
bool good[N][N]; // 0 - not good, 1 - good [ good - is path from (1, 1) - (x, y) - (n, m)
int cnt[2*N+4]; // how many good cells with X+Y = i
bool nin(int x, int y) {
return x < 1 || x > n || y < 1 || y > m;
}
void dfs(int x, int y, bool up=0) {
if(nin(x, y)) return;
if(!good[x][y]) return;
if(up && (good[x+1][y] || good[x][y+1])) return;
if(!up && (good[x-1][y] || good[x][y-1])) return;
good[x][y] = 0; cnt[x+y]--;
debug cerr<<"{"<<x<<", "<<y<<"} is bad, so cnt["<<x+y<<"] = "<<cnt[x+y]<<"\n";
if(!up) {
dfs(x+1, y, up);
dfs(x, y+1, up);
}
else {
dfs(x-1, y, up);
dfs(x, y-1, up);
}
}
void upd(int x, int y, bool print) {
bool ok = 1;
if(good[x][y] && cnt[x+y] == 1) ok = 0;
if(ok && good[x][y]) {
good[x][y] = 0; cnt[x+y]--;
dfs(x+1, y);
dfs(x, y+1);
dfs(x-1, y, 1);
dfs(x, y-1, 1);
}
if(print) cout<<ok<<"\n";
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>m;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
good[i][j] = 1;
cnt[i+j]++;
}
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
int c; cin>>c;
if(c == 1) upd(i, j, 0);
}
}
int q; cin>>q;
while(q--) {
int x, y; cin>>x>>y;
upd(x, y, 1);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
3 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
468 KB |
Output is correct |
6 |
Correct |
3 ms |
468 KB |
Output is correct |
7 |
Correct |
4 ms |
468 KB |
Output is correct |
8 |
Correct |
4 ms |
512 KB |
Output is correct |
9 |
Correct |
5 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
3 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
468 KB |
Output is correct |
6 |
Correct |
3 ms |
468 KB |
Output is correct |
7 |
Correct |
4 ms |
468 KB |
Output is correct |
8 |
Correct |
4 ms |
512 KB |
Output is correct |
9 |
Correct |
5 ms |
468 KB |
Output is correct |
10 |
Correct |
9 ms |
596 KB |
Output is correct |
11 |
Correct |
2 ms |
340 KB |
Output is correct |
12 |
Correct |
138 ms |
5884 KB |
Output is correct |
13 |
Correct |
54 ms |
3020 KB |
Output is correct |
14 |
Correct |
235 ms |
10712 KB |
Output is correct |
15 |
Correct |
233 ms |
11012 KB |
Output is correct |
16 |
Correct |
253 ms |
11820 KB |
Output is correct |
17 |
Correct |
264 ms |
12424 KB |
Output is correct |
18 |
Correct |
332 ms |
12176 KB |
Output is correct |
19 |
Correct |
391 ms |
12816 KB |
Output is correct |
20 |
Correct |
319 ms |
12816 KB |
Output is correct |
21 |
Correct |
274 ms |
12848 KB |
Output is correct |