# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
516305 | qwerasdfzxcl | Furniture (JOI20_furniture) | C++14 | 606 ms | 23844 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[1010][1010], dp1[1010][1010], dp2[1010][1010], cnt[2020];
void debug(int n, int m){
printf("DEBUG\n");
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++) printf("%d ", dp1[i][j]);
printf("\n");
}
printf("\n");
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++) printf("%d ", dp2[i][j]);
printf("\n");
}
printf("\n");
}
int main(){
int n, m;
scanf("%d %d", &n, &m);
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++) scanf("%d", a[i]+j);
}
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
dp1[i][j] = dp1[i][j-1] | dp1[i-1][j];
if (a[i][j]) dp1[i][j] = 0;
dp1[1][1] = 1;
}
}
for (int i=n;i;i--){
for (int j=m;j;j--){
dp2[i][j] = dp2[i][j+1] | dp2[i+1][j];
if (a[i][j]) dp2[i][j] = 0;
dp2[n][m] = 1;
}
}
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++) if (dp1[i][j] && dp2[i][j]) cnt[i+j]++;
}
//debug(n, m);
int q;
scanf("%d", &q);
while(q--){
int x, y;
scanf("%d %d", &x, &y);
if (cnt[x+y]==1 && dp1[x][y] && dp2[x][y]) {printf("0\n"); continue;}
printf("1\n");
a[x][y] = 1;
queue<pair<int, int>> q;
q.emplace(x, y);
while(!q.empty()){
auto p = q.front(); q.pop();
if (!dp1[p.first][p.second]) continue;
if (!a[p.first][p.second] && (dp1[p.first-1][p.second] || dp1[p.first][p.second-1])) continue;
dp1[p.first][p.second] = 0;
if (dp2[p.first][p.second]) cnt[p.first+p.second]--;
if (p.first+1<=n) q.emplace(p.first+1, p.second);
if (p.second+1<=m) q.emplace(p.first, p.second+1);
}
q.emplace(x, y);
while(!q.empty()){
auto p = q.front(); q.pop();
if (!dp2[p.first][p.second]) continue;
if (!a[p.first][p.second] && (dp2[p.first+1][p.second] || dp2[p.first][p.second+1])) continue;
dp2[p.first][p.second] = 0;
if (dp1[p.first][p.second]) cnt[p.first+p.second]--;
if (p.first-1>0) q.emplace(p.first-1, p.second);
if (p.second-1>0) q.emplace(p.first, p.second-1);
}
//debug(n, m);
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |