oj.uz

답안 #298917

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
298917 2020-09-14T10:20:06 Z toloraia Furniture (JOI20_furniture) C++14
0 / 100
 2 ms 384 KB 
#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);
      |                                   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -