제출 #68878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68878		duality	Golf (JOI17_golf)	C++11	30 / 100	279 ms	94116 KiB

golf

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int A[100000],B[100000],C[100000],D[100000];
vi xLines,yLines;
int diff[2002][2002];
int dist[2002][2002][4];
deque<pair<pii,int> > Q;
int main() {
    int i;
    int N,S,T,U,V;
    scanf("%d %d %d %d %d",&S,&T,&U,&V,&N);
    xLines.pb(S),yLines.pb(T);
    xLines.pb(U),yLines.pb(V);
    for (i = 0; i < N; i++) {
        scanf("%d %d %d %d",&A[i],&B[i],&C[i],&D[i]);
        xLines.pb(A[i]),xLines.pb(B[i]);
        yLines.pb(C[i]),yLines.pb(D[i]);
    }
    sort(xLines.begin(),xLines.end());
    xLines.resize(unique(xLines.begin(),xLines.end())-xLines.begin());
    sort(yLines.begin(),yLines.end());
    yLines.resize(unique(yLines.begin(),yLines.end())-yLines.begin());

    int j;
    S = lower_bound(xLines.begin(),xLines.end(),S)-xLines.begin();
    T = lower_bound(yLines.begin(),yLines.end(),T)-yLines.begin();
    U = lower_bound(xLines.begin(),xLines.end(),U)-xLines.begin();
    V = lower_bound(yLines.begin(),yLines.end(),V)-yLines.begin();
    for (i = 0; i < N; i++) {
        A[i] = lower_bound(xLines.begin(),xLines.end(),A[i])-xLines.begin();
        B[i] = lower_bound(xLines.begin(),xLines.end(),B[i])-xLines.begin();
        C[i] = lower_bound(yLines.begin(),yLines.end(),C[i])-yLines.begin();
        D[i] = lower_bound(yLines.begin(),yLines.end(),D[i])-yLines.begin();
        diff[A[i]][C[i]]++,diff[A[i]][D[i]]--,diff[B[i]][C[i]]--,diff[B[i]][D[i]]++;
    }
    for (i = 0; i < xLines.size(); i++) {
        for (j = 0; j < yLines.size(); j++) {
            if (i > 0) diff[i][j] += diff[i-1][j];
            if (j > 0) diff[i][j] += diff[i][j-1];
            if ((i > 0) && (j > 0)) diff[i][j] -= diff[i-1][j-1];
        }
    }
    memset(dist,-1,sizeof(dist));
    for (i = 0; i < 4; i++) {
        dist[S][T][i] = 0;
        Q.pb(mp(mp(S,T),i));
    }
    while (!Q.empty()) {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int d = Q.front().second;
        Q.pop_front();

        if ((x == U) && (y == V)) {
            printf("%d\n",dist[x][y][d]+1);
            return 0;
        }
        for (i = 0; i < 4; i++) {
            int xx = x+dx[i];
            int yy = y+dy[i];
            int yes = 1;
            if ((i & 1) && diff[xx][min(y,yy)] && (xx > 0) && diff[xx-1][min(y,yy)]) yes = 0;
            if (!(i & 1) && diff[min(x,xx)][yy] && (yy > 0) && diff[min(x,xx)][yy-1]) yes = 0;
            if ((xx >= 0) && (xx < xLines.size()) && (yy >= 0) && (yy < yLines.size()) && yes) {
                if (i == d) {
                    if ((dist[xx][yy][i] == -1) || (dist[x][y][d] < dist[xx][yy][i])) {
                        dist[xx][yy][i] = dist[x][y][d];
                        Q.push_front(mp(mp(xx,yy),i));
                    }
                }
                else {
                    if ((dist[xx][yy][i] == -1) || (dist[x][y][d]+1 < dist[xx][yy][i])) {
                        dist[xx][yy][i] = dist[x][y][d]+1;
                        Q.pb(mp(mp(xx,yy),i));
                    }
                }
            }
        }
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

golf.cpp: In function 'int main()':
golf.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < xLines.size(); i++) {
                 ~~^~~~~~~~~~~~~~~
golf.cpp:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < yLines.size(); j++) {
                     ~~^~~~~~~~~~~~~~~
golf.cpp:73:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if ((xx >= 0) && (xx < xLines.size()) && (yy >= 0) && (yy < yLines.size()) && yes) {
                               ~~~^~~~~~~~~~~~~~~
golf.cpp:73:71: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if ((xx >= 0) && (xx < xLines.size()) && (yy >= 0) && (yy < yLines.size()) && yes) {
                                                                    ~~~^~~~~~~~~~~~~~~
golf.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d %d",&S,&T,&U,&V,&N);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d",&A[i],&B[i],&C[i],&D[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 70