Problem:


Score : 500 points

Problem Statement

There are N towns on a plane. The i-th town is located at the coordinates (x_i,y_i). There may be more than one town at the same coordinates.

You can build a road between two towns at coordinates (a,b) and (c,d) for a cost of min(|a-c|,|b-d|) yen (the currency of Japan). It is not possible to build other types of roads.

Your objective is to build roads so that it will be possible to travel between every pair of towns by traversing roads. At least how much money is necessary to achieve this?

Constraints

2 ≤ N ≤ 10^5

0 ≤ x_i,y_i ≤ 10^9

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print the minimum necessary amount of money in order to build roads so that it will be possible to travel between every pair of towns by traversing roads.

Sample Input 1

3
1 5
3 9
7 8

Sample Output 1

3

Build a road between Towns 1 and 2, and another between Towns 2 and 3. The total cost is 2+1=3 yen.

Sample Input 2

6
8 3
4 9
12 19
18 1
13 5
7 6

Sample Output 2

8



Sample input:
3
1 5
3 9
7 8


Sample output:
3

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    x, a, b = LI()
    if b <= a:
        print("delicious")
    elif b <= a + x:
        print("safe")
    else:
        print("dangerous")

    return

#B
def B():
    n = II()
    a = IR(n)
    check = [False] * (n + 1)
    check[1] = True
    now = a[0]
    for i in range(1,n+1):
        if check[now]:
            break
        if now == 2:
            print(i)
            return
        check[now] = True
        now = a[now - 1]
    print(-1)
    return

#C
def C():
    return

#D
def D():
    def find(x):
        if x == par[x]:
            return x
        par[x] = find(par[x])
        return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y: return False
        par[y] = x
        return True
    def solve(x):
        for i in range(n-1):
            x, y, z = xy[i]
            vx, vy, v = xy[i + 1]
            z, v = min(z, v), max(z, v)
            edg[x+i] = (min(abs(vx - x), abs(vy - y)), z, v)
    n = II()
    par = [i for i in range(n)]
    xy = [None] * n
    for i in range(n):
        x, y = LI()
        xy[i] = (x, y, i)
    xy.sort()
    edg = [None] * (2 * n - 2)
    solve(0)
    xy.sort(key=lambda x: x[1])
    solve(n-1)
    ans = 0
    a = 0
    edg.sort()
    for value, p0, p1 in edg:
        if a == n:
            break
        if unite(p0, p1):
            a += 1
            ans += value
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix

N = int(input())
iXY = [[i] + list(map(int, input().split())) for i in range(N)]

P = []
for j in [1, 2]:
  iXY.sort(key=lambda a: a[j])
  for i in range(1, N):
    i0, x0, y0 =  iXY[i - 1]
    i1, x1, y1 =  iXY[i]
    P.append((min(abs(x1 - x0), abs(y1 - y0)), i0, i1))

d, i, j = zip(*P)
G = csr_matrix((d, (i, j)))
mst = minimum_spanning_tree(G)
print(int(mst.sum()))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

import sys
input = sys.stdin.readline

parent_node = []

def get_parent(ind):
    global parent_node
    if ind != parent_node[ind]:
        parent_node[ind] = get_parent(parent_node[ind])
    return parent_node[ind]



def main():
    num = int(input())

    data = defaultdict(tuple)

    for i in range(num):
        x, y = map(int, input().split())
        data[i] = (x, y)

    data_sort = sorted(data.items(), key=lambda x: x[1][0])
    data_x = [ele for ele, ele2 in data_sort]
    data_sort = sorted(data.items(), key=lambda x: x[1][1])
    data_y = [ele for ele, ele2 in data_sort]

    cost_data = [0 for i in range((num - 1) * 2)]
    for i in range(len(data_x) - 1):
        a, b = data_x[i], data_x[i + 1]
        cost = abs(data[a][0] - data[b][0])
        cost_data[i] = a, b, cost
    for i in range(len(data_y) - 1):
        a, b = data_y[i], data_y[i + 1]
        cost = abs(data[a][1] - data[b][1])
        cost_data[i + len(data_x) - 1] = a, b, cost

    cost_data.sort(key=lambda x: x[2])
    global parent_node
    parent_node = [i for i in range(num)]

    ans = 0
    for i in range(len(cost_data)):
        a, b, cost = cost_data[i]
        a_parent = get_parent(a)
        b_parent = get_parent(b)
        if a_parent != b_parent:
            ans += cost
            parent_node[min(a_parent, b_parent)] = max(a_parent, b_parent)

    print(ans)





