oj.uz

Submission #590520

# Submission time Handle Problem Language Result Execution time Memory
590520 2022-07-06T05:10:28 Z 반딧불(#8412) Golf (JOI17_golf) C++17
30 / 100
 3379 ms 668040 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];
bool visited[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!=W && (!board[i][j] || !board[i-1][j])) able[i][j]|=1;
            if(i!=H && (!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(){
    deque<dat> tmpQue;
    while(!que.empty()){
        while(!que.empty()){
            dat tmp = que.front(); que.pop_front();
            int x = tmp.x, y = tmp.y, dir = tmp.d;
            if(visited[x][y][dir]) continue;
            visited[x][y][dir] = 1;
            int len = dist[x][y][dir];
//            printf("%d %d %d: %d\n", x, y, dir, len);
            if(x==2 && y==1 && dir==1){
                printf("");
            }
            for(int tdir = 0; tdir < 4; tdir++){
                if((able[x][y] & (1<<tdir)) == 0) continue;
                if(dist[x+xx[tdir]][y+yy[tdir]][tdir] <= len + (tdir != dir)) continue;
                dist[x+xx[tdir]][y+yy[tdir]][tdir] = len + (tdir != dir);
                if(tdir == dir) que.push_back(dat(x+xx[tdir], y+yy[tdir], tdir));
                else tmpQue.push_back(dat(x+xx[tdir], y+yy[tdir], tdir));
            }
        }
        que.swap(tmpQue);
    }
}

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 'void solve()':
golf.cpp:93:24: warning: zero-length gnu_printf format string [-Wformat-zero-length]
   93 |                 printf("");
      |                        ^~
golf.cpp: In function 'int main()':
golf.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
golf.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         scanf("%d %d %d %d", &ax[i], &bx[i], &ay[i], &by[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 11 ms 8248 KB Output is correct
5 Correct 77 ms 36280 KB Output is correct
6 Correct 61 ms 37364 KB Output is correct
7 Correct 58 ms 36200 KB Output is correct
8 Correct 62 ms 38096 KB Output is correct
9 Correct 62 ms 36608 KB Output is correct
10 Correct 67 ms 38112 KB Output is correct
11 Correct 72 ms 39960 KB Output is correct
12 Correct 58 ms 36916 KB Output is correct
13 Correct 60 ms 37948 KB Output is correct
14 Correct 69 ms 37936 KB Output is correct
15 Correct 23 ms 10708 KB Output is correct
16 Correct 87 ms 28720 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 11 ms 8248 KB Output is correct
5 Correct 77 ms 36280 KB Output is correct
6 Correct 61 ms 37364 KB Output is correct
7 Correct 58 ms 36200 KB Output is correct
8 Correct 62 ms 38096 KB Output is correct
9 Correct 62 ms 36608 KB Output is correct
10 Correct 67 ms 38112 KB Output is correct
11 Correct 72 ms 39960 KB Output is correct
12 Correct 58 ms 36916 KB Output is correct
13 Correct 60 ms 37948 KB Output is correct
14 Correct 69 ms 37936 KB Output is correct
15 Correct 23 ms 10708 KB Output is correct
16 Correct 87 ms 28720 KB Output is correct
17 Correct 1600 ms 438576 KB Output is correct
18 Correct 1520 ms 443828 KB Output is correct
19 Correct 1307 ms 423124 KB Output is correct
20 Correct 1443 ms 436300 KB Output is correct
21 Correct 1603 ms 451576 KB Output is correct
22 Correct 1439 ms 446392 KB Output is correct
23 Correct 1426 ms 432020 KB Output is correct
24 Correct 1275 ms 424692 KB Output is correct
25 Correct 1422 ms 429296 KB Output is correct
26 Correct 1383 ms 423136 KB Output is correct
27 Correct 29 ms 13760 KB Output is correct
28 Correct 102 ms 33172 KB Output is correct
29 Correct 108 ms 33892 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 11 ms 8248 KB Output is correct
5 Correct 77 ms 36280 KB Output is correct
6 Correct 61 ms 37364 KB Output is correct
7 Correct 58 ms 36200 KB Output is correct
8 Correct 62 ms 38096 KB Output is correct
9 Correct 62 ms 36608 KB Output is correct
10 Correct 67 ms 38112 KB Output is correct
11 Correct 72 ms 39960 KB Output is correct
12 Correct 58 ms 36916 KB Output is correct
13 Correct 60 ms 37948 KB Output is correct
14 Correct 69 ms 37936 KB Output is correct
15 Correct 23 ms 10708 KB Output is correct
16 Correct 87 ms 28720 KB Output is correct
17 Correct 1600 ms 438576 KB Output is correct
18 Correct 1520 ms 443828 KB Output is correct
19 Correct 1307 ms 423124 KB Output is correct
20 Correct 1443 ms 436300 KB Output is correct
21 Correct 1603 ms 451576 KB Output is correct
22 Correct 1439 ms 446392 KB Output is correct
23 Correct 1426 ms 432020 KB Output is correct
24 Correct 1275 ms 424692 KB Output is correct
25 Correct 1422 ms 429296 KB Output is correct
26 Correct 1383 ms 423136 KB Output is correct
27 Correct 29 ms 13760 KB Output is correct
28 Correct 102 ms 33172 KB Output is correct
29 Correct 108 ms 33892 KB Output is correct
30 Runtime error 3379 ms 668040 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -