Problem:


Score : 600 points

Problem Statement

There are N cities in Republic of AtCoder. The size of the i-th city is A_{i}.
Takahashi would like to build N-1 bidirectional roads connecting two cities so that any city can be reached from any other city by using these roads.

Assume that the cost of building a road connecting the i-th city and the j-th city is |i-j| \times D + A_{i} + A_{j}.
For Takahashi, find the minimum possible total cost to achieve the objective.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq D \leq 10^9

1 \leq A_{i} \leq 10^9

A_{i} and D are integers.

Input

Input is given from Standard Input in the following format:

N D
A_1 A_2 ... A_N

Output

Print the minimum possible total cost.

Sample Input 1

3 1
1 100 1

Sample Output 1

106

This cost can be achieved by, for example, building roads connecting City 1, 2 and City 1, 3.

Sample Input 2

3 1000
1 100 1

Sample Output 2

2202

Sample Input 3

6 14
25 171 7 1 17 162

Sample Output 3

497

Sample Input 4

12 5
43 94 27 3 69 99 56 25 8 15 46 8

Sample Output 4

658



Sample input:
3 1
1 100 1


Sample output:
106

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N, D = mi()

#As[i] = [各都市のコスト,各都市の番号]
#0-indexed
As = [[a, i] for i, a in enumerate(list(mi()))]

#Union-Find ****0スタートなので注意！****
class UnionFind():
  # 作りたい要素数（ノードの数）nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n) #元々はn+1になっていたが、nにした（n+1なら1スタートで使えるかもしれないが、Count_Trees()がおかしくなるのでやめた）
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n) #元々はn+1になっていたが、nにした

  # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  # 木の併合、入力は併合したい集合に属する各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合、何もしないで返す
    if(x == y):
      return
    # 違う木に属していた場合rnkを見てくっつける方を決める
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y] #要素数を足す(根のrootは"-要素数")
      self.root[y] = x #ノードyの親をx（新しい集合の根）とする
    else:
      self.root[y] += self.root[x] #要素数を足す
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
      if(self.rnk[x] == self.rnk[y]):
          self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
  def Count(self, x):
    return -self.root[self.Find_Root(x)] #-符号を外す

#As_規模降順 = [各都市の規模, 各都市の番号（降順ソート前の番号）]
#from operator import itemgetter
#As_costdescending = sorted(As, key=itemgetter(0), reverse=True)
Asd = []
for a,i in As:
	Asd.append((-a,i))
heapq.heapify(Asd)

#SegTreeはやめて、累積最小値を使う
cummin_left = [0] * N
cummin_right = [0] * N

tmpmin = INF
tmpminidx = -1
for i in range(0, N-1): #leftなので、0~N-2を更新
  if (N-i)*D+As[i][0] <= tmpmin:
    tmpmin = (N-i)*D+As[i][0]
    tmpminidx = i
  cummin_left[i] = tmpminidx

tmpmin = INF
tmpminidx = -1
for i in range(N-1, 0, -1): #rightなので、N-1~1を更新
#  print(i+As[i][0])
  if i*D+As[i][0] <= tmpmin:
    tmpmin = i*D+As[i][0]
    tmpminidx = i
  cummin_right[i] = tmpminidx

#print(cummin_left)
#print(cummin_right)
#[(cost, idx, adjidx), ...]
edge_candidates = []

while Asd:
  a, o_idx = heapq.heappop(Asd)
  a = -a #o_idx:降順にする前のidx
  if o_idx == 0: #右だけを見る
    rightmin_oidx = cummin_right[1]
    edge_candidates.append((abs(o_idx-rightmin_oidx)*D+a+As[rightmin_oidx][0], o_idx, rightmin_oidx))
  elif o_idx == N-1: #左だけを見る
    leftmin_oidx = cummin_left[N-2]
    edge_candidates.append((abs(o_idx-leftmin_oidx)*D+a+As[leftmin_oidx][0], o_idx, leftmin_oidx))
  else:
    leftmin_oidx = cummin_left[o_idx-1]
#    print('+0:', o_idx)
#    print('+1:', o_idx+1, cummin_right[o_idx+1])
    rightmin_oidx = cummin_right[o_idx+1]
    edge_candidates.append((abs(o_idx-leftmin_oidx)*D+a+As[leftmin_oidx][0], o_idx, leftmin_oidx))
    edge_candidates.append((abs(o_idx-rightmin_oidx)*D+a+As[rightmin_oidx][0], o_idx, rightmin_oidx))