if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
def solve(n, x, y):
    def dist(i, j):
        return min(abs(x[i]-x[j]), abs(y[i]-y[j]))
    que = []
    for v in [x, y]:
        p = np.argsort(v)
        for i in range(n-1):
            u, v = p[i], p[i+1]
            que.append((u, v, dist(u, v)))
    parent = {i: i for i in range(n)}
    def find(i):
        if parent[i] == i:
            return i
        else:
            j = find(parent[i])
            parent[i] = j
            return j
    ans = 0
    for u, v, d in sorted(que, key=lambda _: _[2]):
        u = find(u)
        v = find(v)
        if u != v:
            ans += d
            parent[u] = v
    return ans

n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())
print(solve(n, x, y))

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
def solve(n, x, y):
    def dist(i, j):
        return min(abs(x[i]-x[j]), abs(y[i]-y[j]))
    que = []
    for v in [x, y]:
        p = np.argsort(v)
        for i in range(n-1):
            u, v = p[i], p[i+1]
            que.append((u, v, dist(u, v)))
    parent = {i: i for i in range(n)}
    def find(i):
        if parent[i] == i:
            return i
        else:
            j = find(parent[i])
            parent[i] = j
            return j
    que = deque(sorted(que, key=lambda _: _[2]))
    ans = 0
    while que:
        u, v, d = que.popleft()
        u = find(u)
        v = find(v)
        if u != v:
            ans += d
            parent[u] = v
    return ans

n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())
print(solve(n, x, y))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

def MST(n, E):
    def par(m):
        if UF[m] == m:
            return m
        ret = par(UF[m])
        UF[m] = ret
        return ret
    
    UF = [i for i in range(n)]
    E = sorted(E, key=lambda x: x[2])
    ans = 0
    for i, j, d in E:
        if par(i) != par(j):
            ans += d
            UF[par(i)] = par(j)
    return ans

N = int(input())

X = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((i, x, y))

F = []
Y = sorted(X, key = lambda x: x[1])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][1]-Y[i][1])))

Y = sorted(X, key = lambda x: x[2])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][2]-Y[i][2])))

print(MST(N, F))

Submission status: Runtime Error

Solution code:
def MST(n, E):
    def par(m):
        if UF[m] == m:
            return m
        ret = par(UF[m])
        UF[m] = ret
        return ret
    
    UF = [i for i in range(n)]
    E = sorted(E, key=lambda x: x[2])
    ans = 0
    for i, j, d in E:
        if par(i) != par(j):
            ans += d
            UF[par(i)] = par(j)
    return ans

N = int(input())

X = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((i, x, y))

F = []
Y = sorted(X, key = lambda x: x[1])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][1]-Y[i][1])))

Y = sorted(X, key = lambda x: x[2])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][2]-Y[i][2])))

print(MST(N, F))

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:

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)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
N=int(input())
city=[]
for i in range(N):
    x,y=map(int,input().split())
    city.append((i,x,y))
city.sort(key=lambda x:x[1])
data=[]
for i in range(N-1):
    data.append((city[i][0],city[i+1][0],city[i+1][1]-city[i][1]))
city.sort(key=lambda y:y[2])
for i in range(N-1):
    data.append((city[i][0],city[i+1][0],city[i+1][2]-city[i][2]))
data.sort(key=lambda d:d[2])
idx=[-1]*N
def find(idx,x):
    if idx[x]<0:
        return x
    elif idx[x]>=0:
        idx[x]=find(idx,idx[x])
        return idx[x]
