Submission #1294331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294331		fairkrash	Soccer (JOI17_soccer)	C++20	35 / 100	3094 ms	19752 KiB

soccer

#include <bits/stdc++.h>
#include <random>

using namespace std;
using ll = long long;
using ld = long double;

ll INF = 1e18;


ll pref[270000];
ll dp[270000];
ll good[270000];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll h, w;
    cin >> h >> w;
    h++;
    w++;
    ll a, b, c;
    cin >> a >> b >> c;
    ll n;
    cin >> n;
    vector<pair<ll, ll>> s(n);
    vector<ll> v1;
    vector<ll> v2;
    for (ll i = 0; i < n; i++) {
        cin >> s[i].first >> s[i].second;
        v1.push_back(s[i].first);
        v2.push_back(s[i].second);
    }
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    v1.resize(unique(v1.begin(), v1.end()) - v1.begin());
    v2.resize(unique(v2.begin(), v2.end()) - v2.begin());
    for (ll i = 0; i < h * w; i++) {
        pref[i] = INF;
    }
    for (ll i = 0; i < n; i++) {
        pref[s[i].first * w + s[i].second] = 0;
    }
    {
        set<pair<ll, ll>> st;
        for (ll i = 0; i < n; i++) {
            st.insert({0, s[i].first * w + s[i].second});
        }
        while (!st.empty()) {
            ll i = st.begin()->second / w;
            ll j = st.begin()->second % w;
            st.erase(st.begin());
            for (ll ij = max(j - 1, 0ll); ij <= min(j + 1, w - 1); ij++) {
                if (pref[i * w + ij] > pref[i * w + j] + abs(ij - j) * c) {
                    st.erase({pref[i * w + ij], i * w + ij});
                    pref[i * w + ij] = pref[i * w + j] + abs(ij - j) * c;
                    st.insert({pref[i * w + ij], i * w + ij});
                }
            }
            for (ll ij = max(i - 1, 0ll); ij <= min(i + 1, h - 1); ij++) {
                if (pref[ij * w + j] > pref[i * w + j] + abs(ij - i) * c) {
                    st.erase({pref[ij * w + j], ij * w + j});
                    pref[ij * w + j] = pref[i * w + j] + abs(i - ij) * c;
                    st.insert({pref[ij * w + j], ij * w + j});
                }
            }
        }
    }
    {
        for (ll i = 0; i < h * w; i++) {
            dp[i] = INF;
        }
        dp[s[0].first * w + s[0].second] = 0;
        set<pair<ll, ll>> st;
        st.insert({0, s[0].first * w + s[0].second});
        while (!st.empty()) {
            ll i = st.begin()->second / w;
            ll j = st.begin()->second % w;
            if (dp[s[n - 1].first * w + s[n - 1].second] == st.begin()->first) {
                cout << dp[s[n - 1].first * w + s[n - 1].second] << endl;
                exit(0);
            }
            st.erase(st.begin());
            if (good[i * w + j] == 1) {
                for (ll ij1 = 0; ij1 < v1.size(); ij1++) {
                    ll ij = v1[ij1];
                    if (dp[ij * w + j] > dp[i * w + j] + abs(ij - i) * a + b + pref[ij * w + j]) {
                        st.erase({dp[ij * w + j], ij * w + j});
                        dp[ij * w + j] = dp[i * w + j] + abs(i - ij) * a + b + pref[ij * w + j];
                        st.insert({dp[ij * w + j], ij * w + j});
                    }
                    if (dp[ij * w + j] > dp[i * w + j] + abs(ij - i) * c) {
                        good[ij * w + j] = 3;
                        st.erase({dp[ij * w + j], ij * w + j});
                        dp[ij * w + j] = dp[i * w + j] + abs(i - ij) * c;
                        st.insert({dp[ij * w + j], ij * w + j});
                    }
                }
                continue;
            }
            if (good[i * w + j] == 3) {
                for (ll ij1 = 0; ij1 < v2.size(); ij1++) {
                    ll ij = v2[ij1];
                    if (dp[i * w + ij] > dp[i * w + j] + abs(ij - j) * a + b + pref[i * w + ij]) {
                        st.erase({dp[i * w + ij], i * w + ij});
                        dp[i * w + ij] = dp[i * w + j] + abs(ij - j) * a + b + pref[i * w + ij];
                        st.insert({dp[i * w + ij], i * w + ij});
                    }
                    if (dp[i * w + ij] > dp[i * w + j] + abs(ij - j) * c) {
                        good[i * w + ij] = 1;
                        st.erase({dp[i * w + ij], i * w + ij});
                        dp[i * w + ij] = dp[i * w + j] + abs(ij - j) * c;
                        st.insert({dp[i * w + ij], i * w + ij});
                    }
                }
                continue;
            }
            for (ll ij1 = 0; ij1 < v1.size(); ij1++) {
                ll ij = v1[ij1];
                if (dp[ij * w + j] > dp[i * w + j] + abs(ij - i) * a + b + pref[ij * w + j]) {
                    st.erase({dp[ij * w + j], ij * w + j});
                    dp[ij * w + j] = dp[i * w + j] + abs(i - ij) * a + b + pref[ij * w + j];
                    st.insert({dp[ij * w + j], ij * w + j});
                }
                if (dp[ij * w + j] > dp[i * w + j] + abs(ij - i) * c) {
                    good[ij * w + j] = 3;
                    st.erase({dp[ij * w + j], ij * w + j});
                    dp[ij * w + j] = dp[i * w + j] + abs(i - ij) * c;
                    st.insert({dp[ij * w + j], ij * w + j});
                }
            }
            for (ll ij1 = 0; ij1 < v2.size(); ij1++) {
                ll ij = v2[ij1];
                if (dp[i * w + ij] > dp[i * w + j] + abs(ij - j) * a + b + pref[i * w + ij]) {
                    st.erase({dp[i * w + ij], i * w + ij});
                    dp[i * w + ij] = dp[i * w + j] + abs(ij - j) * a + b + pref[i * w + ij];
                    st.insert({dp[i * w + ij], i * w + ij});
                }
                if (dp[i * w + ij] > dp[i * w + j] + abs(ij - j) * c) {
                    good[i * w + ij] = 1;
                    st.erase({dp[i * w + ij], i * w + ij});
                    dp[i * w + ij] = dp[i * w + j] + abs(ij - j) * c;
                    st.insert({dp[i * w + ij], i * w + ij});
                }
            }
        }
    }
}

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