#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
//#define ll __int128
#define ll long long
#define int long long
#define LEFT(a) ((a)<<1)
#define RIGHT(a) (LEFT(a) + 1)
#define MID(a,b) ((a+b)>>1)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define y1 y122
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
/*
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/STACK: 20000000005")
*/
using namespace std;
const int N = 1005, M = 1000005;
int dr[4] = {0, 0, -1, 1};
int dc[4] = {-1, 1, 0, 0};
int n, m, q;
int x[M], y[M], ans[M];
int a[N][N];
int dp[N][N];
bool F[N][N];
pair < int, int > fr[N][N];
priority_queue < pair < int, pair < int, int > > > Q;
main()
{
freopen ("in.in", "r", stdin);freopen ("out.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++){
cin >> a[i][j];
a[i][j] ^= 1;
a[i][j] *= q+1;
dp[i][j] = 0;
}
cin >> q;
for (int i = 1; i <= q; i++){
cin >> x[i] >> y[i];
ans[i] = 1;
a[x[i]][y[i]] = i;
}
dp[1][1] = q+1;
Q.push ({q+1, {1, 1}});
while (Q.size() > 0){
int r = Q.top().S.F, c = Q.top().S.S;
Q.pop();
if (F[r][c])
continue;
F[r][c] = 1;
for (int i = 0; i < 4; i++){
int newr = r + dr[i], newc = c + dc[i];
if (newr < 1 || n < newr || newc < 1 || m < newc)
continue;
int mx = min (a[newr][newc], dp[r][c]);
if (mx > dp[newr][newc]){
dp[newr][newc] = mx;
fr[newr][newc] = {r, c};
Q.push ({mx, {newr, newc}});
}
}
}
int r = n, c = m;
while (r+c > 2){
if (a[r][c] <= q)
ans[a[r][c]] = 0;
int newr = fr[r][c].F, newc = fr[r][c].S;
r = newr;
c = newc;
}
for (int i = 1; i <= q; i++)
cout << ans[i] << endl;
}
Compilation message
furniture.cpp:19:1: warning: "/*" within comment [-Wcomment]
19 | /*
|
furniture.cpp:47:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
47 | main()
| ^
furniture.cpp: In function 'int main()':
furniture.cpp:49:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
49 | freopen ("in.in", "r", stdin);freopen ("out.out", "w", stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
furniture.cpp:49:43: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
49 | freopen ("in.in", "r", stdin);freopen ("out.out", "w", stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
