Submission #1073195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073195		_callmelucian	Soccer (JOI17_soccer)	C++14	100 / 100	728 ms	46524 KiB

soccer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;
bool vis[505][505], visit[505][505][2][4];
int x[mn], y[mn], closest[505][505];
ll dist[505][505][2][4];
int n, m, A, B, C;

const int dr[4] = {-1, 0, 0, 1};
const int dc[4] = {0, -1, 1, 0};

bool ok (int i, int j) {
    if (i < 0 || j < 0) return 0;
    if (i > n || j > m) return 0;
    return 1;
}

int mahattan (int i, int j, int u, int v) {
    return abs(i - u) + abs(j - v);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> A >> B >> C;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++) closest[i][j] = INT_MAX;

    int k; cin >> k;
    queue<pii> q;
    for (int i = 1; i <= k; i++) {
        cin >> x[i] >> y[i];
        closest[x[i]][y[i]] = 0;
        q.emplace(x[i], y[i]);
    }

    while (q.size()) {
        int i, j; tie(i, j) = q.front(); q.pop();
        if (vis[i][j]) continue;
        vis[i][j] = 1;
        for (int way = 0; way < 4; way++) {
            int i2 = i + dr[way], j2 = j + dc[way];
            if (ok(i2, j2) && closest[i][j] + 1 < closest[i2][j2]) {
                closest[i2][j2] = closest[i][j] + 1;
                q.emplace(i2, j2);
            }
        }
    }

    priority_queue<tuple<ll,int,int,int,int>> pq; pq.emplace(0, x[1], y[1], 0, 0);
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int kick = 0; kick < 2; kick++)
                for (int way = 0; way < 4; way++) dist[i][j][kick][way] = LLONG_MAX;
    dist[x[1]][y[1]][0][0] = 0;

    ll ans = LLONG_MAX;
    while (pq.size()) {
        ll ndst; int i, j, kick, way; tie(ndst, i, j, kick, way) = pq.top(); pq.pop();
        if (visit[i][j][kick][way]) continue;
        visit[i][j][kick][way] = 1;

        ans = min(ans, dist[i][j][kick][way] + 1LL * C * mahattan(i, j, x[k], y[k]));

        if (kick) {
            // switch to walk mode
            if (dist[i][j][1][way] + 1LL * C * closest[i][j] < dist[i][j][0][way]) {
                dist[i][j][0][way] = dist[i][j][1][way] + 1LL * C * closest[i][j];
                pq.emplace(-dist[i][j][0][way], i, j, 0, way);
            }

            // extend the kick
            int i2 = i + dr[way], j2 = j + dc[way];
            if (ok(i2, j2) && dist[i][j][1][way] + A < dist[i2][j2][1][way]) {
                dist[i2][j2][1][way] = dist[i][j][1][way] + A;
                pq.emplace(-dist[i2][j2][1][way], i2, j2, 1, way);
            }
        }

        else {
            // switch to kick mode
            if (dist[i][j][0][way] + B < dist[i][j][1][way]) {
                dist[i][j][1][way] = dist[i][j][0][way] + B;
                pq.emplace(-dist[i][j][1][way], i, j, 1, way);
            }

            // rotate
            int nway = (way + 1) % 4;
            if (dist[i][j][0][way] < dist[i][j][0][nway]) {
                dist[i][j][0][nway] = dist[i][j][0][way];
                pq.emplace(-dist[i][j][0][nway], i, j, 0, nway);
            }

            // extend the walk
            int i2 = i + dr[way], j2 = j + dc[way];
            if (ok(i2, j2) && dist[i][j][0][way] + C < dist[i2][j2][0][way]) {
                dist[i2][j2][0][way] = dist[i][j][0][way] + C;
                pq.emplace(-dist[i2][j2][0][way], i2, j2, 0, way);
            }
        }
    }
    cout << ans;

    return 0;
}

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