結果

問題 No.1265 Balloon Survival
ユーザー stnkien
提出日時 2020-10-23 22:31:21
言語 Python3
(3.15.2 + numpy 2.5.4 + scipy 1.18.1 + ACL)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 882 ms / 2,000 ms
+ 377µs
コード長 793 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 56 ms
コンパイル使用メモリ 14,848 KB
実行使用メモリ 112,384 KB
最終ジャッジ日時 2026-11-13 10:41:02
合計ジャッジ時間 13,731 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
N = int(input())
X = [tuple(map(int, line.split())) for line in sys.stdin.buffer.readlines()]

INF = 1<<60
D = [[INF]*N for _ in [0]*N]

for i in range(N):
    x, y = X[i]
    for j in range(i+1, N):
        u, v = X[j]
        D[i][j] = D[j][i] = (x-u)**2 + (y-v)**2

D = [sorted((d, j) for j, d in enumerate(Di))[:-1] for Di in D]

status = [0]*N
status[0] = 1

def dfs(i=0):
    cnt = 0
    for d, j in D[i]:
        if status[j] == 2:
            continue
        elif status[j] == 1:
            if j == 0: cnt += 1
            else: status[j] = 2
            status[i] = 2
            return cnt
        status[j] = 1
        cnt += dfs(j)
        if status[i] == 2:
            break
    return cnt

print(dfs())
0