ans=0
for q in range(len(data)):
    i,j,d=data[q]
    iidx=find(idx,i)
    jidx=find(idx,j)
    if iidx==jidx:
        continue
    elif idx[iidx]>=idx[jidx]:
        idx[iidx]+=idx[jidx]
        idx[jidx]=iidx
        ans+=d
    elif idx[iidx]<idx[jidx]:
        idx[jidx]+=idx[iidx]
        idx[iidx]=jidx
        ans+=d
print(ans)

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

#D
def root(x):
    if x == par[x]:
        return x
    par[x] = root(par[x])
    return par[x]

def same(x,y):
    return root(x) == root(y)

def unite(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
n = I()
v = LIR(n)
l = defaultdict(int)
for i in range(n):
    v[i].append(i)
par = [i for i in range(n)]
rank = [0 for i in range(n)]
v.sort(key = lambda x:x[0])
for i in range(n-1):
    l[i] = [v[i][2],v[i+1][2],v[i+1][0]-v[i][0]]
v.sort(key = lambda x:x[1])
for i in range(n-1):
    l[i+n-1] = [v[i][2],v[i+1][2],v[i+1][1]-v[i][1]]
print(l)
l.sort(key = lambda x:x[2])
k = 0
ans = 0
for i in range(2*n-2):
    x,y,c = l[i]
    if not same(x,y):
        k += 1
        ans += c
        unite(x,y)
    if k == n-1:break
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Runtime Error

Solution code:
import sys
from  heapq import heappush, heappop, heapify

N=input()

par=[ i for i in range(N) ]

def root(x):
	if par[x]==x:
		return x
	else:
		par[x]=root( par[x] )
		return par[x]

def same(x,y):
	return root(x)==root(y)

def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y: return
	par[x]=y



X=[]
Y=[]
for i in range(N):
	x,y=map(int, sys.stdin.readline().split()) 
	X.append( (x,i) )
	Y.append( (y,i) )

X.sort(key=lambda x: x[0])
Y.sort(key=lambda x: x[0])

hq=[]
for i in range(N-1):
	d=abs( X[i+1][0]-X[i][0] )
	x1=X[i][1]
	x2=X[i+1][1]
	heappush( hq, (d,x1,x2) )

	d=abs( Y[i+1][0]-Y[i][0] )
	x1=Y[i][1]
	x2=Y[i+1][1]
	heappush( hq, (d,x1,x2) )


ans=0
while hq:
	d,a,b=heappop(hq)
	if not same(a,b):
		ans+=d
		unite(a,b)
		
print ans

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n: int) -> None:
        #マイナスならルートでその深さを表す。プラスならルートのノードを指す。
        self.nodes = [-1]*(n+1)
 
    def find_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find_root(self.nodes[x])
            return self.nodes[x]
 
    def unite(self, x: int, y: int) -> None:
        x, y = self.find_root(x), self.find_root(y)
        #浅い方につなぐ
        if (x != y):
            if (x < y):
                self.nodes[y] += self.nodes[x]
                self.nodes[x] = y
            else:
                self.nodes[x] += self.nodes[y]
                self.nodes[y] = x
        
    def is_same(self, x: int, y: int) -> bool:
        return self.find_root(x) == self.find_root(y)

from operator import itemgetter

N = int(input())
G = [[i] + list(map(int, input().split())) for i in range(N)]

#X,Yそれぞれでソートして各都市の最短距離を求める
G_sorted_by_x = sorted(G, key=itemgetter(1))
G_sorted_by_y = sorted(G, key=itemgetter(2))
R = []
for i in range(N-1):
    i0, x0, _ = G_sorted_by_x[i]
    i1, x1, _ = G_sorted_by_x[i+1]
    R.append((x1-x0, i0, i1))
    i0, _, y0 = G_sorted_by_y[i]
    i1, _, y1 = G_sorted_by_y[i+1]
    R.append((y1-y0, i0, i1))

R_sorted_by_cost = sorted(R, key=itemgetter(0))