heapq.heapify(edge_candidates)

#上でできた配列に対してクラスカル法を適用して最小全域木（のコスト総和）を求める
#Union-Findを使ったクラスカル法
uf = UnionFind(N)
ans = 0
while edge_candidates:
  c, idx, adjidx = heapq.heappop(edge_candidates)
  if not uf.isSameGroup(idx, adjidx):
    ans += c
    uf.Unite(idx, adjidx)

print(ans)

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N, D = mi()

#As[i] = [各都市のコスト,各都市の番号]
#0-indexed
As = [[a, i] for i, a in enumerate(list(mi()))]

#Union-Find ****0スタートなので注意！****
class UnionFind():
  # 作りたい要素数（ノードの数）nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n) #元々はn+1になっていたが、nにした（n+1なら1スタートで使えるかもしれないが、Count_Trees()がおかしくなるのでやめた）
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n) #元々はn+1になっていたが、nにした

  # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  # 木の併合、入力は併合したい集合に属する各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合、何もしないで返す
    if(x == y):
      return
    # 違う木に属していた場合rnkを見てくっつける方を決める
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y] #要素数を足す(根のrootは"-要素数")
      self.root[y] = x #ノードyの親をx（新しい集合の根）とする
    else:
      self.root[y] += self.root[x] #要素数を足す
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
      if(self.rnk[x] == self.rnk[y]):
          self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
  def Count(self, x):
    return -self.root[self.Find_Root(x)] #-符号を外す

#As_規模降順 = [各都市の規模, 各都市の番号（降順ソート前の番号）]
from operator import itemgetter
As_costdescending = sorted(As, key=itemgetter(0), reverse=True)

#SegTreeはやめて、累積最小値を使う
cummin_left = [0] * N
cummin_right = [0] * N

tmpmin = INF
tmpminidx = -1
for i in range(0, N-1): #leftなので、0~N-2を更新
  if (N-i)*D+As[i][0] <= tmpmin:
    tmpmin = (N-i)*D+As[i][0]
    tmpminidx = i
  cummin_left[i] = tmpminidx

tmpmin = INF
tmpminidx = -1
for i in range(N-1, 0, -1): #rightなので、N-1~1を更新
#  print(i+As[i][0])
  if i*D+As[i][0] <= tmpmin:
    tmpmin = i*D+As[i][0]
    tmpminidx = i
  cummin_right[i] = tmpminidx

#print(cummin_left)
#print(cummin_right)
#[(cost, idx, adjidx), ...]
edge_candidates = []

for a, o_idx in As_costdescending: #o_idx:降順にする前のidx
  if o_idx == 0: #右だけを見る
    rightmin_oidx = cummin_right[1]
    edge_candidates.append((abs(o_idx-rightmin_oidx)*D+a+As[rightmin_oidx][0], o_idx, rightmin_oidx))
  elif o_idx == N-1: #左だけを見る
    leftmin_oidx = cummin_left[N-2]
    edge_candidates.append((abs(o_idx-leftmin_oidx)*D+a+As[leftmin_oidx][0], o_idx, leftmin_oidx))
  else:
    leftmin_oidx = cummin_left[o_idx-1]
#    print('+0:', o_idx)
#    print('+1:', o_idx+1, cummin_right[o_idx+1])
    rightmin_oidx = cummin_right[o_idx+1]
    edge_candidates.append((abs(o_idx-leftmin_oidx)*D+a+As[leftmin_oidx][0], o_idx, leftmin_oidx))
    edge_candidates.append((abs(o_idx-rightmin_oidx)*D+a+As[rightmin_oidx][0], o_idx, rightmin_oidx))


heapq.heapify(edge_candidates)

#上でできた配列に対してクラスカル法を適用して最小全域木（のコスト総和）を求める
#Union-Findを使ったクラスカル法
uf = UnionFind(N)
ans = 0
while edge_candidates:
  c, idx, adjidx = heapq.heappop(edge_candidates)
  if not uf.isSameGroup(idx, adjidx):
    ans += c
    uf.Unite(idx, adjidx)

print(ans)

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N, D = mi()

#As[i] = [各都市のコスト,各都市の番号]
#0-indexed
As = [[a, i] for i, a in enumerate(list(mi()))]

