Submission #53659

#	Time	Username	Problem	Language	Result	Execution time	Memory
53659		SpaimaCarpatilor	Soccer (JOI17_soccer)	C++17	100 / 100	967 ms	23264 KiB

soccer

#include<bits/stdc++.h>

using namespace std;

int A, B, C, H, W, N, d[509][509], x[100009], y[100009];
long long minD[5][509][509];
const long long INF = 1LL << 60;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
queue < pair < int, int > > cc;

void read ()
{
    scanf ("%d %d", &H, &W), H ++, W ++;
    scanf ("%d %d %d", &A, &B, &C);
    scanf ("%d", &N);
    for (int i=1; i<=H; i++)
        for (int j=1; j<=W; j++)
            d[i][j] = -1;
    for (int i=1; i<=N; i++)
    {
        scanf ("%d %d", &x[i], &y[i]), x[i] ++, y[i] ++;
        d[x[i]][y[i]] = 0, cc.push ({x[i], y[i]});
    }
    while (!cc.empty ())
    {
        auto curr = cc.front ();
        cc.pop ();
        for (int k=0; k<4; k++)
        {
            int nx = curr.first + dx[k], ny = curr.second + dy[k];
            if (d[nx][ny] == -1)
                d[nx][ny] = d[curr.first][curr.second] + 1, cc.push ({nx, ny});
        }
    }
}

priority_queue < pair < long long, pair < int, pair < int, int > > > > PQ;
void update (int p, int i, int j, long long d)
{
    if (i < 1 || j < 1 || i > H || j > W) return ;
    if (d < minD[p][i][j])
        minD[p][i][j] = d, PQ.push ({-d, {p, {i, j}}});
}

int modul (int x)
{
    if (x < 0) return -x;
    return x;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

read ();
for (int p=0; p<5; p++)
    for (int i=1; i<=H; i++)
        for (int j=1; j<=W; j++)
            minD[p][i][j] = INF;
PQ.push ({0, {4, {x[1], y[1]}}}), minD[4][x[1]][y[1]] = 0;
while (!PQ.empty ())
{
    auto curr = PQ.top ();
    PQ.pop ();
    int i = curr.second.second.first, j = curr.second.second.second, p = curr.second.first;
    if (minD[p][i][j] != -curr.first) continue;
    if (p == 4)
    {
        for (int k=0; k<4; k++)
        {
            update (4, i + dx[k], j + dy[k], minD[4][i][j] + C);
            update (k, i + dx[k], j + dy[k], minD[4][i][j] + A + B);
        }
    }
    else
    {
        update (4, i, j, minD[p][i][j] + 1LL * C * d[i][j]);
        update (p, i + dx[p], j + dy[p], minD[p][i][j] + A);
    }
}
printf ("%lld\n", minD[4][x[N]][y[N]]);
return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'void read()':
soccer.cpp:14:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &H, &W), H ++, W ++;
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
soccer.cpp:15:11: 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:16:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &N);
     ~~~~~~^~~~~~~~~~
soccer.cpp:22:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d %d", &x[i], &y[i]), x[i] ++, y[i] ++;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~

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