#print(R_sorted_by_cost)

uf = UnionFind(N)
total_cost = 0
for cost, i, j in R_sorted_by_cost:
    if (not uf.is_same(i, j)):
        uf.unite(i, j)
        total_cost += cost
    #print((cost, i, j))
print(total_cost)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n: int) -> None:
        #マイナスならルートでその深さを表す。プラスならルートのノードを指す。
        self.nodes = [-1]*n
 
    def find_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find_root(self.nodes[x])
            return self.nodes[x]
 
    def unite(self, x: int, y: int) -> None:
        x, y = self.find_root(x), self.find_root(y)
        #浅い方につなぐ
        if (x != y):
            if (x < y):
                self.nodes[y] += self.nodes[x]
                self.nodes[x] = y
            else:
                self.nodes[x] += self.nodes[y]
                self.nodes[y] = x
        
    def is_same(self, x: int, y: int) -> bool:
        return self.find_root(x) == self.find_root(y)

from operator import itemgetter

N = int(input())
G = [[i] + list(map(int, input().split())) for i in range(N)]

#X,Yそれぞれでソートして各都市の最短距離を求める
G_sorted_by_x = sorted(G, key=itemgetter(1))
G_sorted_by_y = sorted(G, key=itemgetter(2))
R = []
for i in range(N-1):
    i0, x0, _ = G_sorted_by_x[i]
    i1, x1, _ = G_sorted_by_x[i+1]
    R.append((x1-x0, i0, i1))
    i0, _, y0 = G_sorted_by_y[i]
    i1, _, y1 = G_sorted_by_y[i+1]
    R.append((y1-y0, i0, i1))

R_sorted_by_cost = sorted(R, key=itemgetter(0))

#print(R_sorted_by_cost)

uf = UnionFind(N)
total_cost = 0
for cost, i, j in R_sorted_by_cost:
    if (not uf.is_same(i-1, j-1)):
        uf.unite(i-1, j-1)
        total_cost += cost
    #print((cost, i, j))
print(total_cost)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n: int) -> None:
        #マイナスならルートでその深さを表す。プラスならルートのノードを指す。
        self.nodes = [-1]*n
 
    def find_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find_root(self.nodes[x])
            return self.nodes[x]
 
    def unite(self, x: int, y: int) -> None:
        x, y = self.find_root(x), self.find_root(y)
        #浅い方につなぐ
        if (x != y):
            if (x < y):
                self.nodes[y] += self.nodes[x]
                self.nodes[x] = y
            else:
                self.nodes[x] += self.nodes[y]
                self.nodes[y] = x
        
    def is_same(self, x: int, y: int) -> bool:
        return self.find_root(x) == self.find_root(y)

from operator import itemgetter

N = int(input())
G = [[i] + list(map(int, input().split())) for i in range(N)]

#X,Yそれぞれでソートして各都市の最短距離を求める
G_sorted_by_x = sorted(G, key=itemgetter(1))
G_sorted_by_y = sorted(G, key=itemgetter(2))
R = []
for i in range(N-1):
    i0, x0, _ = G_sorted_by_x[i]
    i1, x1, _ = G_sorted_by_x[i+1]
    R.append((x1-x0, i0, i1))
    i0, _, y0 = G_sorted_by_y[i]
    i1, _, y1 = G_sorted_by_y[i+1]
    R.append((y1-y0, i0, i1))

R_sorted_by_cost = sorted(R, key=itemgetter(0))

#print(R_sorted_by_cost)

uf = UnionFind(N)
total_cost = 0
for cost, i, j in R_sorted_by_cost:
    if (not uf.is_same(i, j)):
        uf.unite(i, j)
        total_cost += cost
    #print((cost, i, j))
print(total_cost)

Submission status: Runtime Error

Solution code:
import heapq

def add(i,pj,T):
    if T[i]['p']!=i:
        add(T[i]['p'],pj,T)
    T[i]['p']=pj
    
def parent(i,T):
    if T[i]['p']!=i:
        T[i]['p']= parent(T[i]['p'],T)
        return T[i]['p']
    else:
        return i

