Submission #1173549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173549		LucaIlie	Soccer (JOI17_soccer)	C++20	0 / 100	179 ms	21684 KiB

soccer

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAX_N = 500;
const int MAX_K = 1e5;
const long long INF = 1e18;
const int MAX_P = 5;
bool vis[MAX_N + 2][MAX_N + 2][MAX_P];
int lin[MAX_K], col[MAX_K];
int minDistPlayer[MAX_N + 2][MAX_N + 2];
long long minFatigue[MAX_N + 2][MAX_N + 2][MAX_P];
int dl[4] = { 1, 0, -1, 0 }, dc[4] = { 0, 1, 0, -1 };

int n, m, k, A, B, C;

void computeClosestPlayers() {
    for ( int l = 0; l <= n + 1; l++ ) {
        for ( int c = 0; c <= m + 1; c++ )
            minDistPlayer[l][c] = n + m;
    }

    for ( int l = 0; l <= n + 1; l++ )
        minDistPlayer[l][0] = minDistPlayer[l][m + 1] = -1;
    for ( int c = 0; c <= m + 1; c++ )
        minDistPlayer[0][c] = minDistPlayer[n + 1][c] = -1;

    queue<pair<int, int>> q;
    for ( int i = 0; i < k - 1; i++ ) {
        int l = lin[i], c = col[i];
        minDistPlayer[l][c] = 0;
        q.push( { l, c } );
    }

    while ( !q.empty() ) {
        pair<int, int> cell = q.front();
        q.pop();

        int l = cell.first, c = cell.second;
        for ( int d = 0; d < 4; d++ ) {
            if ( minDistPlayer[l][c] + 1 < minDistPlayer[l + dl[d]][c + dc[d]] ) {
                minDistPlayer[l + dl[d]][c + dc[d]] = minDistPlayer[l][c] + 1;
                q.push( { l + dl[d], c + dc[d] } );
            }
        }
    }
}

struct state {
    int l, c, p;
};

struct infoPQ {
    long long d;
    state s;

    bool operator < ( const infoPQ &x ) const {
        return d > x.d;
    }
};

priority_queue<infoPQ> pq;

const int WITH_PLAYER = 4;

void computeMinimumFatigue() {
    for ( int p = 0; p < MAX_P; p++ ) {
        for ( int l = 0; l <= n + 1; l++ ) {
            for ( int c = 0; c <= m + 1; c++ )
                minFatigue[l][c][p] = INF;
        }

        for ( int l = 0; l <= n + 1; l++ )
            minFatigue[l][0][p] = minFatigue[l][m + 1][p] = -1;
        for ( int c = 0; c <= m + 1; c++ )
            minFatigue[0][c][p] = minFatigue[n + 1][c][p] = -1;
    }
    
    minFatigue[lin[0]][col[0]][WITH_PLAYER] = 0;
    pq.push( { 0, { lin[0], col[0], WITH_PLAYER } } );
    while ( !pq.empty() ) {
        infoPQ x = pq.top();
        pq.pop();
        int l = x.s.l, c = x.s.c, p = x.s.p;
        if ( vis[l][c][p] )
            continue;

        vis[l][c][p] = true;
        if ( p == WITH_PLAYER ) {
            for ( int d = 0; d < 4; d++ ) {
                if ( minFatigue[l][c][WITH_PLAYER] + C < minFatigue[l + dl[d]][c + dc[d]][WITH_PLAYER] ) {
                    minFatigue[l + dl[d]][c + dc[d]][WITH_PLAYER] = minFatigue[l][c][WITH_PLAYER] + C;
                    pq.push( { minFatigue[l + dl[d]][c + dc[d]][WITH_PLAYER], { l + dl[d], c + dc[d], WITH_PLAYER } } );
                }
                if ( minFatigue[l][c][WITH_PLAYER] + B < minFatigue[l][c][d] ) {
                    minFatigue[l][c][d] = minFatigue[l][c][WITH_PLAYER] + B;
                    pq.push( { minFatigue[l][c][d], { l, c, d } } );
                }
            }
        } else {
            int d = p;
            if ( minFatigue[l][c][d] + A < minFatigue[l + dl[d]][c + dc[d]][d] ) {
                minFatigue[l + dl[d]][c + dc[d]][d] = minFatigue[l][c][d] + A;
                pq.push( { minFatigue[l + dl[d]][c + dc[d]][d], { l + dl[d], c + dc[d], d } } );
            }

            if ( minFatigue[l][c][d] + (long long)C * minDistPlayer[l][c] < minFatigue[l][c][WITH_PLAYER] ) {
                minFatigue[l][c][WITH_PLAYER] = minFatigue[l][c][d] + (long long)C * minDistPlayer[l][c];
                pq.push( { minFatigue[l][c][WITH_PLAYER], { l, c, WITH_PLAYER } } );
            }
        }
    }
}

signed main() {
    cin.tie( nullptr );
    ios_base::sync_with_stdio( false );

    cin >> n >> m;
    n++, m++;
    cin >> A >> B >> C;
    cin >> k;
    for ( int i = 0; i < k; i++ ) {
        cin >> lin[i] >> col[i];
        lin[i]++;
        col[i]++;
    }
   
    computeClosestPlayers();
    computeMinimumFatigue();

    int l = lin[k - 1], c = col[k - 1];
    long long best = INF;
    for ( int p = 0; p < MAX_P; p++ )
        best = min( best, minFatigue[l][c][p] );

    cout << best << "\n";

    return 0;
}

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