結果

問題 No.1265 Balloon Survival
ユーザー stnkienstnkien
提出日時 2020-10-23 22:31:21
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,456 ms / 2,000 ms
コード長 793 bytes
コンパイル時間 202 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 136,192 KB
最終ジャッジ日時 2024-07-21 11:20:42
合計ジャッジ時間 18,511 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

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