#Union-Find ****0スタートなので注意！****
class UnionFind():
  # 作りたい要素数（ノードの数）nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n) #元々はn+1になっていたが、nにした（n+1なら1スタートで使えるかもしれないが、Count_Trees()がおかしくなるのでやめた）
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n) #元々はn+1になっていたが、nにした

  # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  # 木の併合、入力は併合したい集合に属する各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合、何もしないで返す
    if(x == y):
      return
    # 違う木に属していた場合rnkを見てくっつける方を決める
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y] #要素数を足す(根のrootは"-要素数")
      self.root[y] = x #ノードyの親をx（新しい集合の根）とする
    else:
      self.root[y] += self.root[x] #要素数を足す
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
      if(self.rnk[x] == self.rnk[y]):
          self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
  def Count(self, x):
    return -self.root[self.Find_Root(x)] #-符号を外す

  # 木の数（＝集合の数）を返す（根の数=rootに-符号を持つものの数を返すだけ）
  def Count_Trees(self):
    treecnt = 0
    for eachroot in self.root:
      if eachroot < 0: treecnt += 1
    return treecnt

#As_規模降順 = [各都市の規模, 各都市の番号（降順ソート前の番号）]
from operator import itemgetter
As_costdescending = sorted(As, key=itemgetter(0), reverse=True)

#SegTreeはやめて、累積最小値を使う
cummin_left = [0] * N
cummin_right = [0] * N

tmpmin = INF
tmpminidx = -1
for i in range(0, N-1): #leftなので、0~N-2を更新
  if N-i+As[i][0] <= tmpmin:
    tmpmin = N-i+As[i][0]
    tmpminidx = i
  cummin_left[i] = tmpminidx

tmpmin = INF
tmpminidx = -1
for i in range(N-1, 0, -1): #rightなので、N-1~1を更新
#  print(i+As[i][0])
  if i+As[i][0] <= tmpmin:
    tmpmin = i+As[i][0]
    tmpminidx = i
  cummin_right[i] = tmpminidx

#print(cummin_left)
#print(cummin_right)
#[(cost, idx, adjidx), ...]
edge_candidates = []

for a, o_idx in As_costdescending: #o_idx:降順にする前のidx
  if o_idx == 0: #右だけを見る
    rightmin_oidx = cummin_right[1]
    edge_candidates.append((abs(o_idx-rightmin_oidx)*D+a+As[rightmin_oidx][0], o_idx, rightmin_oidx))
  elif o_idx == N-1: #左だけを見る
    leftmin_oidx = cummin_left[N-2]
    edge_candidates.append((abs(o_idx-leftmin_oidx)*D+a+As[leftmin_oidx][0], o_idx, leftmin_oidx))
  else:
    leftmin_oidx = cummin_left[o_idx-1]
#    print('+0:', o_idx)
#    print('+1:', o_idx+1, cummin_right[o_idx+1])
    rightmin_oidx = cummin_right[o_idx+1]
    edge_candidates.append((abs(o_idx-leftmin_oidx)*D+a+As[leftmin_oidx][0], o_idx, leftmin_oidx))
    edge_candidates.append((abs(o_idx-rightmin_oidx)*D+a+As[rightmin_oidx][0], o_idx, rightmin_oidx))


heapq.heapify(edge_candidates)

#上でできた配列に対してクラスカル法を適用して最小全域木（のコスト総和）を求める
#Union-Findを使ったクラスカル法
uf = UnionFind(N)
ans = 0
while edge_candidates:
  c, idx, adjidx = heapq.heappop(edge_candidates)
  if not uf.isSameGroup(idx, adjidx):
    ans += c
    uf.Unite(idx, adjidx)

print(ans)

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N, D = mi()

#As[i] = [各都市のコスト,各都市の番号]
#0-indexed
As = [[a, i] for i, a in enumerate(list(mi()))]

#Union-Find ****0スタートなので注意！****
class UnionFind():
  # 作りたい要素数（ノードの数）nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n) #元々はn+1になっていたが、nにした（n+1なら1スタートで使えるかもしれないが、Count_Trees()がおかしくなるのでやめた）
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n) #元々はn+1になっていたが、nにした

  # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  # 木の併合、入力は併合したい集合に属する各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合、何もしないで返す
    if(x == y):
      return
    # 違う木に属していた場合rnkを見てくっつける方を決める
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y] #要素数を足す(根のrootは"-要素数")
      self.root[y] = x #ノードyの親をx（新しい集合の根）とする
    else:
      self.root[y] += self.root[x] #要素数を足す
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
      if(self.rnk[x] == self.rnk[y]):
          self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
  def Count(self, x):
    return -self.root[self.Find_Root(x)] #-符号を外す

  # 木の数（＝集合の数）を返す（根の数=rootに-符号を持つものの数を返すだけ）
  def Count_Trees(self):
    treecnt = 0
    for eachroot in self.root:
      if eachroot < 0: treecnt += 1
    return treecnt

