#include <bits/stdc++.h>
#include <unistd.h>
#define X first
#define Y second
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define vec vector
#define pri(i, poc, n, pov) for(int i = (int) poc; i < (int) n; i += (int) pov)
#define od(i, poc, n, pov) for(int i = (int) poc; i > (int) n; i -= (int) pov)
using namespace std;
const ll INF = 1e18;
const int LOG = 20;
const int OFF = (1 << LOG);
const int MOD = 1e9 + 7;
const int lx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int ly[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int N = 1010;
const int N2 = N + 10;
int abs(int x){
if(x < 0)
return -x;
return x;
}
int n, m;
int h[N2 * N2], hi[N2][N2];
bool ban[N2][N2], west[N2 * N2], nrth[N2 * N2], mat[N2][N2];
int Find(int x){
return (h[x] == x ? x : h[x] = Find(h[x]));
}
void Union(int x, int y){
x = Find(x);
y = Find(y);
h[x] = y;
}
void update(int x, int y){
if(ban[x][y])
return;
ban[x][y] = true;
int hx = Find(hi[x][y]);
if(!west[hx] && (x == n || y == 1))
west[hx] = true;
if(!nrth[hx] && (x == 1 || y == m))
nrth[hx] = true;
pri(i, 0, 8, 1){
if(!ban[x + lx[i]][y + ly[i]])
continue;
int h1 = Find(hi[x][y]);
int h2 = Find(hi[x + lx[i]][y + ly[i]]);
bool w = west[h1] | west[h2];
bool nr = nrth[h1] | nrth[h2];
Union(h2, h1);
h1 = Find(h1);
west[h1] = w;
nrth[h1] = nr;
}
if(ban[x - 1][y + 1]){
update(x, y + 1);
update(x - 1, y);
}
if(ban[x + 1][y - 1]){
update(x + 1, y);
update(x, y - 1);
}
}
bool can(int x, int y){
bool can_n = (x == 1 || y == m);
bool can_w = (x == n || y == 1);
pri(i, 0, 8, 1){
if(!ban[x + lx[i]][y + ly[i]])
continue;
int h1 = Find(hi[x + lx[i]][y + ly[i]]);
can_n |= nrth[h1];
can_w |= west[h1];
}
//cout << x << " " << y << " : " << can_w << " " << can_n << "\n";
return !(can_w & can_n);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
pri(i, 0, N2, 1){
pri(j, 0, N2, 1){
hi[i][j] = i * N2 + j;
h[i * N2 + j] = i * N2 + j;
}
}
cin >> n >> m;
ban[0][0] = true;
pri(i, 1, n + 1, 1){
ban[i][0] = true;
ban[i][m + 1] = true;
west[hi[i][0]] = true;
nrth[hi[i][m + 1]] = true;
pri(j, 1, m + 1, 1){
ban[0][j] = true;
ban[n + 1][j] = true;
nrth[hi[0][j]] = true;
west[hi[n + 1][j]] = true;
cin >> mat[i][j];
}
}
pri(i, 1, n + 1, 1){
pri(j, 1, m + 1, 1){
int x = mat[i][j];
if(x){
update(i, j);
}
}
}
int q;
cin >> q;
pri(i, 0, q, 1){
int x, y;
cin >> x >> y;
//pri(blax, 0, n + 2, 1) pri(blay, 0, m + 2, 1) cout << ban[blax][blay] << " \n"[blay == m + 1];
bool res = can(x, y);
cout << res << "\n";
if(res)
update(x, y);
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8660 KB |
Output is correct |
2 |
Correct |
8 ms |
8868 KB |
Output is correct |
3 |
Correct |
8 ms |
8836 KB |
Output is correct |
4 |
Correct |
9 ms |
8864 KB |
Output is correct |
5 |
Correct |
9 ms |
8916 KB |
Output is correct |
6 |
Correct |
10 ms |
8916 KB |
Output is correct |
7 |
Correct |
9 ms |
8992 KB |
Output is correct |
8 |
Correct |
9 ms |
8916 KB |
Output is correct |
9 |
Correct |
9 ms |
8916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8660 KB |
Output is correct |
2 |
Correct |
8 ms |
8868 KB |
Output is correct |
3 |
Correct |
8 ms |
8836 KB |
Output is correct |
4 |
Correct |
9 ms |
8864 KB |
Output is correct |
5 |
Correct |
9 ms |
8916 KB |
Output is correct |
6 |
Correct |
10 ms |
8916 KB |
Output is correct |
7 |
Correct |
9 ms |
8992 KB |
Output is correct |
8 |
Correct |
9 ms |
8916 KB |
Output is correct |
9 |
Correct |
9 ms |
8916 KB |
Output is correct |
10 |
Correct |
23 ms |
9036 KB |
Output is correct |
11 |
Correct |
8 ms |
8736 KB |
Output is correct |
12 |
Correct |
450 ms |
17220 KB |
Output is correct |
13 |
Correct |
108 ms |
14228 KB |
Output is correct |
14 |
Correct |
729 ms |
21772 KB |
Output is correct |
15 |
Correct |
769 ms |
22032 KB |
Output is correct |
16 |
Correct |
791 ms |
23008 KB |
Output is correct |
17 |
Correct |
855 ms |
23688 KB |
Output is correct |
18 |
Correct |
694 ms |
23204 KB |
Output is correct |
19 |
Correct |
739 ms |
24040 KB |
Output is correct |
20 |
Correct |
539 ms |
24072 KB |
Output is correct |
21 |
Correct |
686 ms |
24164 KB |
Output is correct |