Submission #654843

#	Time	Username	Problem	Language	Result	Execution time	Memory
654843		keta_tsimakuridze	Soccer (JOI17_soccer)	C++14	100 / 100	514 ms	25748 KiB

soccer

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
#define PII pair<pii,pii>
using namespace std;
const int N = 505 + 5, inf = 1e18; // !
int d[N][N][2], D[N][N][6];int n, m;
int dx[] = {0, 0, 0, 1, -1}, dy[] = {0, 1, -1, 0, 0};
bool ok(int i,int j) {
    return (min(i, j) >= 0 && i <= n && j <= m);
}
main(){

    cin >> n >> m;
    int a, b, c;
    cin >> a >> b >> c;
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= m; j++) {
            d[i][j][0] = d[i][j][1] = inf;
            for(int t = 0; t <= 5; ++t) D[i][j][t] = inf;
        }
    }
    
    int Q;
    cin >> Q;
    priority_queue<PII, vector<PII>, greater<PII> > pq;
    queue<pair<int,int>> q[2];
    for(int i = 1; i <= Q; i++) {
        int x, y; cin >> x >> y;
        if(d[x][y][0])
        q[0].push({x, y});
        d[x][y][0] = 0;
        if(i == 1) {
            D[x][y][0] = 0;
            pq.push({{0, 0}, {x, y}});
        }
        if(i == Q) {
            d[x][y][1] = 0;
            q[1].push({x, y});
        }
    }
    for(int t = 0; t < 2; t++)
    while(q[t].size()) {
        int x = q[t].front().f, y = q[t].front().s;
        q[t].pop();
        for(int j = 1; j <= 4; j++) {
            int xn = x + dx[j], yn = y + dy[j];
            if(ok(xn, yn) && d[xn][yn][t] > d[x][y][t] + c) {
                d[xn][yn][t] = d[x][y][t] + c;
                q[t].push({xn, yn});
            }
        }
    }

    int ans = 1e18;
    while(pq.size()) {
        int di = pq.top().f.f, t = pq.top().f.s;
        int x = pq.top().s.f, y = pq.top().s.s;
        pq.pop();
        if(D[x][y][t] < di) continue;
        ans = min(ans, D[x][y][t] + d[x][y][1]);
        if(t && t < 5) {
            int xn = x +dx[t], yn = y + dy[t];
            if(ok(xn, yn) && D[xn][yn][t] > di + a) {
                D[xn][yn][t] = di + a;
                pq.push({{di + a, t}, {xn, yn}});
            }
            if(D[x][y][5] > di) {
                D[x][y][5] = di;
                pq.push({{di, 5}, {x, y}});
            }
            continue;
        }
        if(t == 5) {
            if(D[x][y][0] > D[x][y][5] + d[x][y][0]) {
                D[x][y][0] = D[x][y][5] + d[x][y][0];
                pq.push({{D[x][y][0], 0}, {x, y}});
            }
            continue;
        }
        for(int t = 1; t < 5; t++) {
            int xn = x + dx[t], yn = y + dy[t];
            if(!ok(xn, yn)) continue;
            if(D[xn][yn][0] > di + c) {
               D[xn][yn][0] = di + c;
               pq.push({{di + c, 0}, {xn, yn}});
            }
            if(D[xn][yn][t] > di + a + b) {
               D[xn][yn][t] = di + a + b;
               pq.push({{di + a + b, t}, {xn, yn}});
            }
        }
    }
    cout << ans;
 }

Compilation message (stderr)

soccer.cpp:14:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   14 | main(){
      | ^~~~

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