#As_規模降順 = [各都市の規模, 各都市の番号（降順ソート前の番号）]
from operator import itemgetter
As_costdescending = sorted(As, key=itemgetter(0), reverse=True)

#規模が最大[2番目, 3番目..]の都市を固定し、リストの右側に向けて処理をしていく。
#その際、今固定している都市の番号より小さければ左側だし、大きければ右側なので、それによって場合分けをして、２つのセグ木に入れていけばいい。
#セグ木のサイズは、それぞれ最大N-1個（各都市は自分と道路を繋がないから-1）
##...のはずだが、添字が面倒になりそうなので、どっちもN個にする。端っこはINFになるから多分大丈夫だろう

#ここからの方針
#規模降順で全ての都市についてfor文を回して、各都市との建設コストをセグ木に入れる
#セグ木から、左側と右側の区間最小値を取り出すO(NlogN)-->O(logN)？
####区間最小値となる都市の番号を取り出す必要がある。-->タプルをセグ木に入れる
#区間最小値となる都市の番号が分かったら、今固定している都市と、区間最小値となる都市、そしてその2つを繋ぐコストを配列に入れていく
#sgt_left = SegTree(N)
#sgt_right = SegTree(N)

#for a, i in As:
#  sgt_left.update(i, N-i+a)
#  sgt_right.update(i, i+a)

#SegTreeはやめて、累積最小値を使う
cummin_left = [[INF, 0]] * N
cummin_right = [[INF, 0]] * N

tmpmin = INF
tmpminidx = -1
for i in range(0, N-1): #leftなので、0~N-2を更新
  if N-i+As[i][0] <= tmpmin:
    tmpmin = N-i+As[i][0]
    tmpminidx = i
  cummin_left[i] = [tmpmin, tmpminidx]

tmpmin = INF
tmpminidx = -1
for i in range(N-1, 0, -1): #rightなので、N-1~1を更新
#  print(i+As[i][0])
  if i+As[i][0] <= tmpmin:
    tmpmin = i+As[i][0]
    tmpminidx = i
  cummin_right[i] = [tmpmin, tmpminidx]

#print(cummin_left)
#print(cummin_right)
#[(cost, idx, adjidx), ...]
edge_candidates = []

for a, o_idx in As_costdescending: #o_idx:降順にする前のidx
  if o_idx == 0: #右だけを見る
    rightmin_cost, rightmin_oidx = cummin_right[1]
    edge_candidates.append((abs(o_idx-rightmin_oidx)+a+As[rightmin_oidx][0], o_idx, rightmin_oidx))
  elif o_idx == N-1: #左だけを見る
    leftmin_cost, leftmin_oidx = cummin_left[N-2]
    edge_candidates.append((abs(o_idx-leftmin_oidx)+a+As[leftmin_oidx][0], o_idx, leftmin_oidx))
  else:
    leftmin_cost, leftmin_oidx = cummin_left[o_idx-1]
#    print('+0:', o_idx)
#    print('+1:', o_idx+1, cummin_right[o_idx+1])
    rightmin_cost, rightmin_oidx = cummin_right[o_idx+1]
    edge_candidates.append((abs(o_idx-leftmin_oidx)+a+As[leftmin_oidx][0], o_idx, leftmin_oidx))
    edge_candidates.append((abs(o_idx-rightmin_oidx)+a+As[rightmin_oidx][0], o_idx, rightmin_oidx))


heapq.heapify(edge_candidates)

#上でできた配列に対してクラスカル法を適用して最小全域木（のコスト総和）を求める
#Union-Findを使ったクラスカル法
uf = UnionFind(N)
ans = 0
while edge_candidates:
  c, idx, adjidx = heapq.heappop(edge_candidates)
  if not uf.isSameGroup(idx, adjidx):
    ans += c
    uf.Unite(idx, adjidx)

print(ans)

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N, D = mi()

#As[i] = [各都市のコスト,各都市の番号]
#0-indexed
As = [[a, i] for i, a in enumerate(list(mi()))]

