結果
| 問題 | No.1600 Many Shortest Path Problems |
| コンテスト | |
| ユーザー |
 limbo
|
| 提出日時 | 2025-12-12 21:35:30 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 379 ms / 4,000 ms |
| コード長 | 7,963 bytes |
| 記録 | |
| コンパイル時間 | 1,222 ms |
| コンパイル使用メモリ | 86,996 KB |
| 実行使用メモリ | 46,308 KB |
| 最終ジャッジ日時 | 2025-12-12 21:35:45 |
| 合計ジャッジ時間 | 14,098 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 51 |
ソースコード
/**
* Problem: Everything Everywhere All at Once (Polygon Version)
* Language: C++20
* Input Format:
* N M
* A1 B1
* ...
* AM BM
* Q
* x1 y1 z1
* ...
* xQ yQ zQ
* * Weight Logic: The i-th edge (1-based index) has weight 2^i.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
// =========================================================
// Constants & Globals
// =========================================================
const int MOD = 1e9 + 7;
const int MAXN = 200005;
const int LOGN = 20;
struct Edge {
int u, v, id;
long long w_mod; // 2^id % MOD
bool in_mst;
};
// Global Arrays
vector<Edge> edges;
vector<pair<int, int>> tree_adj[MAXN]; // {neighbor, edge_index}
long long pow2[MAXN]; // Precomputed powers of 2
// LCA & Tree Traversal
int up[MAXN][LOGN];
int depth[MAXN];
int tin[MAXN], tout[MAXN], timer;
long long dist_from_root[MAXN]; // Path cost from root % MOD
int edge_index_up[MAXN]; // Index of edge connecting u to parent
// Replacement Logic
int best_replacement[MAXN]; // Stores the ID of the replacement edge
// =========================================================
// Data Structures
// =========================================================
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 Functions (LCA, DFS)
// =========================================================
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 : tree_adj[u]) {
int v = e.first;
int idx = e.second;
if (v != p) {
// Calculate distance down the tree
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 Solver
// =========================================================
int main() {
// Fast I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
if (!(cin >> N >> M)) return 0;
// Precompute powers of 2 for weights
pow2[0] = 1;
for (int i = 1; i <= M; i++) pow2[i] = (pow2[i - 1] * 2) % MOD;
edges.resize(M + 1);
// 1. Read Edges & Build MST implicitly
// Since edge i has weight 2^i, edges are ALREADY sorted by weight.
// We can run Kruskal's directly as we read input or in a simple 1..M loop.
DSU dsu_mst(N);
for (int i = 1; i <= M; i++) {
edges[i].id = i;
cin >> edges[i].u >> edges[i].v;
edges[i].w_mod = pow2[i]; // Weight is 2^i
edges[i].in_mst = false;
// Kruskal's Step: Attempt to add edge 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;
tree_adj[edges[i].u].push_back({edges[i].v, i});
tree_adj[edges[i].v].push_back({edges[i].u, i});
}
}
// 2. Build Tree Structure (Root at 1)
dfs(1, 1, -1, 0);
// 3. Precompute Replacements
// Iterate non-MST edges from smallest weight (smallest index) to largest.
// Use DSU on Tree to cover paths.
fill(best_replacement, best_replacement + M + 1, -1);
DSU dsu_cover(N);
for (int i = 1; i <= M; i++) {
if (!edges[i].in_mst) {
int u = edges[i].u;
int v = edges[i].v;
int lca = get_lca(u, v);
// Lambda to crawl up the tree and mark edges
auto cover_path = [&](int curr) {
curr = dsu_cover.find(curr);
while (depth[curr] > depth[lca]) {
int edge_up = edge_index_up[curr];
if (best_replacement[edge_up] == -1) {
best_replacement[edge_up] = i; // Store index of replacement edge
}
dsu_cover.unite(curr, up[curr][0]); // Compress path
curr = dsu_cover.find(curr);
}
};
cover_path(u);
cover_path(v);
}
}
// 4. Process Queries
int Q;
cin >> Q;
while (Q--) {
int x, y, z;
cin >> x >> y >> z;
// Base Distance on the full MST
long long base_dist = get_path_cost(x, y);
// Case 1: The removed edge z is NOT in the MST
// The shortest path (MST path) is unaffected.
if (!edges[z].in_mst) {
cout << base_dist << "\n";
continue;
}
// Case 2: The removed edge z IS in the MST
// We need to check if z lies on the simple path between x and y.
int u = edges[z].u;
int v = edges[z].v;
if (depth[u] > depth[v]) swap(u, v);
// v is now the child; the edge is effectively (parent[v] -> v)
// The edge z is on the x-y path IFF exactly one of x, y is in v's subtree.
bool x_in_sub = is_ancestor(v, x);
bool y_in_sub = is_ancestor(v, y);
if (x_in_sub == y_in_sub) {
// Edge z is in MST but NOT on the path x-y. Path is safe.
cout << base_dist << "\n";
} else {
// Edge z is critical for this path. Need replacement.
int rep_idx = best_replacement[z];
if (rep_idx == -1) {
cout << "-1\n"; // Graph disconnected
} else {
// We have a replacement edge (rx, ry)
int rx = edges[rep_idx].u;
int ry = edges[rep_idx].v;
long long w_rep = edges[rep_idx].w_mod;
long long w_removed = edges[z].w_mod;
// To correctly compute the new path length without subtraction issues:
// New Path = Path(x -> rx) + Weight(rx, ry) + Path(ry -> y)
// BUT we need to know which end of the replacement connects to x's component.
// x is in v's subtree if x_in_sub is true.
// rx is in v's subtree if is_ancestor(v, rx) is true.
// If x and rx are on the same side of the cut, we connect x->rx and y->ry.
// Otherwise cross-connect x->ry and y->rx.
long long segment1, segment2;
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 + w_rep) % MOD;
cout << ans << "\n";
}
}
}
return 0;
}