N=int(input())
town=[]
for i in range(N):
    x,y=list(map(int,input().split()))
    town.append([i,x,y])
townX=sorted(town,key=lambda x:x[1])
townY=sorted(town,key=lambda x:x[2])
road=[]
for i in range(1,N):
    heapq.heappush(road,[townX[i][1]-townX[i-1][1],townX[i-1][0],townX[i][0]])
for i in range(1,N):
    heapq.heappush(road,[townY[i][2]-townY[i-1][2],townY[i-1][0],townY[i][0]])

vi=0
ans=0
tree={i:{'p':i,'h':0} for i in range(N)}
while vi<N-1:
    d,u,v = heapq.heappop(road)
    pu=parent(u,tree)
    pv=parent(v,tree)
    if pu == pv:
        continue
    elif tree[pu]['h']<tree[pv]['h']:
        add(u,pv,tree)
    elif tree[pu]['h']==tree[pv]['h']:
        add(u,pv,tree)
        tree[pu]['h']+=1
    else:
        add(v,pu,tree)
    vi+=1
    ans+=d
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
def cost(a, b, c, d):
    return min(abs(a-c), abs(b-d))

N = int(input())
T, Visit = [], {}
for i in range(N):
    x, y = map(int, input().split())
    Visit[(x, y)] = False
    if (x, y) not in T:
        T.append((x, y))
lenT = len(T)
Tx, Ty = sorted(T, key = lambda t:t[0]), sorted(T, key = lambda t:t[1])

now = Tx[0]
Visit[now] = True
Q = [(cost(Tx[0][0], Tx[0][1], Tx[1][0], Tx[1][1]), Tx[1])]
nowy = Ty.index(now)
if nowy == 0:
    Q.append((cost(now[0], now[1], Ty[1][0], Ty[1][1]), Ty[1]))
elif nowy == lenT-1:
    Q.append((cost(now[0], now[1], Ty[-2][0], Ty[-2][1]), Ty[-2]))
else:
    Q.append((cost(now[0], now[1], Ty[nowy-1][0], Ty[nowy-1][1]), Ty[nowy-1]))
    Q.append((cost(now[0], now[1], Ty[nowy+1][0], Ty[nowy+1][1]), Ty[nowy-1]))
heapq.heapify(Q)
search = [-1, 1]
Total = 0
while Q:
    nowCost, now = heapq.heappop(Q)
    if Visit[now] == False:
        Total += nowCost
        Visit[now] = True
        nowx, nowy = Tx.index(now), Ty.index(now)
        for i in search:
            if 0 <= nowx + i <= lenT-1:
                if Visit[Tx[nowx+i]] == False:
                   heapq.heappush(Q, (cost(now[0], now[1], Tx[nowx+i][0], Tx[nowx+i][1]), Tx[nowx+i]))
            if 0 <= nowy + i <= lenT-1:
                if Visit[Ty[nowy+i]] == False:
                   heapq.heappush(Q, (cost(now[0], now[1], Ty[nowy+i][0], Ty[nowy+i][1]), Ty[nowy+i]))

print(Total)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([i,xy[0]])
    b.append([i,xy[1]])

a.sort(key=lambda x: x[1])
b.sort(key=lambda x: x[1])
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for i, x in a[:-1]:
    adj[i].append([a[i+1][1]-x, a[i+1][0]])
    adj[a[i+1][0]].append([a[i+1][1]-x, i])
for i, y in b[:-1]:
    adj[i].append([b[i+1][1]-y, b[i+1][0]])
    adj[b[i+1][0]].append([b[i+1][1]-y, i])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
while h:
    cost, node = heapq.heappop(h)
    if visited[node] != True and cost < d[node]:
        d[node] = cost
        visited[node] = True
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(sum(d))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([i,xy[0]])
    b.append([i,xy[1]])

