結果
問題 |
No.1265 Balloon Survival
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:22:34 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,434 bytes |
コンパイル時間 | 364 ms |
コンパイル使用メモリ | 82,156 KB |
実行使用メモリ | 97,276 KB |
最終ジャッジ日時 | 2025-04-15 23:24:08 |
合計ジャッジ時間 | 6,875 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 9 WA * 23 |
ソースコード
import math from collections import deque def main(): import sys input = sys.stdin.read().split() idx = 0 N = int(input[idx]) idx +=1 x0 = int(input[idx]) y0 = int(input[idx+1]) idx +=2 balloons = [] for _ in range(N-1): x = int(input[idx]) y = int(input[idx+1]) idx +=2 balloons.append((x, y)) if N == 1: print(0) return # Compute t_i for each balloon t = [] for (x, y) in balloons: dx = x - x0 dy = y - y0 dist = math.hypot(dx, dy) t_i = dist / 2.0 t.append(t_i) # Build adjacency list for bipartite graph adj = [[] for _ in range(len(balloons))] for i in range(len(balloons)): xi, yi = balloons[i] for j in range(i+1, len(balloons)): xj, yj = balloons[j] dx = xi - xj dy = yi - yj dist_ij = math.hypot(dx, dy) t_ij = dist_ij / 2.0 if t_ij < min(t[i], t[j]): adj[i].append(j) adj[j].append(i) # Bipartite graph: split each node into left and right # Use Hopcroft-Karp algorithm # Each node is represented in left and right partitions # So node i in left is i, in right is len(balloons) + i size_left = len(balloons) size_right = len(balloons) graph = [[] for _ in range(size_left + size_right)] for i in range(len(balloons)): for j in adj[i]: graph[i].append(len(balloons) + j) graph[len(balloons) + j].append(i) # Hopcroft-Karp algorithm def hopcroft_karp(): pair_U = [-1] * (size_left + size_right) pair_V = [-1] * (size_left + size_right) dist = [0] * (size_left + size_right) def bfs(): queue = deque() for u in range(size_left): if pair_U[u] == -1: dist[u] = 0 queue.append(u) else: dist[u] = float('inf') dist_null = float('inf') while queue: u = queue.popleft() if dist[u] < dist_null: for v in graph[u]: if pair_V[v] == -1: dist_null = dist[u] + 1 elif dist[pair_V[v]] == float('inf'): dist[pair_V[v]] = dist[u] + 1 queue.append(pair_V[v]) return dist_null != float('inf') def dfs(u): for v in graph[u]: if pair_V[v] == -1 or (dist[pair_V[v]] == dist[u] + 1 and dfs(pair_V[v])): pair_U[u] = v pair_V[v] = u return True dist[u] = float('inf') return False result = 0 while bfs(): for u in range(size_left): if pair_U[u] == -1: if dfs(u): result +=1 return result max_matching = hopcroft_karp() # Each pair in bipartite graph corresponds to a pair in original graph, but each original edge is represented twice # So the actual maximum matching in the original graph is max_matching // 2 actual_matching = max_matching // 2 answer = (N-1) - 2 * actual_matching print(answer) if __name__ == "__main__": main()