結果
| 問題 | No.2353 Guardian Dogs in Spring |
| ユーザー |
 navel_tos
|
| 提出日時 | 2023-06-16 22:37:11 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,379 bytes |
| コンパイル時間 | 768 ms |
| コンパイル使用メモリ | 82,304 KB |
| 実行使用メモリ | 511,788 KB |
| 最終ジャッジ日時 | 2024-06-24 15:19:22 |
| 合計ジャッジ時間 | 4,998 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 152 ms
93,952 KB |
| testcase_01 | AC | 155 ms
88,552 KB |
| testcase_02 | AC | 151 ms
88,448 KB |
| testcase_03 | AC | 151 ms
88,448 KB |
| testcase_04 | AC | 152 ms
88,832 KB |
| testcase_05 | TLE | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
ソースコード
#yukicoder393D
'''
「近い奴とつねに向き合う」ってしょうもな貪欲法するか。
ただN=8000だとちょっと制約がきついなぁ。
え、この貪欲落ちるの？
えーTLE。かなしい。
どうしよう。最小全域木でも作る？
'''
from fractions import Fraction as Fc
from collections import defaultdict as dd, deque as dq
import heapq as hq
f=lambda:tuple(map(int,input().split()))
#直線の切片のx座標y座標を返す
def line(P,Q):
x1,y1=P; x2,y2=Q
if x1==x2: return (x1,10**18)
R=Fc(y2-y1,x2-x1); return (R,-R*x1+y1)
N=int(input()); N=N//2*2; P=[f() for _ in range(N)]; print(N//2)
Q=[]; G=[[] for _ in range(N)]; visited=[0]*N; visited[0]=1
for next in range(1,N):
hq.heappush(Q,((P[0][0]-P[next][0])**2+(P[0][1]-P[next][1])**2,next,0))
#MST
while Q:
dist,now,back=hq.heappop(Q)
if visited[now]: continue
G[now].append(back); G[back].append(now); visited[now]=1
for next in range(N):
if visited[next]: continue
hq.heappush(Q,((P[now][0]-P[next][0])**2+(P[now][1]-P[next][1])**2,next,now))
#答えを探索
Q=dq(); looked=[0]*N
for now in range(N):
if len(G[now])==1: Q.append(now)
while Q:
now=Q.popleft()
if looked[now]: continue
looked[now]=1
for next in G[now]:
if looked[next]: continue
print(now+1,next+1); looked[next]=1; break