Problem p03682 (python)

Fixed submission:
import sys
sys.setrecursionlimit(100000)

def unite(i, j):
    j = get_par(j)
    par[j] = get_par(i)
    return

def get_par(p):
    if par[p] is None:
        return p
    par[p] = get_par(par[p])
    return par[p]

N = int(input())
points = []
edges = []
for i in range(N):
    x,y = map(int, input().split())
    points.append([x,y,i])
points.sort()
for i in range(N-1):
    edges.append((abs(points[i][0] - points[i+1][0]), points[i][2], points[i+1][2]))
points.sort(key=lambda x:x[1])
for i in range(N-1):
    edges.append((abs(points[i][1] - points[i+1][1]), points[i][2], points[i+1][2]))
edges.sort(key=lambda x:x[0], reverse=True)

par = [None] * N
cost = 0
count = 0
points.sort()
while count < N - 1:
    c, i, j = edges.pop()
    if get_par(i) == get_par(j):
        continue
    unite(i, j)
    cost += c
    count += 1
print(cost)

Buggy submission (verdict: Runtime Error):
def unite(par, i, j):
    j = get_par(par, j)
    par[j] = get_par(par, i)

def get_par(par, p):
    while par[p] != None:
        p = par[p]
    return par[p]

N = int(input())
points = []
edges = []
for i in range(N):
    x,y = map(int, input().split())
    points.append([x,y,i])
points.sort()
for i in range(N-1):
    edges.append((abs(points[i][0] - points[i+1][0]), points[i][2], points[i+1][2]))
points.sort(key=lambda x:x[1])
for i in range(N-1):
    edges.append((abs(points[i][1] - points[i+1][1]), points[i][2], points[i+1][2]))
edges.sort(key=lambda x:x[0], reverse=True)

par = [None] * N
cost = 0
count = 0
points.sort()
while count < N - 1:
    c, i, j = edges.pop()
    if get_par(par, i) == get_par(par, j):
        continue
    unite(points, i, j)
    cost += c
    count += 1
print(cost)

Buggy submission (verdict: Runtime Error):
def unite(par, i, j):
    j = get_par(par, j)
    par[j] = get_par(par, i)

def get_par(par, p):
    while par[p] != None:
        p = par[p]
    return par[p]

N = int(input())
points = []
edges = []
for i in range(N):
    x,y = map(int, input().split())
    points.append([x,y,i])
points.sort()
for i in range(N-1):
    edges.append((abs(points[i][0] - points[i+1][0]), points[i][2], points[i+1][2]))
points.sort(key=lambda x:x[1])
for i in range(N-1):
    edges.append((abs(points[i][1] - points[i+1][1]), points[i][2], points[i+1][2]))
edges.sort(key=lambda x:x[0], reverse=True)

par = [None] * N
cost = 0
count = 0
points.sort()
while count < N - 1:
    c, i, j = edges.pop()
    if get_par(points, i) == get_par(points, j):
        continue
    unite(points, i, j)
    cost += c
    count += 1
print(cost)

Buggy submission (verdict: Runtime Error):

def update_tree(par, a, b):
    frm = par[a][0] if par[par[a][0]][1] < par[par[b][0]][1] else par[b][0]
    to = par[b][0] if frm == par[a][0] else par[a][0]
    if par[par[frm][0]][1] > par[par[to][0]][1]:
        par[par[to][0]][1] = par[par[frm][0]][1]
    
    while par[frm][0] != par[par[frm][0]][0]: 
        par[frm][0], frm = to, par[frm][0]
    par[frm][0] = to

def get_par(par, p):
    while par[p][0] != par[p][1]:
        p = par[p][0]
    return p

manhattan = lambda x,y:min(abs(x[0] - y[0]), abs(x[1]- y[1]))
N = int(input())
points = []
edges = []
for i in range(N):
    x,y = map(int, input().split())
    points.append([i,i,[x,y]])
points.sort()
for i in range(N-1):
    edges.append((abs(points[i][2][0], points[i+1][2][0]), i+1, i))
points.sort(key=lambda x:x[1])
for i in range(N-1):
    edges.append((abs(points[i][2][1], points[i+1][2][1]), i+1, i))
edges.sort(key=lambda x:x[0], reverse=True)
cost = 0
count = 0
while count < N - 1:
    edge = edges.pop()
    if get_par(points, edge[1]) == get_par(points, edge[2]):
        continue
    cost += edge[0]
    count += 1
    update_tree(points, edge[1], edge[2])
print(cost)