Submission #1193236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193236		vux2code	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	247 ms	327680 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = numeric_limits<ll>::max() / 4;

vector<ll> dijkstra(int src, const vector<vector<pair<int,ll>>> &adj) {
    int n = adj.size();
    vector<ll> dist(n, INF);
    using pli = pair<ll,int>;
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    dist[src] = 0;
    pq.emplace(0, src);
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (auto &[v, w] : adj[u]) {
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    int S, T; cin >> S >> T;
    int U, V; cin >> U >> V;

    vector<vector<pair<int,ll>>> adj(N + 1);
    vector<tuple<int,int,ll>> edges;
    edges.reserve(M);
    for (int i = 0; i < M; ++i) {
        int a, b; ll c;
        cin >> a >> b >> c;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
        edges.emplace_back(a, b, c);
    }

    auto dS = dijkstra(S, adj);
    auto dT = dijkstra(T, adj);
    auto dU = dijkstra(U, adj);
    auto dV = dijkstra(V, adj);
    ll bestST = dS[T];

    // Build shortest-path DAG
    vector<vector<int>> dag(N + 1);
    for (auto &[a, b, c] : edges) {
        if (dS[a] + c + dT[b] == bestST) dag[a].push_back(b);
        if (dS[b] + c + dT[a] == bestST) dag[b].push_back(a);
    }

    // Mark nodes on some SP from S to T
    vector<char> fromS(N + 1, 0), toT(N + 1, 0);
    { // BFS from S
        queue<int> q;
        q.push(S); fromS[S] = 1;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : dag[u]) if (!fromS[v]) {
                fromS[v] = 1;
                q.push(v);
            }
        }
    }
    { // reverse-DAG BFS from T
        vector<vector<int>> dag_rev(N + 1);
        for (int u = 1; u <= N; ++u)
            for (int v : dag[u]) dag_rev[v].push_back(u);
        queue<int> q;
        q.push(T); toT[T] = 1;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : dag_rev[u]) if (!toT[v]) {
                toT[v] = 1;
                q.push(v);
            }
        }
    }

    // DFS to enumerate SP nodes in DAG (pruned to nodes reaching T)
    vector<int> ord(N + 1, 0), rev; rev.reserve(N + 1);
    vector<int> parent; parent.reserve(N + 1);
    int K = 0;
    function<void(int)> dfs = [&](int u) {
        ord[u] = ++K;
        rev.push_back(u);
        for (int v : dag[u]) {
            if (fromS[v] && toT[v] && !ord[v]) {
                dfs(v);
                parent.push_back(ord[u]);
            }
        }
    };
    dfs(S);
    // rev[i] is 0-indexed list of original nodes in DFS order; ord maps original to 1-based index
    // parent list is built in same order as rev except first element (S) has no parent
    vector<int> par(K+1);
    par[1] = 0;
    for (int i = 2; i <= K; ++i) par[i] = parent[i-2];

    // Build reduced graph for dominator computation
    vector<vector<int>> g(K+1), rg(K+1);
    for (int idx = 0; idx < K; ++idx) {
        int u = rev[idx];
        for (int v : dag[u]) {
            if (fromS[v] && toT[v]) {
                int iu = ord[u], iv = ord[v];
                g[iu].push_back(iv);
                rg[iv].push_back(iu);
            }
        }
    }

    // Lengauer-Tarjan dominator tree
    vector<int> sdom(K+1), dom(K+1), dsu(K+1), label(K+1);
    vector<vector<int>> bucket(K+1);
    for (int i = 1; i <= K; ++i) {
        sdom[i] = label[i] = dsu[i] = i;
        dom[i] = 0;
    }
    function<int(int)> find = [&](int u) {
        if (dsu[u] == u) return u;
        int v = find(dsu[u]);
        if (sdom[label[dsu[u]]] < sdom[label[u]]) label[u] = label[dsu[u]];
        return dsu[u] = v;
    };
    auto unite = [&](int u, int v){ dsu[v] = u; };

    for (int i = K; i >= 2; --i) {
        for (int j : rg[i]) {
            find(j);
            sdom[i] = min(sdom[i], sdom[label[j]]);
        }
        bucket[sdom[i]].push_back(i);
        unite(par[i], i);
        for (int j : bucket[par[i]]) {
            find(j);
            dom[j] = (sdom[label[j]] < sdom[j]) ? label[j] : par[i];
        }
        bucket[par[i]].clear();
    }
    for (int i = 2; i <= K; ++i) {
        if (dom[i] != sdom[i]) dom[i] = dom[dom[i]];
    }
    dom[1] = 0;

    // Build dominator tree children
    vector<vector<int>> tree(K+1);
    for (int i = 2; i <= K; ++i) tree[dom[i]].push_back(i);

    // Compute Bmin over dominator subtree: Bmin_tree[i] = min dV over rev-subtree
    vector<ll> Bmin_tree(K+1, INF);
    for (int i = 1; i <= K; ++i) {
        int u = rev[i-1];
        Bmin_tree[i] = dV[u];
    }
    function<void(int)> dfs_bmin = [&](int u) {
        for (int v : tree[u]) {
            dfs_bmin(v);
            Bmin_tree[u] = min(Bmin_tree[u], Bmin_tree[v]);
        }
    };
    dfs_bmin(1);

    // Compute answer
    ll answer = dU[V];
    for (int i = 1; i <= K; ++i) {
        int u = rev[i-1];
        if (dU[u] < INF && Bmin_tree[i] < INF) {
            answer = min(answer, dU[u] + Bmin_tree[i]);
        }
    }
    cout << answer << '\n';
    return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45