結果

問題 No.1600 Many Shortest Path Problems
ユーザー Ricky_ponRicky_pon
提出日時 2021-07-14 11:03:07
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 681 ms / 4,000 ms
コード長 8,898 bytes
コンパイル時間 2,226 ms
コンパイル使用メモリ 107,284 KB
実行使用メモリ 83,520 KB
最終ジャッジ日時 2023-09-16 08:36:22
合計ジャッジ時間 19,124 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
5,948 KB
testcase_01 AC 4 ms
5,936 KB
testcase_02 AC 4 ms
6,044 KB
testcase_03 AC 4 ms
6,008 KB
testcase_04 AC 681 ms
83,460 KB
testcase_05 AC 663 ms
83,444 KB
testcase_06 AC 4 ms
5,864 KB
testcase_07 AC 4 ms
5,788 KB
testcase_08 AC 4 ms
5,888 KB
testcase_09 AC 4 ms
5,904 KB
testcase_10 AC 196 ms
16,460 KB
testcase_11 AC 264 ms
17,596 KB
testcase_12 AC 402 ms
35,316 KB
testcase_13 AC 559 ms
62,664 KB
testcase_14 AC 666 ms
83,320 KB
testcase_15 AC 4 ms
5,932 KB
testcase_16 AC 4 ms
5,848 KB
testcase_17 AC 478 ms
48,656 KB
testcase_18 AC 650 ms
83,520 KB
testcase_19 AC 4 ms
5,848 KB
testcase_20 AC 4 ms
5,952 KB
testcase_21 AC 465 ms
48,568 KB
testcase_22 AC 4 ms
6,004 KB
testcase_23 AC 4 ms
5,840 KB
testcase_24 AC 667 ms
83,516 KB
testcase_25 AC 4 ms
5,932 KB
testcase_26 AC 4 ms
5,872 KB
testcase_27 AC 5 ms
5,788 KB
testcase_28 AC 4 ms
5,840 KB
testcase_29 AC 289 ms
58,744 KB
testcase_30 AC 301 ms
55,124 KB
testcase_31 AC 434 ms
48,596 KB
testcase_32 AC 471 ms
48,464 KB
testcase_33 AC 4 ms
5,960 KB
testcase_34 AC 4 ms
5,792 KB
testcase_35 AC 435 ms
83,492 KB
testcase_36 AC 265 ms
81,300 KB
testcase_37 AC 4 ms
5,844 KB
testcase_38 AC 261 ms
54,336 KB
testcase_39 AC 4 ms
5,952 KB
testcase_40 AC 296 ms
55,224 KB
testcase_41 AC 264 ms
58,748 KB
testcase_42 AC 275 ms
55,156 KB
testcase_43 AC 280 ms
55,244 KB
testcase_44 AC 332 ms
53,168 KB
testcase_45 AC 275 ms
58,520 KB
testcase_46 AC 281 ms
55,044 KB
testcase_47 AC 299 ms
55,128 KB
testcase_48 AC 334 ms
54,996 KB
testcase_49 AC 4 ms
5,796 KB
testcase_50 AC 4 ms
5,936 KB
testcase_51 AC 4 ms
5,896 KB
testcase_52 AC 4 ms
6,040 KB
testcase_53 AC 4 ms
5,908 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #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());
    }
}
0