Submission #590516

# Submission time Handle Problem Language Result Execution time Memory
590516 2022-07-06T05:03:35 Z 반딧불(#8412) Golf (JOI17_golf) C++17
0 / 100
1 ms 580 KB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int xx[]={0, 1, 0, -1}, yy[]={1, 0, -1, 0};

struct dat{
    int x, y, d;
    dat(){}
    dat(int x, int y, int d): x(x), y(y), d(d){}
};

int n;
int H, W;
int sx, sy, ex, ey;
int ax[100002], ay[100002], bx[100002], by[100002];
bool board[4010][4010];
int able[4010][4010];
int dist[4010][4010][4];
deque<dat> que;

void renumber(){
    vector<int> xVec = {-1, sx, ex};
    vector<int> yVec = {-1, sy, ey};
    for(int i=1; i<=n; i++){
        xVec.push_back(ax[i]-1);
        xVec.push_back(ax[i]);
        xVec.push_back(bx[i]);
        xVec.push_back(bx[i]+1);
        yVec.push_back(ay[i]-1);
        yVec.push_back(ay[i]);
        yVec.push_back(by[i]);
        yVec.push_back(by[i]+1);
    }
    sort(xVec.begin(), xVec.end());
    xVec.erase(unique(xVec.begin(), xVec.end()), xVec.end());
    sort(yVec.begin(), yVec.end());
    yVec.erase(unique(yVec.begin(), yVec.end()), yVec.end());
    for(int i=1; i<=n; i++){
        ax[i] = lower_bound(xVec.begin(), xVec.end(), ax[i]) - xVec.begin();
        bx[i] = lower_bound(xVec.begin(), xVec.end(), bx[i]) - xVec.begin();
        ay[i] = lower_bound(yVec.begin(), yVec.end(), ay[i]) - yVec.begin();
        by[i] = lower_bound(yVec.begin(), yVec.end(), by[i]) - yVec.begin();
    }
    sx = lower_bound(xVec.begin(), xVec.end(), sx) - xVec.begin();
    ex = lower_bound(xVec.begin(), xVec.end(), ex) - xVec.begin();
    sy = lower_bound(yVec.begin(), yVec.end(), sy) - yVec.begin();
    ey = lower_bound(yVec.begin(), yVec.end(), ey) - yVec.begin();
    H = (int)xVec.size()-1;
    W = (int)yVec.size()-1;
}

void init(){
    for(int i=1; i<=H; i++) for(int j=1; j<=W; j++) for(int d=0; d<4; d++) dist[i][j][d] = 1e9;

    for(int i=1; i<=n; i++){
        for(int x=ax[i]; x<bx[i]; x++){
            for(int y=ay[i]; y<by[i]; y++){
                board[x][y] = 1;
            }
        }
    }

    for(int i=1; i<=H; i++){
        for(int j=1; j<=W; j++){
            if(j!=H && (!board[i][j] || !board[i-1][j])) able[i][j]|=1;
            if(i!=W && (!board[i][j] || !board[i][j-1])) able[i][j]|=2;
            if(j!=1 && (!board[i][j-1] || !board[i-1][j-1])) able[i][j]|=4;
            if(i!=1 && (!board[i-1][j] || !board[i-1][j-1])) able[i][j]|=8;
        }
    }

    for(int i=0; i<4; i++){
        que.push_back(dat(sx, sy, i));
        dist[sx][sy][i] = 1;
    }
}

void solve(){
    while(!que.empty()){
        dat tmp = que.front(); que.pop_front();
        int x = tmp.x, y = tmp.y, dir = tmp.d;
        int len = dist[x][y][dir];
//        printf("%d %d %d: %d\n", x, y, dir, len);
        for(int tdir = 0; tdir < 4; tdir++){
            if((able[x][y] & (1<<tdir)) == 0) continue;
            if(dist[x+xx[tdir]][y+yy[tdir]][tdir] < 1e9) continue;
            dist[x+xx[tdir]][y+yy[tdir]][tdir] = len + (tdir != dir);
            if(tdir == dir) que.push_front(dat(x+xx[tdir], y+yy[tdir], tdir));
            else que.push_back(dat(x+xx[tdir], y+yy[tdir], tdir));
        }
    }
}

int main(){
    scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d %d %d %d", &ax[i], &bx[i], &ay[i], &by[i]);
    }
    renumber();
    init();
    solve();
    printf("%d", *min_element(dist[ex][ey], dist[ex][ey]+4));
}

Compilation message

golf.cpp: In function 'int main()':
golf.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
golf.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         scanf("%d %d %d %d", &ax[i], &bx[i], &ay[i], &by[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 580 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 580 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 580 KB Output isn't correct
2 Halted 0 ms 0 KB -