結果

問題 No.1600 Many Shortest Path Problems
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:27:10
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,519 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 82,428 KB
実行使用メモリ 312,872 KB
最終ジャッジ日時 2025-06-12 14:27:40
合計ジャッジ時間 8,096 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 4 TLE * 1 -- * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0

    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1

    edges = []
    for i in range(1, M+1):
        A = int(data[idx])-1
        idx += 1
        B = int(data[idx])-1
        idx += 1
        edges.append((A, B))

    Q = int(data[idx])
    idx +=1

    queries = []
    for _ in range(Q):
        x = int(data[idx])-1
        idx +=1
        y = int(data[idx])-1
        idx +=1
        z = int(data[idx])-1
        idx +=1
        queries.append((x, y, z))

    MOD = 10**9 +7

    for q in queries:
        x, y, z = q
        low = 0
        high = M
        ans_i = -1

        while low <= high:
            mid = (low + high) // 2

            uf = {}
            def find(u):
                if u not in uf:
                    uf[u] = u
                while uf[u] != u:
                    uf[u] = uf[uf[u]]
                    u = uf[u]
                return u

            def union(u, v):
                u_root = find(u)
                v_root = find(v)
                if u_root == v_root:
                    return
                uf[v_root] = u_root

            for i in range(mid):
                A, B = edges[i]
                union(A, B)

            if mid ==0:
                connected_with_z = (x == y)
            else:
                connected_with_z = find(x) == find(y)

            if mid < z:
                if connected_with_z:
                    ans_i = mid
                    high = mid -1
                else:
                    low = mid +1
            else:
                temp_edges = edges[:mid]
                if z < mid:
                    temp_edges = [e for i, e in enumerate(edges[:mid]) if i != z]

                uf2 = {}
                def find2(u):
                    if u not in uf2:
                        uf2[u] = u
                    while uf2[u] != u:
                        uf2[u] = uf2[uf2[u]]
                        u = uf2[u]
                    return u

                def union2(u, v):
                    u_root = find2(u)
                    v_root = find2(v)
                    if u_root == v_root:
                        return
                    uf2[v_root] = u_root

                for A, B in temp_edges:
                    union2(A, B)

                connected_without_z = (find2(x) == find2(y))

                if connected_without_z:
                    ans_i = mid
                    high = mid -1
                else:
                    low = mid +1

        if ans_i == -1:
            print(-1)
            continue

        total = 0
        path_edges = []
        visited = set()
        stack = [(x, 0)]
        found = False

        while stack:
            u, current = stack.pop()
            if u == y:
                found = True
                break
            if u in visited:
                continue
            visited.add(u)
            for i in range(ans_i):
                A, B = edges[i]
                if u == A:
                    v = B
                elif u == B:
                    v = A
                else:
                    continue
                if i == z:
                    continue
                new_current = current | (1 << (i+1))
                stack.append((v, new_current))

        if found:
            print(current % MOD)
        else:
            print(-1)

if __name__ == '__main__':
    main()
0