#Union-Find ****0スタートなので注意！****
class UnionFind():
  # 作りたい要素数（ノードの数）nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n) #元々はn+1になっていたが、nにした（n+1なら1スタートで使えるかもしれないが、Count_Trees()がおかしくなるのでやめた）
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n) #元々はn+1になっていたが、nにした

  # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  # 木の併合、入力は併合したい集合に属する各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合、何もしないで返す
    if(x == y):
      return
    # 違う木に属していた場合rnkを見てくっつける方を決める
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y] #要素数を足す(根のrootは"-要素数")
      self.root[y] = x #ノードyの親をx（新しい集合の根）とする
    else:
      self.root[y] += self.root[x] #要素数を足す
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
      if(self.rnk[x] == self.rnk[y]):
          self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
  def Count(self, x):
    return -self.root[self.Find_Root(x)] #-符号を外す

  # 木の数（＝集合の数）を返す（根の数=rootに-符号を持つものの数を返すだけ）
  def Count_Trees(self):
    treecnt = 0
    for eachroot in self.root:
      if eachroot < 0: treecnt += 1
    return treecnt

#クラスを使ったセグ木 - ちょっと遅いけど、2つ以上作りたい時に
class SegTree:
  __slots__ = ['node', 'size']

  def __init__(self, n_):
    self.size = 2 ** n_.bit_length()
    self.node = [INF] * (2 * self.size)

  # k番目の値をaに変更
  def update(self, k, a):
    k += self.size - 1
    self.node[k] = a
    # 登りながら更新
    while k >= 0:
      k = (k - 1) // 2
      self.node[k] = min(self.node[k * 2 + 1], self.node[k * 2 + 2])

  # [a, b)の最小値を求める
  def query(self, a, b):
    l, r = a + self.size, b + self.size
    res = INF
    while l < r:
      if r & 1:
        r -= 1
        res = min(res, self.node[r - 1])

      if l & 1:
        res = min(res, self.node[l - 1])
        l += 1

      l >>= 1
      r >>= 1
    return res

#As_規模降順 = [各都市の規模, 各都市の番号（降順ソート前の番号）]
from operator import itemgetter
As_costdescending = sorted(As, key=itemgetter(0), reverse=True)

#規模が最大[2番目, 3番目..]の都市を固定し、リストの右側に向けて処理をしていく。
#その際、今固定している都市の番号より小さければ左側だし、大きければ右側なので、それによって場合分けをして、２つのセグ木に入れていけばいい。
#セグ木のサイズは、それぞれ最大N-1個（各都市は自分と道路を繋がないから-1）
##...のはずだが、添字が面倒になりそうなので、どっちもN個にする。端っこはINFになるから多分大丈夫だろう

#ここからの方針
#規模降順で全ての都市についてfor文を回して、各都市との建設コストをセグ木に入れる
#セグ木から、左側と右側の区間最小値を取り出すO(NlogN)-->O(logN)？
####区間最小値となる都市の番号を取り出す必要がある。-->タプルをセグ木に入れる
#区間最小値となる都市の番号が分かったら、今固定している都市と、区間最小値となる都市、そしてその2つを繋ぐコストを配列に入れていく
#sgt_left = SegTree(N)
#sgt_right = SegTree(N)

#for a, i in As:
#  sgt_left.update(i, N-i+a)
#  sgt_right.update(i, i+a)

#SegTreeはやめて、累積最小値を使う
cummin_left = [[INF, 0]] * N
cummin_right = [[INF, 0]] * N

tmpmin = INF
tmpminidx = -1
for i in range(0, N-1): #leftなので、0~N-2を更新
  if N-i+As[i][0] <= tmpmin:
    tmpmin = N-i+As[i][0]
    tmpminidx = i
  cummin_left[i] = [tmpmin, tmpminidx]

tmpmin = INF
tmpminidx = -1
for i in range(N-1, 0, -1): #rightなので、N-1~1を更新
#  print(i+As[i][0])
  if i+As[i][0] <= tmpmin:
    tmpmin = i+As[i][0]
    tmpminidx = i
  cummin_right[i] = [tmpmin, tmpminidx]

#print(cummin_left)
#print(cummin_right)
#[(cost, idx, adjidx), ...]
edge_candidates = []
heapq.heapify(edge_candidates)

