結果
問題 |
No.1600 Many Shortest Path Problems
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()