Submission #537399

#	Time	Username	Problem	Language	Result	Execution time	Memory
537399		79brue	Soccer (JOI17_soccer)	C++14	100 / 100	2759 ms	171152 KiB

soccer

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
 
typedef long long ll;
 
struct dat{
    ll x, y, d; int i;
    dat(){}
    dat(ll x, ll y, ll d, int i): x(x), y(y), d(d), i(i){}
};
 
struct cont{
    ll x, y; int d, i; ll dist;
    cont(){}
    cont(ll x, ll y, int d, int i, ll dist): x(x), y(y), d(d), i(i), dist(dist){}
 
    bool operator<(const cont &r)const{
        return dist > r.dist;
    }
};
 
const int xx[]={0, 1, 0, -1}, yy[]={1, 0, -1, 0};
 
int n, m, k;
ll a, b, c;
ll x[100002], y[100002];
ll near[502][502][2];
int nearIdx[502][502][2];
ll dist[502][502][5][2];
int distIdx[502][502][5][2];
ll ans = LLONG_MAX;
 
void makeNear(){
    for(int i=0; i<=n; i++){
        for(int j=0; j<=m; j++){
            near[i][j][0] = near[i][j][1] = 1e18;
            nearIdx[i][j][0] = nearIdx[i][j][1] = -1;
            for(int dir=0; dir<5; dir++){
                dist[i][j][dir][0] = dist[i][j][dir][1] = 1e18;
                distIdx[i][j][dir][0] = distIdx[i][j][dir][1] = -1;
            }
        }
    }
 
    queue<dat> que;
    for(int i=1; i<=k; i++){
        que.push(dat(x[i], y[i], 0, i));
        for(int j=0; j<2; j++){
            if(near[x[i]][y[i]][j] == 1e18){
                near[x[i]][y[i]][j] = 0;
                nearIdx[x[i]][y[i]][j] = i;
                break;
            }
        }
    }
 
    while(!que.empty()){
        dat tmp = que.front();
        que.pop();
 
        for(int d=0; d<4; d++){
            int tx = tmp.x+xx[d], ty = tmp.y+yy[d];
            if(!(0<=tx&&tx<=n&&0<=ty&&ty<=m) || nearIdx[tx][ty][1] != -1 || nearIdx[tx][ty][0] == tmp.i) continue;
            int u = 0;
            if(nearIdx[tx][ty][0] != -1) u=1;
            near[tx][ty][u] = tmp.d + 1;
            nearIdx[tx][ty][u] = tmp.i;
            que.push(dat(tx, ty, tmp.d+1, tmp.i));
        }
    }
}
 
int main(){
    scanf("%d %d %lld %lld %lld %d", &n, &m, &a, &b, &c, &k);
    for(int i=1; i<=k; i++) scanf("%lld %lld", &x[i], &y[i]);
    makeNear();
 
    for(int i=0; i<=n; i++){
        for(int j=0; j<=m; j++){
//            printf("%d %d: %lld %d / %lld %d\n", i, j, near[i][j][0], nearIdx[i][j][0], near[i][j][1], nearIdx[i][j][1]);
        }
    }
 
    priority_queue<cont> pq;
    pq.push(cont(x[1], y[1], 4, 1, 0));
 
    while(!pq.empty()){
        cont tmp = pq.top(); pq.pop();
        if(distIdx[tmp.x][tmp.y][tmp.d][1] != -1 || distIdx[tmp.x][tmp.y][tmp.d][0] == tmp.i) continue;
        int u = (distIdx[tmp.x][tmp.y][tmp.d][0] == -1) ? 0 : 1;
        dist[tmp.x][tmp.y][tmp.d][u] = tmp.dist;
        distIdx[tmp.x][tmp.y][tmp.d][u] = tmp.i;
 
        ans = min(ans, tmp.dist + c * (abs(tmp.x-x[k]) + abs(tmp.y-y[k])));
//        printf("%lld %lld %d %d: %lld\n", tmp.x, tmp.y, tmp.d, u, tmp.dist);
 
        if(tmp.d == 4){ /// 현재 선수가 공을 가지고 있다.
            for(int d=0; d<4; d++){
                ll tx = tmp.x + xx[d], ty = tmp.y + yy[d];
                if(tx<0||tx>n||ty<0||ty>m) continue;
                { /// d번 방향으로 한 칸 이동하기
                    if(distIdx[tx][ty][4][1] != -1 || distIdx[tx][ty][4][0] == tmp.i) continue;
                    pq.push(cont(tx, ty, 4, tmp.i, tmp.dist + c));
                }
                { /// d번 방향으로 공 굴리기
                    if(distIdx[tx][ty][d][1] != -1 || distIdx[tx][ty][d][0] == tmp.i) continue;
                    pq.push(cont(tx, ty, d, tmp.i, tmp.dist + a + b));
                }
            }
        }
        else{
            { /// 공이 계속 굴러가게 하기
                int d = tmp.d;
                ll tx = tmp.x + xx[d], ty = tmp.y + yy[d];
                if(!(tx<0 || tx>n || ty<0 || ty>m)){
                    if(distIdx[tx][ty][d][1] != -1 || distIdx[tx][ty][d][0] == tmp.i) continue;
                    pq.push(cont(tx, ty, d, tmp.i, tmp.dist + a));
                }
            }
            { /// 공을 선수가 잡기
                for(int u=0; u<2; u++){
                    if(tmp.i == nearIdx[tmp.x][tmp.y][u]) continue;
                    pq.push(cont(tmp.x, tmp.y, 4, nearIdx[tmp.x][tmp.y][u], tmp.dist + near[tmp.x][tmp.y][u] * c));
                }
            }
        }
    }
 
    printf("%lld", ans);
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d %d %lld %lld %lld %d", &n, &m, &a, &b, &c, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:79:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     for(int i=1; i<=k; i++) scanf("%lld %lld", &x[i], &y[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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