Submission #758811

#	Time	Username	Problem	Language	Result	Execution time	Memory
758811		Kihihihi	Soccer (JOI17_soccer)	C++17	100 / 100	691 ms	39372 KiB

soccer

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <ctime>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <fstream>
#include <functional>
#include <complex>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

const long long INF = 1e18, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 18;
const long double EPS = 1e-9, PI = acos(-1);

const long long dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };

void solve()
{
    long long n, m, a, b, c, k;
    vector<pair<long long, long long>> v;
    cin >> n >> m >> a >> b >> c >> k;
    v.resize(k);
    n++; m++;
    for (long long i = 0; i < k; i++)
    {
        cin >> v[i].first >> v[i].second;
    }

    vector<vector<long long>> near(n, vector<long long>(m, INF));
    deque<pair<long long, long long>> bq;
    for (long long i = 0; i < k; i++)
    {
        near[v[i].first][v[i].second] = 0;
        bq.push_back({ v[i].first, v[i].second });
    }

    auto inside = [&](long long x, long long y) -> bool
    {
        return 0 <= x && x < n && 0 <= y && y < m;
    };

    while (bq.size())
    {
        auto [x, y] = bq.front();
        bq.pop_front();

        for (long long _ = 0; _ < 4; _++)
        {
            long long xx = x + dx[_], yy = y + dy[_];
            if (!inside(xx, yy) || near[xx][yy] != INF)
            {
                continue;
            }

            near[xx][yy] = near[x][y] + 1;
            bq.push_back({ xx, yy });
        }
    }

    vector<vector<vector<long long>>> dist(n, vector<vector<long long>>(m, vector<long long>(5, INF)));
    dist[v[0].first][v[0].second][4] = 0;

    set<tuple<long long, long long, long long, long long>> dq = { { 0, v[0].first, v[0].second, 4 } };
    while (dq.size())
    {
        auto [d, x, y, dir] = *dq.begin();
        dq.erase(dq.begin());

        if (dir == 4)
        {
            for (long long _ = 0; _ < 4; _++)
            {
                long long xx = x + dx[_], yy = y + dy[_];
                if (!inside(xx, yy))
                {
                    continue;
                }

                if (d + a + b < dist[xx][yy][_])
                {
                    dq.erase({ dist[xx][yy][_], xx, yy, _ });
                    dist[xx][yy][_] = d + a + b;
                    dq.insert({ dist[xx][yy][_], xx, yy, _ });
                }

                long long neutr = min(d + a + b + near[xx][yy] * c, d + c);
                if (neutr < dist[xx][yy][4])
                {
                    dq.erase({ dist[xx][yy][4], xx, yy, 4 });
                    dist[xx][yy][4] = neutr;
                    dq.insert({ dist[xx][yy][4], xx, yy, 4 });
                }
            }
            continue;
        }

        if (d + near[x][y] * c < dist[x][y][4])
        {
            dq.erase({ dist[x][y][4], x, y, 4 });
            dist[x][y][4] = d + near[x][y] * c;
            dq.insert({ dist[x][y][4], x, y, 4 });
        }

        long long xx = x + dx[dir], yy = y + dy[dir];
        if (!inside(xx, yy))
        {
            continue;
        }

        if (d + a < dist[xx][yy][dir])
        {
            dq.erase({ dist[xx][yy][dir], xx, yy, dir });
            dist[xx][yy][dir] = d + a;
            dq.insert({ dist[xx][yy][dir], xx, yy, dir });
        }
    }

    cout << dist[v[k - 1].first][v[k - 1].second][4] << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    srand(time(NULL));

    int tst = 1;
    //cin >> tst;
    while (tst--)
    {
        solve();
    }

    return 0;
}

/*
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀
⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀
⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀
⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀
⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁
⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀
⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀
⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀
⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀
⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀
⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀
⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀
⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀
⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀
⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧
⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘
⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀
⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
*/

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