Submission #1052004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052004		SamAnd	Soccer (JOI17_soccer)	C++17	100 / 100	405 ms	31456 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 503;
const int xx[4] = {0, 1, 0, -1};
const int yy[4] = {1, 0, -1, 0};

int n, m;
int A, B, C;
int k;
int x[N * N], y[N * N];
bool cc[N][N];
int dd[N][N];

struct ban
{
    int x, y, z;
    ll d;
    ban(){}
    ban(int x, int y, int z, ll d)
    {
        this->x = x;
        this->y = y;
        this->z = z;
        this->d = d;
    }
};
bool operator<(const ban& a, const ban& b)
{
    return a.d > b.d;
}

bool c[N][N][4 + 1];

void solv()
{
    cin >> n >> m;
    cin >> A >> B >> C;
    cin >> k;
    queue<pair<int, int> > qq;
    for (int i = 1; i <= k; ++i)
    {
        cin >> x[i] >> y[i];
        cc[x[i]][y[i]] = true;
        dd[x[i]][y[i]] = 0;
        qq.push(m_p(x[i], y[i]));
    }

    while (!qq.empty())
    {
        int x = qq.front().fi;
        int y = qq.front().se;
        qq.pop();
        for (int i = 0; i < 4; ++i)
        {
            int hx = x + xx[i];
            int hy = y + yy[i];
            if (0 <= hx && hx <= n && 0 <= hy && hy <= m && !cc[hx][hy])
            {
                cc[hx][hy] = true;
                dd[hx][hy] = dd[x][y] + 1;
                qq.push(m_p(hx, hy));
            }
        }
    }

    priority_queue<ban> q;
    q.push(ban(x[1], y[1], 4, 0));
    while (!q.empty())
    {
        ban t = q.top();
        q.pop();
        if (c[t.x][t.y][t.z])
            continue;
        c[t.x][t.y][t.z] = true;
        if (t.x == x[k] && t.y == y[k])
        {
            cout << t.d << "\n";
            return;
        }
        q.push(ban(t.x, t.y, 4, t.d + dd[t.x][t.y] * 1LL * C));

        if (t.z < 4)
        {
            ban h = t;
            h.x += xx[t.z];
            h.y += yy[t.z];
            h.d += A;
            if (0 <= h.x && h.x <= n && 0 <= h.y && h.y <= m)
                q.push(h);
        }
        else
        {
            for (int i = 0; i < 4; ++i)
            {
                ban h = t;
                h.x += xx[i];
                h.y += yy[i];
                h.d += C;
                if (0 <= h.x && h.x <= n && 0 <= h.y && h.y <= m)
                    q.push(h);
            }
            for (int i = 0; i < 4; ++i)
            {
                ban h = t;
                h.d += B;
                h.z = i;
                q.push(h);
            }
        }
    }
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

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