Submission #291918

#	Time	Username	Problem	Language	Result	Execution time	Memory
291918		anonymous	Soccer (JOI17_soccer)	C++14	100 / 100	669 ms	40564 KiB

soccer

#include <iostream>
#include <queue>
#include <utility>
#define MAXD 505
#define MAXN 100005
#define LL long long
using namespace std;
int W, H, N, P[MAXN][2];
LL A, B, C, dist[MAXD][MAXD][6], closest[MAXD][MAXD];

int Dy[4] = {1,0,-1,0}, Dx[4] = {0,1,0,-1};

bool okay(int x, int y) {
    return(x >= 0 && y >= 0 && x <= H && y <= W);
}

struct state {
    int x, y, type; //still, dribble, up, down, right, left
    LL dist;
};

class CompareClass {
public:
    bool operator() (state a, state b) {
        return(a.dist > b.dist); //smallest first
    }
};

priority_queue <state, vector<state>, CompareClass> PQ;

void gendist() {
    queue <pair<int,int> > Q;
    for (int i=0; i <= H; i++) {
        for (int j=0; j <= W; j++) {
            closest[i][j] = 1LL << 60;
        }
    }

    for (int i=1; i<=N; i++) {
        Q.push({P[i][0], P[i][1]});
        closest[P[i][0]][P[i][1]] = 0;
    }

    while (Q.size()) {
        int cx = Q.front().first, cy = Q.front().second;
        Q.pop();
        for (int i=0; i<4; i++) {
            if (okay(cx + Dx[i], cy + Dy[i]) && closest[cx+Dx[i]][cy + Dy[i]] > closest[cx][cy]+C) {
                closest[cx+Dx[i]][cy + Dy[i]] = closest[cx][cy]+C;
                Q.push({cx+Dx[i], cy+Dy[i]});
            }
        }
    }

}

void relax(int x, int y, int type, LL d) {
    if (dist[x][y][type] > d) {
        dist[x][y][type] = d;
        PQ.push(state {x,y,type, d});
    }
}

int main() {
    //freopen("soccerin.txt","r",stdin);
    scanf("%d %d\n%lld %lld %lld\n%d",&H,&W,&A,&B,&C,&N);
    for (int i=1; i<=N; i++) {
        scanf("%d %d",&P[i][0], &P[i][1]);
    }
    gendist();

    PQ.push(state {P[1][0], P[1][1], 0, 0});
    for (int i=0; i <= H; i++) {
        for (int j=0; j <= W; j++) {
            for (int k=0; k<6; k++) {
                dist[i][j][k] = 1LL << 60;
            }
        }
    }
    dist[P[1][0]][P[1][1]][0] = 0;

    while (PQ.size()) {
        state cur = PQ.top();
        PQ.pop();
        if (cur.x == P[N][0] && cur.y == P[N][1]) {
            printf("%lld",cur.dist);
            return(0);
        }
        if (cur.dist != dist[cur.x][cur.y][cur.type]) {continue;}
        if (cur.type == 0) {
            relax(cur.x, cur.y, 1, cur.dist + closest[cur.x][cur.y]);
            for (int i=2; i <= 5; i++) {
                relax(cur.x,cur.y, i, cur.dist + closest[cur.x][cur.y] + B);
            }
        } else if (cur.type == 1) {
            relax(cur.x, cur.y, 0, cur.dist);
            for (int i=2; i <= 5; i++) {
                relax(cur.x,cur.y, i, cur.dist + B);
            }
            for (int i=0; i<4; i++) {
                if (okay(cur.x + Dx[i], cur.y + Dy[i])) {
                    relax(cur.x + Dx[i], cur.y + Dy[i], 1, cur.dist + C);
                }
            }
        } else {
            relax(cur.x, cur.y, 0, cur.dist);
            if (okay(cur.x + Dx[cur.type - 2], cur.y + Dy[cur.type - 2])) {
                relax(cur.x + Dx[cur.type - 2], cur.y + Dy[cur.type - 2], cur.type, cur.dist + A);
            }
        }
    }
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     scanf("%d %d\n%lld %lld %lld\n%d",&H,&W,&A,&B,&C,&N);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |         scanf("%d %d",&P[i][0], &P[i][1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65