Submission #1188619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188619		jerzyk	Soccer (JOI17_soccer)	C++20	100 / 100	352 ms	19732 KiB

soccer

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1'000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1'000'000'007LL;
const int N = 507;
vector<pair<int, int>> roza;
int d1[N][N];
ll dis[N][N][2 + 4];

void DoRoza()
{
    roza.pb(pair{-1, 0});
    roza.pb(pair{0, -1});
    roza.pb(pair{1, 0});
    roza.pb(pair{0, 1});
}

void BFS(int n, int m)
{
    int i, j;
    queue<pair<int, int>> q;
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= m; ++j)
            if(d1[i][j] == 0) q.push(pair{i, j});
    while((int)q.size() > 0)
    {
        i = q.front().st; j = q.front().nd;
        q.pop();
        for(int l = 0; l < (int)roza.size(); ++l)
        {
            int ni = i + roza[l].st, nj = j + (int)roza[l].nd;
            if(ni < 0 || ni > n || nj < 0 || nj > m) continue;
            if(d1[ni][nj] > d1[i][j] + 1)
            {
                d1[ni][nj] = d1[i][j] + 1;
                q.push(pair{ni, nj});
            }
        }
    }
}

void Dijkstra(int n, int m, ll A, ll B, ll C)
{
    priority_queue<pair<ll, pair<pair<int, int>, int>>> q;
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= m; ++j)
            if(dis[i][j][0] == 0)
                q.push(pair{0, pair{pair{i, j}, 0}});
    while((int)q.size() > 0)
    {
        int i = q.top().nd.st.st, j = q.top().nd.st.nd, r = q.top().nd.nd;
        ll d = -q.top().st, nd;
        q.pop();
        if(dis[i][j][r] != d)
            continue;
        //cout << "D: " << i << " " << j << " " << r << " : " << dis[i][j][r] << "\n";
        if(r == 0)
        {
            nd = d + C * (ll)d1[i][j];
            if(dis[i][j][1] > nd)
            {
                dis[i][j][1] = nd;
                q.push(pair{-nd, pair{pair{i, j}, 1}});
            }
            continue;
        }
        if(r == 1)
        {
            if(dis[i][j][0] > d)
            {
                dis[i][j][0] = d;
                q.push(pair{-d, pair{pair{i, j}, 0}});
            }
            nd = d + C;
            for(int l = 0; l < (int)roza.size(); ++l)
            {
                int ni = i + roza[l].st, nj = j + (int)roza[l].nd;
                if(ni < 0 || ni > n || nj < 0 || nj > m) continue;
                if(dis[ni][nj][1] > nd)
                {
                    dis[ni][nj][1] = nd;
                    q.push(pair{-nd, pair{pair{ni, nj}, 1}});
                }
            }
            nd = d + A + B;
            for(int l = 0; l < (int)roza.size(); ++l)
            {
                int ni = i + roza[l].st, nj = j + (int)roza[l].nd;
                if(ni < 0 || ni > n || nj < 0 || nj > m) continue;
                if(dis[ni][nj][2 + l] > nd)
                {
                    dis[ni][nj][2 + l] = nd;
                    q.push(pair{-nd, pair{pair{ni, nj}, 2 + l}});
                }
            }
            continue;
        }
        if(dis[i][j][0] > d)
        {
            dis[i][j][0] = d;
            q.push(pair{-d, pair{pair{i, j}, 0}});
        }
        int ni = i + roza[r - 2].st, nj = j + (int)roza[r - 2].nd;
        if(ni < 0 || ni > n || nj < 0 || nj > m) continue;
        nd = d + A;
        if(dis[ni][nj][r] > nd)
        {
            dis[ni][nj][r] = nd;
            q.push(pair{-nd, pair{pair{ni, nj}, r}});
        }
    }
}

void Solve()
{
    int n, m, il, a, b;
    ll A, B, C;
    cin >> n >> m;
    cin >> A >> B >> C;
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= m; ++j)
            d1[i][j] = II;
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= m; ++j)
            for(int r = 0; r < 6; ++r)
                dis[i][j][r] = I;
    cin >> il;
    for(int i = 1; i <= il; ++i)
    {
        cin >> a >> b;
        d1[a][b] = 0;
        if(i == 1)
            dis[a][b][0] = 0LL;
    }
    BFS(n, m);
    Dijkstra(n, m, A, B, C);
    ll ans = dis[a][b][0];
    cout << ans << "\n";
}

int main()
{
    DoRoza();
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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