for a, o_idx in As_costdescending: #o_idx:降順にする前のidx
  if o_idx == 0: #右だけを見る
    rightmin_cost, rightmin_oidx = cummin_right[1]
    heapq.heappush(edge_candidates, (abs(o_idx-rightmin_oidx)+a+As[rightmin_oidx][0], o_idx, rightmin_oidx))
  elif o_idx == N-1: #左だけを見る
    leftmin_cost, leftmin_oidx = cummin_left[N-2]
    heapq.heappush(edge_candidates, (abs(o_idx-leftmin_oidx)+a+As[leftmin_oidx][0], o_idx, leftmin_oidx))
  else:
    leftmin_cost, leftmin_oidx = cummin_left[o_idx-1]
#    print('+0:', o_idx)
#    print('+1:', o_idx+1, cummin_right[o_idx+1])
    rightmin_cost, rightmin_oidx = cummin_right[o_idx+1]
    heapq.heappush(edge_candidates, (abs(o_idx-leftmin_oidx)+a+As[leftmin_oidx][0], o_idx, leftmin_oidx))
    heapq.heappush(edge_candidates, (abs(o_idx-rightmin_oidx)+a+As[rightmin_oidx][0], o_idx, rightmin_oidx))

#上でできた配列に対してクラスカル法を適用して最小全域木（のコスト総和）を求める
#Union-Findを使ったクラスカル法
uf = UnionFind(N)
ans = 0
while edge_candidates:
  c, idx, adjidx = heapq.heappop(edge_candidates)
  if not uf.isSameGroup(idx, adjidx):
    ans += c
    uf.Unite(idx, adjidx)

print(ans)

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N, D = mi()

#As[i] = [各都市のコスト,各都市の番号]
#0-indexed
As = [[a, i] for i, a in enumerate(list(mi()))]

#Union-Find ****0スタートなので注意！****
class UnionFind():
  # 作りたい要素数（ノードの数）nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n) #元々はn+1になっていたが、nにした（n+1なら1スタートで使えるかもしれないが、Count_Trees()がおかしくなるのでやめた）
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n) #元々はn+1になっていたが、nにした

  # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  # 木の併合、入力は併合したい集合に属する各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合、何もしないで返す
    if(x == y):
      return
    # 違う木に属していた場合rnkを見てくっつける方を決める
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y] #要素数を足す(根のrootは"-要素数")
      self.root[y] = x #ノードyの親をx（新しい集合の根）とする
    else:
      self.root[y] += self.root[x] #要素数を足す
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
      if(self.rnk[x] == self.rnk[y]):
          self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
  def Count(self, x):
    return -self.root[self.Find_Root(x)] #-符号を外す

  # 木の数（＝集合の数）を返す（根の数=rootに-符号を持つものの数を返すだけ）
  def Count_Trees(self):
    treecnt = 0
    for eachroot in self.root:
      if eachroot < 0: treecnt += 1
    return treecnt

#クラスを使ったセグ木 - ちょっと遅いけど、2つ以上作りたい時に
class SegTree:
  __slots__ = ['node', 'size']

  def __init__(self, n_):
    self.size = 2 ** n_.bit_length()
    self.node = [INF] * (2 * self.size)

  # k番目の値をaに変更
  def update(self, k, a):
    k += self.size - 1
    self.node[k] = a
    # 登りながら更新
    while k >= 0:
      k = (k - 1) // 2
      self.node[k] = min(self.node[k * 2 + 1], self.node[k * 2 + 2])

  # [a, b)の最小値を求める
  def query(self, a, b):
    l, r = a + self.size, b + self.size
    res = INF
    while l < r:
      if r & 1:
        r -= 1
        res = min(res, self.node[r - 1])

      if l & 1:
        res = min(res, self.node[l - 1])
        l += 1

      l >>= 1
      r >>= 1
    return res

#As_規模降順 = [各都市の規模, 各都市の番号（降順ソート前の番号）]
from operator import itemgetter
As_costdescending = sorted(As, key=itemgetter(0))

#規模が最大[2番目, 3番目..]の都市を固定し、リストの右側に向けて処理をしていく。
#その際、今固定している都市の番号より小さければ左側だし、大きければ右側なので、それによって場合分けをして、２つのセグ木に入れていけばいい。
#セグ木のサイズは、それぞれ最大N-1個（各都市は自分と道路を繋がないから-1）
##...のはずだが、添字が面倒になりそうなので、どっちもN個にする。端っこはINFになるから多分大丈夫だろう

