Submission #1221760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221760		badge881	Soccer (JOI17_soccer)	C++20	100 / 100	284 ms	19132 KiB

soccer

#include <bits/stdc++.h>

using namespace std;

const int N = 505, mxN = 1e5 + 5;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int n, m, k, A, B, C;
int s[mxN], t[mxN], f[N][N];
long long d[N][N][5];

bool inside(int i, int j)
{
    return 0 <= i && i <= n && 0 <= j && j <= m;
}

int main()
{

    scanf("%d%d%d%d%d%d", &n, &m, &A, &B, &C, &k);
    memset(f, -1, sizeof(f));
    queue<array<int, 2>> q;
    for (int i = 1; i <= k; ++i)
    {
        scanf("%d%d", &s[i], &t[i]);
        f[s[i]][t[i]] = 0;
        q.push({s[i], t[i]});
    }
    while (q.size())
    {
        auto [u, v] = q.front();
        q.pop();
        for (int dr = 0; dr < 4; ++dr)
        {
            int x = u + dx[dr], y = v + dy[dr];
            if (inside(x, y) && f[x][y] == -1)
            {
                f[x][y] = f[u][v] + 1;
                q.push({x, y});
            }
        }
    }
    memset(d, 0x3f, sizeof(d));
    using T = tuple<long long, int, int, int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    auto psh = [&](int i, int j, int t, long long w)
    {
        if (inside(i, j) && d[i][j][t] > w)
            pq.push({d[i][j][t] = w, i, j, t});
    };
    psh(s[1], t[1], 4, 0);
    while (pq.size())
    {
        auto [c, x, y, t] = pq.top();
        pq.pop();
        if (c != d[x][y][t])
        {
            continue;
        }
        if (t == 4)
        {
            for (int dr = 0; dr < 4; ++dr)
            {
                int i = x + dx[dr], j = y + dy[dr];
                psh(i, j, dr, c + B + A);
                psh(i, j, 4, c + C);
            }
        }
        else
        {
            psh(x + dx[t], y + dy[t], t, c + A);
            psh(x, y, 4, c + (long long)f[x][y] * C);
        }
    }
    printf("%lld\n", d[s[k]][t[k]][4]);
    return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d%d%d%d%d%d", &n, &m, &A, &B, &C, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         scanf("%d%d", &s[i], &t[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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