結果

問題 No.1265 Balloon Survival
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0