#1140197 (C++17) No.1600 Many Shortest Path Problems

• 問題: No.1600 Many Shortest Path Problems
• ユーザー: limbo
• 提出日時: 2025-12-12 21:42:04
• 言語: C++17 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 371 ms / 4,000 ms
• コード長: 7,779 bytes
• コンパイル時間: 1,395 ms
• コンパイル使用メモリ: 91,320 KB
• 実行使用メモリ: 46,484 KB
• 最終ジャッジ日時: 2025-12-12 21:42:22
• 合計ジャッジ時間: 14,373 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 51

ソースコード

/**
 * Problem: Everything Everywhere All at Once
 * Input Format:
 * N M
 * A1 B1
 * ...
 * AM BM
 * Q
 * x1 y1 z1
 * ...
 * xQ yQ zQ
 *
 * Logic: Universal (Handles distinct weights, gaps, and arbitrary order).
 * - Implicit Weight: The i-th edge in input has weight 2^i.
 * - Logic preserves the "Universal" approach by sorting edges internally.
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

// =========================================================
// Constants
// =========================================================
const int MOD = 1e9 + 7;
const int LOGN = 20;
const int MAXN = 200005;

// =========================================================
// Data Structures
// =========================================================

struct Edge {
    int u, v, original_id;
    int c;             // Exponent cost (acts as weight comparator)
    long long w_mod;   // 2^c % MOD (for the final answer)
    bool in_mst;       // Flag: is this edge part of the MST?
};

// Global Data
vector<Edge> edges; // Will be sorted by weight
vector<pair<int, int>> adj[MAXN]; // MST Adjacency: {neighbor, edge_index_in_sorted_array}

// LCA & Tree Traversal
int up[MAXN][LOGN];
int depth[MAXN];
int tin[MAXN], tout[MAXN], timer;
long long dist_from_root[MAXN];
int edge_index_up[MAXN]; // Index in 'edges' array of the edge to parent

// Replacement Logic
// Maps 'original_id' -> 'original_id of replacement'
vector<int> best_replacement; 
// Map: Original ID -> Sorted Array Index
vector<int> original_to_sorted_idx;

// =========================================================
// Utilities
// =========================================================

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

struct DSU {
    vector<int> parent;
    DSU(int n) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) parent[root_i] = root_j;
    }
};

// =========================================================
// Tree Logic
// =========================================================

void dfs(int u, int p, int edge_idx, long long current_dist) {
    tin[u] = ++timer;
    depth[u] = depth[p] + 1;
    up[u][0] = p;
    dist_from_root[u] = current_dist;
    edge_index_up[u] = edge_idx;

    for (int i = 1; i < LOGN; i++) {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }

    for (auto& e : adj[u]) {
        int v = e.first;
        int idx = e.second;
        if (v != p) {
            dfs(v, u, idx, (current_dist + edges[idx].w_mod) % MOD);
        }
    }
    tout[u] = ++timer;
}

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int get_lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int i = LOGN - 1; i >= 0; i--) {
        if (!is_ancestor(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}

long long get_path_cost(int u, int v) {
    int lca = get_lca(u, v);
    long long res = (dist_from_root[u] + dist_from_root[v]) % MOD;
    long long sub = (2 * dist_from_root[lca]) % MOD;
    return (res - sub + MOD) % MOD;
}

// =========================================================
// Main
// =========================================================

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

    int N, M;
    if (!(cin >> N >> M)) return 0;

    // 1. Read Edges
    // Input format: u v (Implicit weight 2^i)
    for (int i = 1; i <= M; i++) {
        int u, v;
        cin >> u >> v;
        Edge e;
        e.u = u;
        e.v = v;
        e.c = i;               // Exponent is the index i
        e.w_mod = power(2, i); // Weight is 2^i
        e.original_id = i;     // Keep track of original index for queries
        e.in_mst = false;
        edges.push_back(e);
    }

    // 2. Sort Edges by Exponent C (Robust Logic)
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.c < b.c;
    });

    // Map: Original ID -> Index in the sorted 'edges' vector
    original_to_sorted_idx.resize(M + 1);
    for(int i = 0; i < M; i++) {
        original_to_sorted_idx[edges[i].original_id] = i;
    }

    // 3. Build MST (Kruskal's)
    DSU dsu_mst(N);
    for (int i = 0; i < M; i++) {
        if (dsu_mst.find(edges[i].u) != dsu_mst.find(edges[i].v)) {
            dsu_mst.unite(edges[i].u, edges[i].v);
            edges[i].in_mst = true;
            adj[edges[i].u].push_back({edges[i].v, i});
            adj[edges[i].v].push_back({edges[i].u, i});
        }
    }

    // 4. Build Tree Structure
    dfs(1, 1, -1, 0);

    // 5. Precalculate Replacements
    best_replacement.assign(M + 1, -1); 
    DSU dsu_cover(N);

    for (int i = 0; i < M; i++) {
        if (!edges[i].in_mst) {
            int u = edges[i].u;
            int v = edges[i].v;
            int lca = get_lca(u, v);

            auto cover_path = [&](int curr) {
                curr = dsu_cover.find(curr);
                while (depth[curr] > depth[lca]) {
                    int edge_idx_up = edge_index_up[curr]; // Index in sorted array
                    int orig_id = edges[edge_idx_up].original_id;
                    
                    if (best_replacement[orig_id] == -1) {
                        best_replacement[orig_id] = edges[i].original_id;
                    }
                    dsu_cover.unite(curr, up[curr][0]);
                    curr = dsu_cover.find(curr);
                }
            };
            cover_path(u);
            cover_path(v);
        }
    }

    // 6. Process Queries
    int Q;
    cin >> Q;
    while (Q--) {
        int x, y, z; 
        cin >> x >> y >> z; // z is the Original ID of the removed edge

        // Retrieve edge info using the map
        int k_sorted_idx = original_to_sorted_idx[z];
        Edge& removed_edge = edges[k_sorted_idx];

        long long base_dist = get_path_cost(x, y);

        if (!removed_edge.in_mst) {
            cout << base_dist << "\n";
            continue;
        }

        // Check if removed_edge is on the path
        int u = removed_edge.u;
        int v = removed_edge.v;
        if (depth[u] > depth[v]) swap(u, v);

        bool x_in_sub = is_ancestor(v, x);
        bool y_in_sub = is_ancestor(v, y);

        if (x_in_sub == y_in_sub) {
            // Not on path
            cout << base_dist << "\n";
        } else {
            // On path - check replacement
            int rep_orig_id = best_replacement[z];

            if (rep_orig_id == -1) {
                cout << "-1\n";
            } else {
                int rep_idx = original_to_sorted_idx[rep_orig_id];
                Edge& rep_edge = edges[rep_idx];

                int rx = rep_edge.u;
                int ry = rep_edge.v;
                
                long long segment1, segment2;
                // Connect x side to correct end of replacement edge
                if (is_ancestor(v, rx) == x_in_sub) {
                    segment1 = get_path_cost(x, rx);
                    segment2 = get_path_cost(y, ry);
                } else {
                    segment1 = get_path_cost(x, ry);
                    segment2 = get_path_cost(y, rx);
                }

                long long ans = (segment1 + segment2 + rep_edge.w_mod) % MOD;
                cout << ans << "\n";
            }
        }
    }

    return 0;
}