Problem p03682 (python)

Fixed submission:
import sys
sys.setrecursionlimit(100000)
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []

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

def same(i,j):
    return get_par(i) == get_par(j)

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

for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(y-y2),i,j))
path.sort(key = lambda x:x[0],reverse=True)
par = [None]*N
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = path.pop()
    if same(i,j):continue
    unite(i,j)
    ans += c
    cnt += 1
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []

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

def same(i,j):
    return get_par(i) == get_par(j)

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

for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    if i>j:i,j = j,i
    heapq.heappush(path,(abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    if i>j:i,j = j,i
    heapq.heappush(path,(abs(y-y2),i,j))
par = [None]*N
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = heapq.heappop(path)
    if same(i,j):continue
    unite(i,j)
    ans += c
    cnt += 1
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []

def get_root(n):
    if tree[n][0] is None:return n
    return get_root(tree[n][0])

def in_tree(i,j):
    i = get_root(i)
    while i is not None:
        if   i == j : return True
        elif j < i  : i = tree[i][1]
        else        : i = tree[i][2]
    return False

def add_tree(i,j):
    i = get_root(i)
    j = get_root(j)
    c = i
    while c is not None:
        i = c
        if j < i : c = tree[i][1]
        else     : c = tree[i][2]
    tree[j][0] = i
    tree[i][1+(j>=i)] = j
    return

for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    if i>j:i,j = j,i
    heapq.heappush(path,(abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    if i>j:i,j = j,i
    heapq.heappush(path,(abs(y-y2),i,j))
tree = [[None]*3 for _ in [0]*N] #Parent,l-child,r-child
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = heapq.heappop(path)
    if in_tree(i,j):continue
    add_tree(i,j)
    ans += c
    cnt += 1
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
def bin_search_in(n,a):
    l = 0
    r = len(a)-1
    while l+1<r:
        i = (l+r)//2
        if a[i] <= n:
            l = i
        else:
            r = i
    return a[l]==n or a[r]==n
xy.sort()
path = []
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    heapq.heappush(path,(abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    heapq.heappush(path,(abs(y-y2),i,j))
union = [[i] for i in range(N)]
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = heapq.heappop(path)
    if bin_search_in(j,union[i]):continue
    while union[j]:
        heapq.heappush(union[i],heapq.heappop(union[j]))
    union[j] = union[i]
    ans += c
    cnt += 1
print(ans)