a.sort(key=lambda x: x[1])
b.sort(key=lambda x: x[2])
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for i in range(len(a)-1):
    adj[a[i][0]].append([a[i+1][1]-a[i][1], a[i+1][0]])
    adj[a[i+1][0]].append([a[i+1][1]-a[i][1], a[i][0]])
for i in range(len(b)-1):
    adj[b[i][0]].append([b[i+1][1]-b[i][1], b[i+1][0]])
    adj[b[i+1][0]].append([b[i+1][1]-b[i][1], b[i][0]])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
while h:
    current = heapq.heappop(h)
    if visited[current[1]] != True and current[0] < d[current[1]]:
        d[current[1]] = current[0]
        visited[current[1]] = True
        cnt += 1
        if cnt == n:
            break
        for edge in adj[current[1]]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(sum(d))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

N = int(input())
town = [[int(x) for x in input().split()] + [i] for i in range(N)]


class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        return self.find(x) == self.find(y)


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(dict)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src][dst] = weight

    def get_nodes(self):
        return self.graph.keys()


class Kruskal(object):
    def __init__(self, graph):
        self.edge = []
        self.total = 0

        N = len(graph)
        g = graph.graph
        uf = UnionFind(N)

        Q = []
        for src, v in g.items():
            for dst, cost in v.items():
                heappush(Q, (cost, (src, dst)))

        while len(self.edge) < N - 1 and Q:
            cost, edge = heappop(Q)
            if uf.find(edge[0]) != uf.find(edge[1]):
                self.total += cost
                self.edge.append(edge)
                uf.union(*edge)


g = Graph()
for i in range(2):
    town = sorted(town, key=itemgetter(i))
    for j in range(N - 1):
        t1, t2 = town[j], town[j + 1]
        d = t2[i] - t1[i]
        g.add_edge(t1[2], t2[2], d)
print(Kruskal(g).total)

Submission status: Runtime Error

Solution code:
N = int(input())
T = [[i] + list(map(int, input().split())) for i in range(N)]
E = [[] for i in range(N)]
E = []
T.sort(key=lambda x: x[1])
for i in range(N-1):
    s, l = T[i:i+2]
    E.append([s[0], l[0], l[1]-s[1]])
T.sort(key=lambda x: x[2])
for i in range(N-1):
    s, l = T[i:i+2]
    E.append([s[0], l[0], l[2]-s[2]])
E.sort(key=lambda x: x[2])

Par = list(range(N))
def root(x):
    if Par[x] == x:
        return x
    else:
        Par[x] = root(Par[x])
        return Par[x]

def same(x, y):
    return root(x) == root(y)

def unite(x, y):
    x = root(x)
    y = root(y)
    if x != y:
        Par[x] = y

ans = 0
for e in E:
    if not same(e[0], e[1]):
        ans += e[2]
        unite(e[0], e[1])

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
x = []
y = []
for i in range(n):
    s = list(map(int, input().split()))
    x.append([s[0], i])
    y.append([s[1], i])

x.sort()
y.sort()

xdiff = []
ydiff = []
for i in range(1, n):
    xdiff.append([x[i][0] - x[i - 1][0], x[i - 1][1], x[i][1]])
    ydiff.append([y[i][0] - y[i - 1][0], y[i - 1][1], y[i][1]])

xdiff.sort()
ydiff.sort()

parent = [-1] * n

def getParent(index):
    if parent[index] == -1:
        return index
    else:
        return getParent(parent[index])

count = 0
ans = 0
xIndex = 0
yIndex = 0
while count != n - 1:
    if xIndex != n - 1:
        xTemp = xdiff[xIndex]
    if yIndex != n - 1:
        yTemp = ydiff[yIndex]

    if yIndex == n - 1 or (xIndex != n - 1 and xTemp[0] < yTemp[0]):
        xIndex += 1
        temp = xTemp
    else:
        yIndex += 1
        temp = yTemp

    parent1 = getParent(temp[1])
    parent2 = getParent(temp[2])
    if parent1 == parent2:
        continue
    else:
        count += 1
        ans += temp[0]
        parent[temp[1]] = temp[2]

print(ans)