結果

問題 No.2909 Imaginary Summer
ユーザー 👑 p-adicp-adic
提出日時 2024-09-27 07:29:22
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,751 bytes
コンパイル時間 408 ms
コンパイル使用メモリ 82,264 KB
実行使用メモリ 277,860 KB
最終ジャッジ日時 2024-10-02 17:32:29
合計ジャッジ時間 28,521 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
53,920 KB
testcase_01 AC 35 ms
54,428 KB
testcase_02 AC 38 ms
56,596 KB
testcase_03 AC 36 ms
53,748 KB
testcase_04 AC 34 ms
54,572 KB
testcase_05 AC 35 ms
55,500 KB
testcase_06 AC 200 ms
78,816 KB
testcase_07 AC 39 ms
56,288 KB
testcase_08 AC 42 ms
56,896 KB
testcase_09 AC 2,081 ms
168,680 KB
testcase_10 AC 1,705 ms
142,220 KB
testcase_11 AC 1,680 ms
141,404 KB
testcase_12 AC 2,055 ms
170,328 KB
testcase_13 AC 1,791 ms
144,960 KB
testcase_14 AC 1,644 ms
136,236 KB
testcase_15 TLE -
testcase_16 TLE -
testcase_17 AC 5,924 ms
272,688 KB
testcase_18 TLE -
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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

R=range
def TwoDimensionalAllNearestNeighbourNonBalanced( d2 , S , T ):
	S_size = len(S)
	if S_size == 0:return[]
	T_size = len(T)
	assert( T_size > 0 )
	if T_size == 1:return[[0]for i in R(S_size)]
	x_min,y_min = T[0]
	x_max,y_max = T[0]
	for j in R(1,T_size):
		x,y = T[j]
		x_min = min( x_min , x ); x_max = max( x , x_max )
		y_min = min( y_min , y ); y_max = max( y , y_max )
	neighbours = [[[1,0]]for i in R(S_size)]
	updatable = [1]*S_size
	divisible_block = [[x_min , x_max , y_min , y_max , list(R(T_size))]]
	indivisible_block = []
	while divisible_block:
		divisible_block_size = len(divisible_block)
		next_divisible_block = []
		Partition = [[]for num in R(divisible_block_size)]
		for num in R(divisible_block_size):
			x_min,x_max,y_min,y_max,t = divisible_block[num]
			x_mid = ( x_min + x_max ) // 2
			y_mid = ( y_min + y_max ) // 2
			block_sub = [[[0]*4+[[]]for num_y in R(2)]for num_x in R(2)]
			for j in t:
				x,y = T[j]
				x_min_sub,x_max_sub,y_min_sub,y_max_sub,t_sub = block_sub[x > x_mid][y > y_mid]
				if t_sub:
					x_min_sub = min( x_min_sub , x ); x_max_sub = max( x , x_max_sub )
					y_min_sub = min( y_min_sub , y ); y_max_sub = max( y , y_max_sub )
				else:x_min_sub = x_max_sub = x; y_min_sub = y_max_sub = y
				t_sub += [j]
				block_sub[x > x_mid][y > y_mid] = [x_min_sub,x_max_sub,y_min_sub,y_max_sub,t_sub]
			for num_x in R(2):
				for num_y in R(2):
					block_xy = block_sub[num_x][num_y]
					t_size = len(block_xy[4])
					if t_size != 0:
						if t_size == 1:
							Partition[num] += [[ 0 , len(indivisible_block) ]]
							indivisible_block += [block_xy]
						else:
							Partition[num] += [[ 1 , len(next_divisible_block) ]]
							next_divisible_block += [block_xy]
		divisible_block = next_divisible_block
		for i in R(S_size):
			if not updatable[i]:continue
			updatable[i] = 0
			neighbour_partition = []
			for coord in neighbours[i]:
				divisible,num = coord
				if divisible:
					for coord_sub in Partition[num]:neighbour_partition += [coord_sub]
				else:neighbour_partition += [coord]
			x,y = S[i]
			def d2_max( coord ):
				divisible,num = coord
				x_min,x_max,y_min,y_max,t = ( divisible_block if divisible else indivisible_block )[num]
				return d2( [ 0 , 0 ] , [ max( abs( x - x_min ) , abs( x_max - x ) ) , max( abs( y - y_min ) , abs( y_max - y ) ) ] )
			def d2_min( coord ):
				divisible,num = coord
				x_min,x_max,y_min,y_max,t = ( divisible_block if divisible else indivisible_block )[num]
				return d2( S[i] , [ x_min if x < x_min else x_max if x_max < x else x , y_min if y < y_min else y_max if y_max < y else y ] )
			d2_max_min = min( d2_max( np )for np in neighbour_partition )
			neighbours[i] = []
			for np in neighbour_partition:
				if d2_min( np ) <= d2_max_min:
					updatable[i] |= np[0]
					neighbours[i] += [np]
	answer = [[]for i in R(S_size)]
	for i in R(S_size):
		for divisible,num in neighbours[i]:
			assert( not divisible )
			x_min,x_max,y_min,y_max,t = indivisible_block[num]
			assert( len(t) == 1 and x_min == x_max == T[t[0]][0] and y_min == y_max == T[t[0]][1] )
			answer[i] += [t[0]]
	return answer

def d2(u,v):return (u[0]-v[0])**2+(u[1]-v[1])**2

J=lambda:list(map(int,input().split()))
N,M,K=J()
N+=1
XY=[J()for i in R(N)]
AB=[J()for k in R(K)]
V=J()[0]
import heapq
E=[[]for i in R(N)]
for j in R(M):u,v=J();w=d2(XY[u],XY[v])**0.5/V;E[u]+=[[v,w]];E[v]+=[[u,w]]
for i in R(1,N):E[0]+=[[i,d2(XY[0],XY[i])**0.5]]
W=[9**20]*N
W[0]=0
S=[[0,0]]
while S:
	w,i=heapq.heappop(S)
	if w>W[i]:continue
	for j,v in E[i]:
		if w+v<W[j]:W[j]=w+v;heapq.heappush(S,[w+v,j])
ann=TwoDimensionalAllNearestNeighbourNonBalanced(d2,AB,XY)
answer=sum(min(d2(XY[0],AB[k])**0.5,min(W[i]+d2(XY[i],AB[k])**0.5 for i in ann[k]))for k in R(K))
print(answer*2)
0