Submission #192843

#	Time	Username	Problem	Language	Result	Execution time	Memory
192843		Akashi	Soccer (JOI17_soccer)	C++14	100 / 100	1162 ms	38556 KiB

soccer

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

const long long INF = 1e18;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};

struct state{
    long long cost;
    int x, y, dir;

    bool operator < (const state &aux)const{
        return cost > aux.cost;
    }
};

int n, m, k, a, b, c;
int x[100005], y[100005];

long long ad[6];
long long d[505][505][6];

priority_queue <state> pq;

inline void Move(int l, int c, long long cost, int dir){
    for(int k = 0; k < 4 ; ++k){
        int x = l + dx[k];
        int y = c + dy[k];
        if(!(x > 0 && y > 0 && x <= n && y <= m)) continue ;

        if(cost + ad[dir] < d[x][y][dir]){
            d[x][y][dir] = cost + ad[dir];
            pq.push({d[x][y][dir], x, y, dir});
        }
    }
}

inline void Throw(int l, int c, long long cost, int dir){
    int x = l + dx[dir], y = c + dy[dir];
    if(x > 0 && y > 0 && x <= n && y <= m && d[x][y][dir] > cost + ad[dir]){
        d[x][y][dir] = cost + ad[dir];
        pq.push({d[x][y][dir], x, y, dir});
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%d%d%d", &a, &b, &c);
    scanf("%d", &k);

    for(int k = 0; k < 4 ; ++k) ad[k] = a;
    ad[4] = ad[5] = c;

    ++n; ++m;
    for(int i = 1; i <= k ; ++i){
        scanf("%d%d", &x[i], &y[i]);
        ++x[i]; ++y[i];
    }

    for(int i = 1; i <= n ; ++i)
        for(int j = 1; j <= m ; ++j)
            for(int k = 0; k < 6 ; ++k) d[i][j][k] = INF;

    for(int i = 1; i <= k ; ++i){
        d[x[i]][y[i]][5] = 0;
        pq.push({0, x[i], y[i], 5});
    }

    d[x[1]][y[1]][4] = 0;
    pq.push({0, x[1], y[1], 4});

    while(!pq.empty()){
        int l = pq.top().x, c = pq.top().y, dir = pq.top().dir;
        pq.pop();

        if(dir == 4){
            Move(l, c, d[l][c][4], 4);
            for(int k = 0; k < 4 ; ++k) Throw(l, c, d[l][c][4] + b, k);
        }

        if(dir < 4){
            Throw(l, c, d[l][c][dir], dir);
        }

        if(dir == 5){
            Move(l, c, d[l][c][5], 5);
        }

        long long Min = INF;
        for(int k = 0; k < 4 ; ++k) Min = min(Min, d[l][c][k]);
        if((dir == 5 || dir < 4) && (d[l][c][5] != INF && Min != INF)){
            Move(l, c, d[l][c][5] + Min, 4);
            for(int k = 0; k < 4 ; ++k) Throw(l, c, d[l][c][5] + Min + b, k);
        }
    }

    long long Sol = INF;
    for(int dir = 0; dir <= 4 ; ++dir) Sol = min(Sol, d[x[k]][y[k]][dir]);

    printf("%lld", Sol);
    return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
soccer.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &a, &b, &c);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
soccer.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x[i], &y[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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