Submission #1221993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221993		vincentbucourt1	Soccer (JOI17_soccer)	C++20	100 / 100	634 ms	61524 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
void fastIO(){ios_base::sync_with_stdio(false),cin.tie(0);}
#define int long long
#define f first
#define s second

const int INF = (int)1e18;
const int MAXR = 520, MAXC = 520;
const int dr[4] = {0,1,0,-1}, dc[4] = {1,0,-1,0};

int R, C;
int closePlayer[MAXR][MAXC];
int X, Y, Z;
int N;
int startR, startC, endR, endC;
int SP[MAXR][MAXC][2][4];
enum State{onPerson, onKick};
struct Situ {
    int r, c;
    State state;
    int direc;
};
struct cmpSitu {
    bool operator()(const pair<int,Situ>& a, const pair<int,Situ>& b) {
        return a.f > b.f;
    }
};

bool inside (int r, int c) {
    return (0 <= r && r <= R && 0 <= c && c <= C);
}

signed main() {
    fastIO();
    cin >> R >> C;
    cin >> X >> Y >> Z;
    cin >> N;
    for (int r = 0; r <= R; r++) {
        for (int c = 0; c <= C; c++) {
            closePlayer[r][c] = INF;
        }
    }
    deque<pair<int,int>> Q;
    for (int i = 0; i < N; i++) {
        int r, c;
        cin >> r >> c;
        if (i == 0) startR = r, startC = c;
        else if (i == N-1) endR = r, endC = c;
        closePlayer[r][c] = 0;
        Q.push_back({r, c});
    }
    while (!Q.empty()) {
        pair<int,int> on = Q.front();
        Q.pop_front();
        int rOn = on.f, cOn = on.s;
        for (int d = 0; d < 4; d++) {
            if (inside(rOn+dr[d], cOn+dc[d]) && closePlayer[rOn + dr[d]][cOn + dc[d]] > closePlayer[rOn][cOn] + 1) {
                closePlayer[rOn + dr[d]][cOn + dc[d]] = closePlayer[rOn][cOn] + 1;
                Q.push_back({rOn+dr[d], cOn+dc[d]});
            }
        }
    }
    // for (int r = 0; r < R; r++) {
    //     for (int c = 0; c < C; c++) cerr << closePlayer[r][c] << " ";
    //     cerr << "\n";
    // }
    for (int r = 0; r <= R; r++) {
        for (int c = 0; c <= C; c++) {
            for (int s = 0; s < 2; s++) {
                for (int d = 0; d < 4; d++) {
                    SP[r][c][s][d] = INF;
                }
            }
        }
    }
    for (int d = 0; d < 4; d++) {
        SP[startR][startC][onPerson][d] = 0;
    }
    priority_queue<pair<int,Situ>, vector<pair<int,Situ>>, cmpSitu> PQ;
    PQ.push({0, Situ{startR, startC, onPerson, 0}});
    while (!PQ.empty()) {
        pair<int,Situ> situOn = PQ.top();
        PQ.pop();
        int r = situOn.s.r, c = situOn.s.c, direc = situOn.s.direc;
        State state = situOn.s.state;
        int distOn = situOn.f;
        // if (distOn > SP[r][c][state][direc]) {
        //     continue;
        // }
        for (int d = 0; d < 4; d++) {
            if (!inside(r+dr[d], c+dc[d])) {
                continue;
            }
            assert(inside(r+dr[d], c+dc[d]));
            if (state == onPerson) {
                if (SP[r+dr[d]][c+dc[d]][onPerson][d] > SP[r][c][onPerson][direc] + Z) {
                    SP[r+dr[d]][c+dc[d]][onPerson][d] = SP[r][c][onPerson][direc] + Z;
                    PQ.push({SP[r+dr[d]][c+dc[d]][onPerson][d], Situ{r+dr[d], c+dc[d], onPerson, d}});
                }
                if (SP[r+dr[d]][c+dc[d]][onKick][d] > SP[r][c][onPerson][direc] + X + Y) {
                    SP[r+dr[d]][c+dc[d]][onKick][d] = SP[r][c][onPerson][direc] + X + Y;
                    PQ.push({SP[r+dr[d]][c+dc[d]][onKick][d], Situ{r+dr[d], c+dc[d], onKick, d}});
                }
            }
            else {
                assert(state == onKick);
                if (d == direc && SP[r+dr[d]][c+dc[d]][onKick][d] > SP[r][c][onKick][direc] + X) {
                    SP[r+dr[d]][c+dc[d]][onKick][d] = SP[r][c][onKick][direc] + X;
                    PQ.push({SP[r+dr[d]][c+dc[d]][onKick][d], Situ{r+dr[d], c+dc[d], onKick, d}});
                }
                if (SP[r][c][onPerson][d] > SP[r][c][onKick][direc] + closePlayer[r][c]*Z) {
                    SP[r][c][onPerson][d] = SP[r][c][onKick][direc] + closePlayer[r][c]*Z;
                    PQ.push({SP[r][c][onPerson][d], Situ{r, c, onPerson, d}});
                }
            }
        }
    }
    int ans = INF;
    for (int s = 0; s < 2; s++) {
        for (int d = 0; d < 4; d++) {
            ans = min(ans, SP[endR][endC][s][d]);
        }
    }
    cout << ans << "\n";
}

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