Problem p03153 (python)

Fixed submission:
from operator import itemgetter
import itertools
def inpl(): return list(map(int, input().split()))
def cost(x, y):
    if x == y:
        return float('inf')
    return D * abs(x - y) + A[x] + A[y]
N, D = inpl()
A = inpl()
Right = [(v - i*D, i) for i, v in enumerate(A)]
Left = [(v + i*D, i) for i, v in enumerate(A)][::-1]
Right = list(map(itemgetter(1), itertools.accumulate(Right, min)))
Left = list(map(itemgetter(1), itertools.accumulate(Left, min)))[::-1]
ans = 0
hub = []
for i, (l, r) in enumerate(zip(Left, Right)) :
    if i == l == r:
        hub.append(i)
    else:
        ans += min(cost(i, r), cost(i, l))
print(ans + sum([cost(i, j) for i, j in zip(hub, hub[1:])]))

Buggy submission (verdict: Runtime Error):
import itertools
from operator import itemgetter
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
            if self.par[rx] > self.par[ry]:
                self.par[rx] = ry
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
        return

def inpl(): return list(map(int, input().split()))
def cost(x, y):
    return D * abs(x - y) + A[x] + A[y]
N, D = inpl()
A = inpl()
minx = A.index(min(A))
Right = [(v - i*D, i) for i, v in enumerate(A)]
Left = [(v + i*D, i) for i, v in enumerate(A)][::-1]
Right = list(itertools.accumulate(Right[minx:], min))
Left = list(itertools.accumulate(Left[N - 1 - minx:], min))
hub = [0]
for _, i in itertools.chain(Left[::-1],Right,(0, N-1)):
    if hub[-1] != i:
        hub.append(i)
edge = [(cost(hub[i], k), hub[i], k) for i in range(len(hub)-1) for k in range(hub[i]+1, hub[i+1])]\
+ [(cost(hub[i+1], k), hub[i+1], k) for i in range(len(hub)-1) for k in range(hub[i], hub[i+1])]
edge.sort(reverse = True)
Uf = UnionFind(N)
ctr = 1
ans = 0
while ctr < N:
    v, i, j = edge.pop()
    if Uf.find(i) != Uf.find(j):
        Uf.union(i, j)
        ctr += 1
        ans += v
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
import itertools
from operator import itemgetter
from collections import defaultdict
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
            if self.par[rx] > self.par[ry]:
                self.par[rx] = ry
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
        return

def inpl(): return list(map(int, input().split()))
def cost(x, y):
    return D * abs(x - y) + A[x] + A[y]
N, D = inpl()
A = inpl()
minx = A.index(min(A))
Right = [(v - i*D, i) for i, v in enumerate(A)]
Left = [(v + i*D, i) for i, v in enumerate(A)][::-1]
Right = itertools.accumulate(Right[minx:], min)
Left = itertools.accumulate(Left[N - 1 - minx:], min)
hub = set(map(itemgetter(1), Right))
hub.update(map(itemgetter(1), Left))
hub.add(0)
hub.add(N-1)
hub = list(sorted(hub))
edge = [(cost(hub[i], k), hub[i], k) for i in range(len(hub)-1) for k in range(hub[i], hub[i+1])]\
+ [(cost(hub[i+1], k), hub[i+1], k) for i in range(len(hub)-1) for k in range(hub[i], hub[i+1])]
edge.sort(reverse = True)
Uf = UnionFind(N)
ctr = 1
ans = 0
print(edge)
while ctr < N:
    v, i, j = edge.pop()
    if Uf.find(i) != Uf.find(j):
        Uf.union(i, j)
        ctr += 1
        ans += v
print(ans)