Submission #298917

#	Time	Username	Problem	Language	Result	Execution time	Memory
298917		toloraia	Furniture (JOI20_furniture)	C++14	0 / 100	2 ms	384 KiB

furniture

#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 (stderr)

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);
      |                                   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95