Submission #591606

#	Time	Username	Problem	Language	Result	Execution time	Memory
591606		piOOE	Olympic Bus (JOI20_ho_t4)	C++17	37 / 100	1094 ms	3792 KiB

ho_t4

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 200, M = 50000;
const ll infL = 3e18;

bool in_s_to_all[M], in_n_to_all[M], in_all_to_s[M], in_all_to_n[M], used[N];
ll dist_s_to_all[N], dist_n_to_all[N], dist_all_to_s[N], dist_all_to_n[N], D_s_all[N], D_all_s[N], D_n_all[N], D_all_n[N];

int A[M], B[M], W[M], D[M], P[M], revP[M], n, m;

vector<pair<int, int>> newg[N];

void dijkstra(int s, vector<pair<int, int>> g[], ll dist[], bool need, bool in[]) {
    fill(dist, dist + n, infL);
    dist[s] = 0;
    set<pair<ll, int>> st;
    st.insert({0, s});
    while (!st.empty()) {
        auto [ww, x] = *st.begin();
        st.erase(st.begin());
        for (auto [to, i]: g[x]) {
            if (dist[to] > dist[x] + W[i]) {
                st.erase({dist[to], to});
                dist[to] = dist[x] + W[i];
                st.insert({dist[to], to});
            }
        }
    }
    if (need) {
        for (int i = 0; i < n; ++i) {
            newg[i].clear();
        }
        for (int i = 0; i < n; ++i) {
            for (auto [to, j]: g[i]) {
                if (dist[to] == dist[i] + W[j]) {
                    newg[i].emplace_back(to, j);
                }
            }
        }
        memset(used, 0, sizeof(used[0]) * n);
        function<void(int)> dfs = [&](int v) {
            used[v] = true;
            for (auto [to, i]: newg[v]) {
                if (!used[to]) {
                    in[i] = true;
                    dfs(to);
                }
            }
        };
        dfs(s);
    }
}

vector<pair<int, int>> g[N], revg[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> A[i] >> B[i] >> W[i] >> D[i];
        --A[i], --B[i];
        P[i] = (int) g[A[i]].size();
        revP[i] = (int) revg[B[i]].size();
        g[A[i]].emplace_back(B[i], i);
        revg[B[i]].emplace_back(A[i], i);
    }
    dijkstra(0, g, dist_s_to_all, true, in_s_to_all);
    dijkstra(0, revg, dist_all_to_s, true, in_all_to_s);
    dijkstra(n - 1, g, dist_n_to_all, true, in_n_to_all);
    dijkstra(n - 1, revg, dist_all_to_n, true, in_all_to_n);
    ll ans = infL;
    ans = min(ans, dist_s_to_all[n - 1] + dist_n_to_all[0]);
    for (int i = 0; i < m; ++i) {
        {
            swap(g[A[i]][P[i]], g[A[i]].back());
            g[A[i]].pop_back();
            g[B[i]].emplace_back(A[i], i);
        }
        {
            swap(revg[B[i]][revP[i]], revg[B[i]].back());
            revg[B[i]].pop_back();
            revg[A[i]].emplace_back(B[i], i);
        }
        ll val_s_all_n, val_s_all_b, val_all_n_a, val_n_all_0, val_n_all_b, val_all_s_a;
        if (in_s_to_all[i]) {
            dijkstra(0, g, D_s_all, false, in_s_to_all);
            val_s_all_n = D_s_all[n - 1];
            val_s_all_b = D_s_all[B[i]];
        } else {
            val_s_all_n = dist_s_to_all[n - 1];
            val_s_all_b = dist_s_to_all[B[i]];
        }
        if (in_all_to_s[i]) {
            dijkstra(0, revg, D_all_s, false, in_all_to_s);
            val_all_s_a = D_all_s[A[i]];
        } else {
            val_all_s_a = dist_all_to_s[A[i]];
        }
        if (in_n_to_all[i]) {
            dijkstra(n - 1, g, D_n_all, false, in_n_to_all);
            val_n_all_0 = D_n_all[0];
            val_n_all_b = D_n_all[B[i]];
        } else {
            val_n_all_0 = dist_n_to_all[0];
            val_n_all_b = dist_n_to_all[B[i]];
        }
        if (in_all_to_n[i]) {
            dijkstra(n - 1, revg, D_all_n, false, in_all_to_n);
            val_all_n_a = D_all_n[A[i]];
        } else {
            val_all_n_a = dist_all_to_n[A[i]];
        }
        ans = min(ans, D[i] + min(val_s_all_n, val_s_all_b + W[i] + val_all_n_a) +
                       min(val_n_all_0, val_n_all_b + W[i] + val_all_s_a));
        {
            g[A[i]].emplace_back(B[i], i);
            swap(g[A[i]][P[i]], g[A[i]].back());
            g[B[i]].pop_back();
        }
        {
            revg[B[i]].emplace_back(A[i], i);
            swap(revg[B[i]][revP[i]], revg[B[i]].back());
            revg[A[i]].pop_back();
        }
    }
    cout << (ans == infL ? -1 : ans);
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 0 / 63