#ここからの方針
#規模降順で全ての都市についてfor文を回して、各都市との建設コストをセグ木に入れる
#セグ木から、左側と右側の区間最小値を取り出すO(NlogN)-->O(logN)？
####区間最小値となる都市の番号を取り出す必要がある。-->タプルをセグ木に入れる
#区間最小値となる都市の番号が分かったら、今固定している都市と、区間最小値となる都市、そしてその2つを繋ぐコストを配列に入れていく
#sgt_left = SegTree(N)
#sgt_right = SegTree(N)

#for a, i in As:
#  sgt_left.update(i, N-i+a)
#  sgt_right.update(i, i+a)

#SegTreeはやめて、累積最小値を使う
cummin_left = [[INF, 0]] * N
cummin_right = [[INF, 0]] * N

tmpmin = INF
tmpminidx = -1
for i in range(0, N-1): #leftなので、0~N-2を更新
  if N-i+As[i][0] <= tmpmin:
    tmpmin = N-i+As[i][0]
    tmpminidx = i
  cummin_left[i] = [tmpmin, tmpminidx]

tmpmin = INF
tmpminidx = -1
for i in range(N-1, 0, -1): #rightなので、N-1~1を更新
#  print(i+As[i][0])
  if i+As[i][0] <= tmpmin:
    tmpmin = i+As[i][0]
    tmpminidx = i
  cummin_right[i] = [tmpmin, tmpminidx]

#print(cummin_left)
#print(cummin_right)
#[(cost, idx, adjidx), ...]
edge_candidates = []
heapq.heapify(edge_candidates)

for a, o_idx in As_costdescending: #o_idx:降順にする前のidx
  if o_idx == 0: #右だけを見る
    rightmin_cost, rightmin_oidx = cummin_right[1]
    heapq.heappush(edge_candidates, (abs(o_idx-rightmin_oidx)+a+As[rightmin_oidx][0], o_idx, rightmin_oidx))
  elif o_idx == N-1: #左だけを見る
    leftmin_cost, leftmin_oidx = cummin_left[N-1]
    heapq.heappush(edge_candidates, (abs(o_idx-leftmin_oidx)+a+As[leftmin_oidx][0], o_idx, leftmin_oidx))
  else:
    leftmin_cost, leftmin_oidx = cummin_left[o_idx-1]
#    print('+0:', o_idx)
#    print('+1:', o_idx+1, cummin_right[o_idx+1])
    rightmin_cost, rightmin_oidx = cummin_right[o_idx+1]
    heapq.heappush(edge_candidates, (abs(o_idx-leftmin_oidx)+a+As[leftmin_oidx][0], o_idx, leftmin_oidx))
    heapq.heappush(edge_candidates, (abs(o_idx-rightmin_oidx)+a+As[rightmin_oidx][0], o_idx, rightmin_oidx))

#上でできた配列に対してクラスカル法を適用して最小全域木（のコスト総和）を求める
#Union-Findを使ったクラスカル法
uf = UnionFind(N)
ans = 0
while edge_candidates:
  c, idx, adjidx = heapq.heappop(edge_candidates)
  if not uf.isSameGroup(idx, adjidx):
    ans += c
    uf.Unite(idx, adjidx)

print(ans)

Submission status: Wrong Answer

Solution code:
#Union-Find ****0スタートなので注意！****
class UnionFind():
  # 作りたい要素数（ノードの数）nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n) #元々はn+1になっていたが、nにした（n+1なら1スタートで使えるかもしれないが、Count_Trees()がおかしくなるのでやめた）
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n) #元々はn+1になっていたが、nにした

  # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  # 木の併合、入力は併合したい集合に属する各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合、何もしないで返す
    if(x == y):
      return
    # 違う木に属していた場合rnkを見てくっつける方を決める
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y] #要素数を足す(根のrootは"-要素数")
      self.root[y] = x #ノードyの親をx（新しい集合の根）とする
    else:
      self.root[y] += self.root[x] #要素数を足す
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
      if(self.rnk[x] == self.rnk[y]):
          self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
  def Count(self, x):
    return -self.root[self.Find_Root(x)] #-符号を外す

  # 木の数（＝集合の数）を返す（根の数=rootに-符号を持つものの数を返すだけ）
  def Count_Trees(self):
    treecnt = 0
    for eachroot in self.root:
      if eachroot < 0: treecnt += 1
    return treecnt