結果

問題 No.3200 Sinking Islands
コンテスト
ユーザー YY-otter
提出日時 2025-07-02 06:26:08
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
Judge  
(最初)
実行時間 -
コード長 4,704 bytes
コンパイル時間 1,154 ms
コンパイル使用メモリ 107,924 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-07-03 16:52:10
合計ジャッジ時間 5,525 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 10 RE * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// 順序制約を扱う、拡張された重み付きUnion-Find構造体
struct DSU_Ordered {
    // 親要素を記録
    std::vector<int> parent;
    // 親に対するポテンシャル (pos(i) - pos(parent[i]))
    std::vector<long long> potential;
    // 各連結成分に含まれる点の番号の最小値
    std::vector<int> min_idx;
    // 各連結成分に含まれる点の番号の最大値
    std::vector<int> max_idx;

    // コンストラクタ
    DSU_Ordered(int n) {
        parent.resize(n + 1);
        std::iota(parent.begin(), parent.end(), 0);
        potential.assign(n + 1, 0);
        min_idx.resize(n + 1);
        std::iota(min_idx.begin(), min_idx.end(), 0);
        max_idx.resize(n + 1);
        std::iota(max_idx.begin(), max_idx.end(), 0);
    }

    // 根を探しながら、ポテンシャルを更新（経路圧縮）
    int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        int root = find(parent[i]);
        potential[i] += potential[parent[i]];
        parent[i] = root;
        return root;
    }

    // 2点間の相対距離を計算
    long long diff(int i, int j) {
        // findを呼び出すことで、iとjのポテンシャルが根からの相対距離に更新される
        find(i);
        find(j);
        return potential[j] - potential[i];
    }

    // 2つの点を情報dに基づいて連結する
    // pos(j) = pos(i) + d
    void unite(int i, int j, long long d) {
        int root_i = find(i);
        int root_j = find(j);

        if (root_i == root_j) {
            // --- 等式矛盾チェック ---
            // 既に同じ集合なのに、新しい情報が既存の関係と矛盾する場合は無視
            if (diff(i, j) != d) {
                return; // 矛盾するので無視
            }
        } else {
            // --- 順序矛盾チェック ---
            // これから連結した場合に、ある i_ < j_ で pos(j_) - pos(i_) < j_ - i_ とならないか？
            // 2つのグループの境界点についてチェックすれば十分
            
            // 連結した場合の、根と根の相対距離を計算
            // potential[root_j] = pos(root_j) - pos(root_i) となるようにしたい
            long long d_roots = potential[i] - potential[j] + d;

            int min_i_idx = min_idx[root_i];
            int max_i_idx = max_idx[root_i];
            int min_j_idx = min_idx[root_j];
            int max_j_idx = max_idx[root_j];

            // 境界点1: (max_i, min_j)
            if (max_i_idx < min_j_idx) {
                // 連結後の pos(min_j) - pos(max_i) を計算
                // pos(min_j) = pos(root_j) + potential[min_j]
                // pos(max_i) = pos(root_i) + potential[max_i]
                // 差分 = (pos(root_j) - pos(root_i)) + potential[min_j] - potential[max_i]
                long long boundary_diff = d_roots + diff(root_j, min_j_idx) - diff(root_i, max_i_idx);
                if (boundary_diff < min_j_idx - max_i_idx) {
                    return; // 順序矛盾なので無視
                }
            }
            
            // 境界点2: (max_j, min_i)
            if (max_j_idx < min_i_idx) {
                // 連結後の pos(min_i) - pos(max_j) を計算
                // 差分 = (pos(root_i) - pos(root_j)) + potential[min_i] - potential[max_j]
                long long boundary_diff = -d_roots + diff(root_i, min_i_idx) - diff(root_j, max_j_idx);
                 if (boundary_diff < min_i_idx - max_j_idx) {
                    return; // 順序矛盾なので無視
                }
            }

            // --- 矛盾がなかったので、実際に連結 ---
            // (簡単のため、常にroot_jをroot_iに繋ぐ)
            parent[root_j] = root_i;
            potential[root_j] = d_roots;
            min_idx[root_i] = std::min(min_idx[root_i], min_idx[root_j]);
            max_idx[root_i] = std::max(max_idx[root_i], max_idx[root_j]);
        }
    }
};

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

    int N, M;
    std::cin >> N >> M;

    DSU_Ordered dsu(N);

    for (int k = 0; k < M; ++k) {
        int u, v;
        long long d;
        std::cin >> u >> v >> d;
        dsu.unite(u, v, d);
    }

    int Q;
    std::cin >> Q;
    for (int k = 0; k < Q; ++k) {
        int u, v;
        std::cin >> u >> v;

        if (dsu.find(u) != dsu.find(v)) {
            std::cout << "Ambiguous\n";
        } else {
            std::cout << dsu.diff(u, v) << "\n";
        }
    }

    return 0;
}
0