結果
問題 |
No.1265 Balloon Survival
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:47:59 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,171 bytes |
コンパイル時間 | 159 ms |
コンパイル使用メモリ | 82,240 KB |
実行使用メモリ | 111,696 KB |
最終ジャッジ日時 | 2025-03-20 20:48:11 |
合計ジャッジ時間 | 4,731 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 4 WA * 28 |
ソースコード
from collections import deque import sys def main(): sys.setrecursionlimit(1 << 25) n_total = int(sys.stdin.readline()) points = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n_total)] if n_total == 1: print(0) return first_x, first_y = points[0] others = points[1:] m = len(others) if m == 0: print(0) return adj = [[] for _ in range(m)] d_j0_sq = [] # Precompute squared distances to the first balloon for x, y in others: dx = x - first_x dy = y - first_y d_sq = dx * dx + dy * dy d_j0_sq.append(d_sq) # Build adjacency list for j in range(m): dj0 = d_j0_sq[j] for k in range(m): if j == k: continue xj, yj = others[j] xk, yk = others[k] dx = xj - xk dy = yj - yk djk_sq = dx * dx + dy * dy if djk_sq <= dj0: adj[j].append(k) # Step 1: Compute finishing times using original graph visited = [False] * m order = [] for u in range(m): if not visited[u]: stack = [(u, False)] while stack: node, processed = stack.pop() if processed: order.append(node) continue if visited[node]: continue visited[node] = True stack.append((node, True)) # To process in the same order as recursive DFS, reverse the adjacency list for v in reversed(adj[node]): if not visited[v]: stack.append((v, False)) order.reverse() # Step 2: Assign components using reversed graph reversed_adj = [[] for _ in range(m)] for u in range(m): for v in adj[u]: reversed_adj[v].append(u) visited = [False] * m scc_id = [0] * m component_sizes = [] current_component = 0 for u in order: if not visited[u]: stack = [u] visited[u] = True component = [u] while stack: node = stack.pop() for v in reversed_adj[node]: if not visited[v]: visited[v] = True stack.append(v) component.append(v) for node in component: scc_id[node] = current_component component_sizes.append(len(component)) current_component += 1 # If no components with size >=2, the answer is m (remove all) marked_components = set() for i in range(len(component_sizes)): if component_sizes[i] >= 2: marked_components.add(i) if not marked_components: print(m) return # Build condensed adjacency condensed_adj = [[] for _ in range(current_component)] for u in range(m): cu = scc_id[u] for v in adj[u]: cv = scc_id[v] if cu != cv: condensed_adj[cu].append(cv) # Deduplicate the edges for i in range(current_component): condensed_adj[i] = list(set(condensed_adj[i])) # Build reversed condensed adjacency condensed_rev_adj = [[] for _ in range(current_component)] for u in range(current_component): for v in condensed_adj[u]: condensed_rev_adj[v].append(u) # BFS to find all components that can reach marked components in original DAG allowed = set() for s in marked_components: if s in allowed: continue queue = deque([s]) visited_in_bfs = set([s]) allowed.add(s) while queue: u = queue.popleft() for v in condensed_rev_adj[u]: if v not in visited_in_bfs: visited_in_bfs.add(v) allowed.add(v) queue.append(v) # Calculate the total allowed nodes total = 0 for comp in allowed: total += component_sizes[comp] print(m - total) if __name__ == "__main__": main()