Submission #61870352

---

Source Code Expand

##### import #####
from time import time
from random import randint
from collections import deque

##### input #####
N,M,H = map(int,input().split())
A = list(map(int,input().split()))
sortedA = [[A[i],i]for i in range(N)]
U = [list()for _ in range(M)]   #U[i]に頂点iと隣接している頂点番号の配列
for _ in range(M):
  v1,v2 = map(int,input().split())
  U[v1].append(v2)
  U[v2].append(v1)

##### function #####
def tree(r,size):
  global selected
  global selected_v
  global ANS
  selected_v += 1
  selected[r] = True
  a_look = 0  #この木の見栄え
  dq = deque([[r,0,-1]])  #幅優先探索のdeque　各要素は[見るべき場所,根からの距離,元の頂点]
  while len(dq)>0:
    s = dq.popleft()
    a_look += A[s[0]]*(s[1]+1)
    ANS[s[0]] = s[2]
    if s[1] < size:  #dq追加処理
      for v in U[s[0]]:
        if not selected[v] and randint(1,(s[1]+1)*A[v])>30:
          selected[v] = True
          selected_v += 1
          dq.append([v,s[1]+1,s[0]])
  return a_look

def decide_root():
  ret = [0]*N
  C = sortedA[:]
  dq = deque([])
  for _ in range(1000):
    _selected = selected[:]
    edge = C.pop()[1]
    Rscore = [1]*N
    dq.append([edge,1,-1]) #幅優先探索のdeque　各要素は[見るべき場所,根からの距離,元の頂点]
    while len(dq)>0:
      r = dq.popleft()
      for v in U[r[0]]:
        if not _selected[v] and A[v]<A[r[0]]:
          _selected[v] = True
          Rscore[v] = Rscore[r[2]]*((r[1]+3)/r[1]+2)
          ret[v] += Rscore[v]
          dq.append([v,r[1]+1,r[0]])
  #print(Rscore)
  return ret

##### 本体 #####
stime = time()  #処理開始時の時刻
ANS = [-1]*N
max_score = -1
TRUE_ANS = 0
while time()<stime+1.7:
  selected = [False]*N  #選択済みの頂点かどうか
  selected_v = 0  #選択済み頂点の個数
  root = randint(0,N-1)
  score = 0
  while selected_v < N:
    Rscore = decide_root()
    Rscore = [[Rscore[i],i]for i in range(N)]
    Rscore.sort()
    #print(Rscore)
    while True:
      root = Rscore.pop()[1]
      if not selected[root]:
        break
    score += tree(root,H)
  if score > max_score:
    max_score = score
    TRUE_ANS = ANS
print(*TRUE_ANS)

Submission Info

Judge Result