結果
| 問題 |
No.1600 Many Shortest Path Problems
|
| コンテスト | |
| ユーザー |
 Ricky_pon
|
| 提出日時 | 2021-07-14 11:03:07 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 866 ms / 4,000 ms |
| コード長 | 8,898 bytes |
| コンパイル時間 | 1,943 ms |
| コンパイル使用メモリ | 104,456 KB |
| 最終ジャッジ日時 | 2025-01-23 01:00:00 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 51 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:301:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
301 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
main.cpp:305:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
305 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
main.cpp:335:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
335 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
main.cpp:338:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
338 | scanf("%d%d%d", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
ソースコード
// #include <bits/stdc++.h>
#include <atcoder/modint>
#include <iostream>
#include <cassert>
#include <vector>
template <class S, S (*op)(S, S), S (*e)()>
struct DualSegTree {
public:
DualSegTree() : DualSegTree(0) {}
DualSegTree(int n) : DualSegTree(std::vector<S>(n, e())) {}
DualSegTree(const std::vector<S> &v) : _n(int(v.size())) {
size = 1;
log = 0;
while (size < _n) size <<= 1, ++log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
S sum = e();
for (int i = 0; i <= log; i++) sum = op(sum, d[p >> i]);
return sum;
}
void prod(int l, int r, S x) {
assert(0 <= l && l <= r && r <= _n);
l += size;
r += size;
while (l < r) {
if (l & 1) d[l] = op(d[l], x), ++l;
if (r & 1) --r, d[r] = op(d[r], x);
l >>= 1;
r >>= 1;
}
}
void all_prod(S x) { d[1] = op(d[1], x); }
private:
int _n, size, log;
std::vector<S> d;
};
#include <atcoder/dsu>
#include <vector>
template <class T = int>
struct Edge {
int from, to;
T cost;
int idx;
Edge() = default;
Edge(int from, int to, T cost = 1, int idx = 0)
: from(from), to(to), cost(cost), idx(idx) {}
};
template <class T = int>
struct Graph {
std::vector<std::vector<Edge<T>>> es;
int edge_num;
Graph(int n) : edge_num(0) { es.resize(n); }
int size() { return es.size(); }
void add_edge(int from, int to, T cost = 1, int idx = 0) {
es[from].emplace_back(from, to, cost, idx);
++edge_num;
}
std::vector<Edge<T>> edges() {
std::vector<Edge<T>> res(edge_num);
for (int v = 0; v < (int)es.size(); ++v) {
for (auto& e : es[v]) res[e.idx] = e;
}
return res;
}
std::vector<Edge<T>>& operator[](int i) { return es[i]; }
};
#include <vector>
template <class T>
std::pair<T, std::vector<int>> kruscal(Graph<T> &gr) {
auto es = gr.edges();
std::sort(es.begin(), es.end(),
[](const Edge<> &a, const Edge<> &b) { return a.cost < b.cost; });
atcoder::dsu uf(gr.size());
T cost = 0;
std::vector<int> mst_es;
for (auto &e : es) {
if (uf.same(e.from, e.to)) continue;
uf.merge(e.from, e.to);
cost += e.cost;
mst_es.push_back(e.idx);
}
return {cost, mst_es};
}
#include <algorithm>
#include <cassert>
#include <vector>
template <class T>
bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <class T>
bool chmin(T &a, const T &b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T>
T div_floor(T a, T b) {
if (b < 0) a *= -1, b *= -1;
return a >= 0 ? a / b : (a + 1) / b - 1;
}
template <class T>
T div_ceil(T a, T b) {
if (b < 0) a *= -1, b *= -1;
return a > 0 ? (a - 1) / b + 1 : a / b;
}
template <typename T>
struct CoordComp {
std::vector<T> v;
bool sorted;
CoordComp() : sorted(false) {}
int size() { return v.size(); }
void add(T x) { v.push_back(x); }
void build() {
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());
sorted = true;
}
int get_idx(T x) {
assert(sorted);
return lower_bound(v.begin(), v.end(), x) - v.begin();
}
T &operator[](int i) { return v[i]; }
};
struct HeavyLightDecomposition {
public:
std::vector<int> idx, par, head, out;
HeavyLightDecomposition(Graph<> gr, int root = 0) {
idx.resize(gr.size());
par.resize(gr.size());
head.resize(gr.size());
out.resize(gr.size());
sz_dfs(gr, root, -1);
int cur = 0;
idx[root] = cur++;
head[root] = root;
hld_dfs(gr, root, -1, root, cur);
}
int lca(int u, int v) {
while (true) {
if (idx[u] > idx[v]) std::swap(u, v);
if (head[u] == head[v]) return u;
v = par[head[v]];
}
}
std::pair<std::vector<std::pair<int, int>>,
std::vector<std::pair<int, int>>>
get_path(int u, int v) {
std::vector<std::pair<int, int>> up, down;
while (true) {
if (head[u] == head[v]) {
if (idx[u] < idx[v])
down.emplace_back(idx[u], idx[v] + 1);
else
up.emplace_back(idx[v], idx[u] + 1);
std::reverse(up.begin(), up.end());
std::reverse(down.begin(), down.end());
return {up, down};
} else {
if (idx[u] < idx[v]) {
down.emplace_back(idx[head[v]], idx[v] + 1);
v = par[head[v]];
} else {
up.emplace_back(idx[head[u]], idx[u] + 1);
u = par[head[u]];
}
}
}
}
private:
int sz_dfs(Graph<> &gr, int v, int pv) {
int ret = 1, max_sz = 0;
for (int i = 0; i < (int)gr[v].size(); ++i) {
if (gr[v][i].to == pv) continue;
int tmp = sz_dfs(gr, gr[v][i].to, v);
ret += tmp;
if (chmax(max_sz, tmp)) std::swap(gr[v][0], gr[v][i]);
}
return ret;
}
void hld_dfs(Graph<> &gr, int v, int pv, int h, int &cur) {
for (auto &e : gr[v]) {
if (e.to == pv) continue;
idx[e.to] = cur++;
par[e.to] = v;
head[e.to] = (gr[v][0].to == e.to ? h : e.to);
hld_dfs(gr, e.to, v, head[e.to], cur);
}
out[v] = cur;
}
};
#define For(i, a, b) for (int i = (int)(a); (i) < (int)(b); ++(i))
#define rFor(i, a, b) for (int i = (int)(a)-1; (i) >= (int)(b); --(i))
#define rep(i, n) For(i, 0, n)
#define rrep(i, n) rFor(i, n, 0)
#define fi first
#define se second
using namespace std;
using lint = long long;
using pii = pair<int, int>;
using namespace atcoder;
using mint = modint1000000007;
constexpr int MAX = 200010;
int op(int a, int b) { return min(a, b); }
int e() { return MAX; }
int n, m;
mint pow2[MAX];
int dep[MAX * 2];
mint sum[MAX * 2];
void dfs(Graph<> &gr, int v, int pv) {
for (auto &e : gr[v]) {
if (e.to == pv) continue;
dep[e.to] = dep[v];
sum[e.to] = sum[v];
if (e.to < n) {
++dep[e.to];
sum[e.to] += pow2[e.cost];
}
dfs(gr, e.to, v);
}
}
int get_dist(HeavyLightDecomposition &hld, int x, int y) {
int lca = hld.lca(x, y);
return dep[x] + dep[y] - dep[lca] * 2;
}
mint get_sum(HeavyLightDecomposition &hld, int x, int y) {
int lca = hld.lca(x, y);
return sum[x] + sum[y] - sum[lca] * 2;
}
int main() {
pow2[0] = 1;
For(i, 1, MAX) pow2[i] = pow2[i - 1] * 2;
scanf("%d%d", &n, &m);
Graph gr(n);
rep(i, m) {
int a, b;
scanf("%d%d", &a, &b);
--a;
--b;
gr.add_edge(a, b, i + 1, i);
}
auto es = gr.edges();
auto mst_es = kruscal(gr).se;
Graph mst(n * 2 - 1);
int cur = n;
vector<int> conv(m, -1);
for (auto i : mst_es) {
const auto &e = es[i];
mst.add_edge(e.from, cur, e.cost);
mst.add_edge(cur, e.from, e.cost);
mst.add_edge(cur, e.to, e.cost);
mst.add_edge(e.to, cur, e.cost);
conv[e.idx] = cur++;
}
HeavyLightDecomposition hld(mst);
DualSegTree<int, op, e> st(2 * n - 1);
rep(i, m) if (conv[i] < 0) {
auto [up, down] = hld.get_path(es[i].from, es[i].to);
for (auto [l, r] : up) st.prod(l, r, i);
for (auto [l, r] : down) st.prod(l, r, i);
}
dfs(mst, 0, -1);
int q;
scanf("%d", &q);
rep(i, q) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
--x;
--y;
--z;
if (conv[z] < 0) {
printf("%u\n", get_sum(hld, x, y).val());
continue;
}
auto d1 = get_dist(hld, x, es[z].from) + 1 + get_dist(hld, es[z].to, y);
auto d2 = get_dist(hld, x, es[z].to) + 1 + get_dist(hld, es[z].from, y);
auto d3 = get_dist(hld, x, y);
if (d1 != d3 && d2 != d3) {
printf("%u\n", get_sum(hld, x, y).val());
continue;
}
int alt = st.get(hld.idx[conv[z]]);
if (alt == MAX) {
puts("-1");
continue;
}
auto &e = es[alt];
d1 = get_dist(hld, x, e.from) + 1 + get_dist(hld, e.to, y);
d2 = get_dist(hld, x, e.to) + 1 + get_dist(hld, e.from, y);
if (d2 < d1) swap(x, y);
printf("%u\n",
(get_sum(hld, x, e.from) + pow2[e.cost] + get_sum(hld, e.to, y))
.val());
}
}