結果
| 問題 | No.2221 Set X |
| コンテスト | |
| ユーザー |
 limbo
|
| 提出日時 | 2025-12-12 21:26:32 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 8,402 bytes |
| 記録 | |
| コンパイル時間 | 1,062 ms |
| コンパイル使用メモリ | 92,996 KB |
| 実行使用メモリ | 15,304 KB |
| 最終ジャッジ日時 | 2025-12-12 21:26:43 |
| 合計ジャッジ時間 | 9,076 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 1 RE * 2 |
| other | WA * 16 RE * 10 TLE * 1 -- * 13 |
ソースコード
/**
* Problem: Everything Everywhere All at Once
* Language: C++20 (Standard)
* Complexity: O(M log M + Q log N)
* * Logic:
* 1. Build MST (Unique due to distinct 2^C weights).
* 2. Precompute LCA and path distances.
* 3. Precompute "Best Replacement Edge" for every MST edge using DSU-on-Tree.
* 4. Answer queries based on whether the removed edge is on the shortest path.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
// =========================================================
// Constants and Modular Arithmetic
// =========================================================
const int MOD = 1e9 + 7;
const long long INF_LL = 1e18; // Just a placeholder, not used for actual logic
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;
}
// =========================================================
// Data Structures
// =========================================================
struct Edge {
int u, v, id;
int c; // Exponent (used for comparison)
long long w_mod; // 2^c % MOD (used for answer)
bool is_mst_edge; // Is this edge part of the MST?
// Sort edges by exponent C
bool operator<(const Edge& other) const {
return c < other.c;
}
};
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;
}
}
};
// =========================================================
// Global Variables
// =========================================================
const int MAXN = 200005;
const int LOGN = 20;
vector<Edge> all_edges; // 1-based indexing matches input
vector<pair<int, int>> mst_adj[MAXN]; // {neighbor, edge_index}
int mst_edge_index_up[MAXN]; // Index of edge connecting node to its parent
// LCA and Tree Traversal
int up[MAXN][LOGN];
int depth[MAXN];
int tin[MAXN], tout[MAXN];
int timer;
long long dist_from_root[MAXN]; // Path cost from root % MOD
// Replacement Logic
int best_replacement[MAXN]; // best_replacement[k] = index of edge that replaces MST edge k
// =========================================================
// Tree Functions
// =========================================================
void dfs_lca(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;
mst_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& edge : mst_adj[u]) {
int v = edge.first;
int idx = edge.second;
if (v != p) {
dfs_lca(v, u, idx, (current_dist + all_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 cost = (dist_from_root[u] + dist_from_root[v]) % MOD;
long long sub = (2 * dist_from_root[lca]) % MOD;
return (cost - sub + MOD) % MOD;
}
// =========================================================
// Main Solver
// =========================================================
int main() {
// Fast I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M, Q;
if (!(cin >> N >> M >> Q)) return 0;
all_edges.resize(M + 1);
for (int i = 1; i <= M; i++) {
all_edges[i].id = i;
cin >> all_edges[i].u >> all_edges[i].v >> all_edges[i].c;
all_edges[i].w_mod = power(2, all_edges[i].c);
all_edges[i].is_mst_edge = false;
}
// 1. Kruskal's Algorithm to build MST
// We sort indices based on edge cost (exponent C)
vector<int> sorted_indices(M);
iota(sorted_indices.begin(), sorted_indices.end(), 1);
sort(sorted_indices.begin(), sorted_indices.end(), [](int a, int b) {
return all_edges[a].c < all_edges[b].c;
});
DSU dsu_mst(N);
for (int idx : sorted_indices) {
int u = all_edges[idx].u;
int v = all_edges[idx].v;
if (dsu_mst.find(u) != dsu_mst.find(v)) {
dsu_mst.unite(u, v);
all_edges[idx].is_mst_edge = true;
mst_adj[u].push_back({v, idx});
mst_adj[v].push_back({u, idx});
}
}
// 2. Build LCA table and Tree properties
// Root at 1 (Graph is connected)
dfs_lca(1, 1, -1, 0);
// 3. Precalculate Replacement Edges
// We iterate through non-MST edges from smallest to largest.
// Each non-MST edge covers a path in the tree. We use a DSU to efficiently
// jump over edges that are already covered.
fill(best_replacement, best_replacement + M + 1, -1);
DSU dsu_cover(N); // Used to compress paths on the tree
for (int idx : sorted_indices) {
if (!all_edges[idx].is_mst_edge) {
int u = all_edges[idx].u;
int v = all_edges[idx].v;
int lca = get_lca(u, v);
// Cover path from u to LCA
// Find the highest uncovered node in u's chain
int curr = dsu_cover.find(u);
while (depth[curr] > depth[lca]) {
int edge_above = mst_edge_index_up[curr];
if (best_replacement[edge_above] == -1) {
best_replacement[edge_above] = idx;
}
// Union with parent to skip this node next time
dsu_cover.unite(curr, up[curr][0]);
curr = dsu_cover.find(curr);
}
// Cover path from v to LCA
curr = dsu_cover.find(v);
while (depth[curr] > depth[lca]) {
int edge_above = mst_edge_index_up[curr];
if (best_replacement[edge_above] == -1) {
best_replacement[edge_above] = idx;
}
dsu_cover.unite(curr, up[curr][0]);
curr = dsu_cover.find(curr);
}
}
}
// 4. Answer Queries
for (int i = 0; i < Q; i++) {
int A, B, K;
cin >> A >> B >> K;
long long base_cost = get_path_cost(A, B);
// Case 1: The removed edge is NOT in the MST.
// The shortest path (which is the MST path) remains valid.
if (!all_edges[K].is_mst_edge) {
cout << base_cost << "\n";
continue;
}
// Case 2: The removed edge IS in the MST.
// We need to check if it lies on the unique path between A and B.
int u = all_edges[K].u;
int v = all_edges[K].v;
// Assume v is the deeper node (child)
if (depth[u] > depth[v]) swap(u, v);
// K is on the path A-B if and only if:
// One of A or B is in v's subtree, and the other is NOT.
bool a_in_subtree = is_ancestor(v, A);
bool b_in_subtree = is_ancestor(v, B);
if (a_in_subtree == b_in_subtree) {
// K is NOT on the path. The MST path is still valid.
cout << base_cost << "\n";
} else {
// K IS on the path. We must use the replacement edge.
int rep_idx = best_replacement[K];
if (rep_idx == -1) {
// No replacement edge exists -> Graph becomes disconnected
cout << "-1\n";
} else {
long long cost_removed = all_edges[K].w_mod;
long long cost_added = all_edges[rep_idx].w_mod;
long long ans = (base_cost - cost_removed + cost_added) % MOD;
if (ans < 0) ans += MOD;
cout << ans << "\n";
}
}
}
return 0;
}