#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e3+7, INF=1e9+7;
int T[LIM][LIM], lst[LIM][LIM], uzyte[LIM][LIM], ans[LIM*LIM], n, m;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
rep(i, n) rep(j, m) {
T[i][j]=INF;
int a;
cin >> a;
if(a) T[i][j]=-1;
}
int q;
cin >> q;
rep(i, q) {
ans[i]=1;
int a, b;
cin >> a >> b; --a; --b;
T[a][b]=i;
}
priority_queue<pair<pair<pair<int,int>,int>,pair<int,int>>>pq;
pq.push({{{T[0][0], INF}, 0}, {0, 0}});
while(!pq.empty()) {
int x=pq.top().st.st.st, y=pq.top().st.nd, z=pq.top().st.st.nd;
int a=pq.top().nd.st, b=pq.top().nd.nd;
pq.pop();
if(lst[a][b]) continue;
lst[a][b]=y;
if(a<n-1) pq.push({{{T[a+1][b], min(z, T[a][b])}, 1}, {a+1, b}});
if(b<m-1) pq.push({{{T[a][b+1], min(z, T[a][b])}, 2}, {a, b+1}});
}
int a=n-1, b=m-1;
while(a || b) {
uzyte[a][b]=1;
if(lst[a][b]==1) --a;
else --b;
}
uzyte[0][0]=1;
rep(i, n) rep(j, m) if(uzyte[i][j]) {
if(T[i][j]<INF) ans[T[i][j]]=0;
}
rep(i, q) cout << ans[i] << '\n';
}
Compilation message
furniture.cpp: In function 'int main()':
furniture.cpp:32:7: warning: unused variable 'x' [-Wunused-variable]
32 | int x=pq.top().st.st.st, y=pq.top().st.nd, z=pq.top().st.st.nd;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1232 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
1484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1232 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
1484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
