Submission #1026088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026088		phong	Soccer (JOI17_soccer)	C++17	100 / 100	622 ms	55848 KiB

soccer

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

#define ll long long
//#define int long long
const int nmax = 500 + 5;
const int lg = 18;
const int base = 311;
const int M = 5e6;
const ll oo = 1e18 + 1;
const int mod = 987654321;
#define fi first
#define se second
#define endl "\n"
#define debug(a, m) for(int j = 1; j <= n; ++j) cout << a[j] << ' ';cout << endl;
#define pii pair<ll, int>

using namespace std;

int n, m, q, vis[nmax][nmax];
ll A, B, C;
ll dp[nmax][nmax][3][4];
ll F[nmax][nmax];
struct node{
    ll w;
    int x, y, id, h;
    friend bool operator < (const node&a, const node&b){
        return a.w > b.w;
    }
};
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
pii a[nmax * nmax];
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> m;
    cin >> A >> B >> C;
    cin >> q;
    for(int i = 1, u, v; i <= q; ++i){
        cin >> u >> v;
        a[i]= {u, v};
        vis[u][v] = 1;
    }
    memset(dp, 0x3f, sizeof dp);
    memset(F, 0x3f, sizeof F);
    priority_queue<node> two;
    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= m; ++j){
            if(vis[i][j]){
                F[i][j] = 0;
                two.push({F[i][j], i, j});
            }
        }
    }
    while(two.size()){
        node tmp = two.top();two.pop();
        if(tmp.w != F[tmp.x][tmp.y]) continue;
        for(int k = 0; k < 4; ++k){
            int i = dx[k] + tmp.x;
            int j = dy[k] + tmp.y;
            if(i >= 0 && i <= n && j >= 0 && j <= m){
                if(F[i][j] > tmp.w + C){
                    F[i][j] = tmp.w + C;
                    two.push({tmp.w + C, i, j});
                }
            }
        }
    }
    priority_queue<node> one;
    for(int j = 0; j < 4; ++j){
        dp[a[1].fi][a[1].se][0][j] = 0;
        one.push({0, a[1].fi, a[1].se, 0, j});
    }
    while(one.size()){
        node tmp = one.top();one.pop();
        if(tmp.w != dp[tmp.x][tmp.y][tmp.id][tmp.h]) continue;
        if(tmp.id == 0){
            int i = dx[tmp.h] + tmp.x;
            int j = dy[tmp.h] + tmp.y;
            if(i >= 0 && i <= n && j >= 0 && j <= m){
                if(dp[i][j][0][tmp.h] > tmp.w + C){
                    dp[i][j][0][tmp.h] = tmp.w + C;
                    one.push({tmp.w + C, i, j, 0, tmp.h});
                }
            }
            if(dp[tmp.x][tmp.y][tmp.id + 1][tmp.h] > tmp.w){
                dp[tmp.x][tmp.y][tmp.id + 1][tmp.h] = tmp.w;
                one.push({tmp.w, tmp.x, tmp.y, tmp.id + 1, tmp.h});
            }
            for(int k =0; k < 4; ++k){
                if(dp[tmp.x][tmp.y][0][k] > tmp.w){
                    dp[tmp.x][tmp.y][0][k] = tmp.w;
                    one.push({tmp.w, tmp.x, tmp.y, tmp.id, k});

                }
            }
        }
        else{
            if(tmp.id == 1){
                int i = dx[tmp.h] + tmp.x;
                int j = dy[tmp.h] + tmp.y;
                if(i >= 0 && i <= n && j >= 0 && j <= m){
                    if(dp[i][j][1][tmp.h] > tmp.w + A){
                        dp[i][j][1][tmp.h] = tmp.w + A;
                        one.push({tmp.w + A, i, j, 1, tmp.h});
                    }
                }
                if(dp[tmp.x][tmp.y][tmp.id ^ 1][tmp.h] > tmp.w + B + F[tmp.x][tmp.y]){
                    dp[tmp.x][tmp.y][tmp.id ^ 1][tmp.h] = tmp.w + B + F[tmp.x][tmp.y];
                    one.push({tmp.w + F[tmp.x][tmp.y] + B, tmp.x, tmp.y, tmp.id ^ 1, tmp.h});
                }
            }
        }
    }
    ll ans = oo;
//    cout << dp[1][5][0][1] << ' ' << F[1][4];
    for(int i = 0; i < 4; ++i){
        ans = min({ans, dp[a[q].fi][a[q].se][0][i]});
    }
    cout << ans;
}
/*
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10

*/

Compilation message (stderr)

soccer.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main(){
      | ^~~~
soccer.cpp: In function 'int main()':
soccer.cpp:14:12: warning: narrowing conversion of 'a[1].std::pair<long long int, int>::first' from 'long long int' to 'int' [-Wnarrowing]
   14 | #define fi first
      |            ^
soccer.cpp:77:27: note: in expansion of macro 'fi'
   77 |         one.push({0, a[1].fi, a[1].se, 0, j});
      |                           ^~

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