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:
import sys
import collections
import itertools

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

    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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def are_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def grouper(self):
        import itertools
        import operator
        par = operator.itemgetter(1)
        for _, group in itertools.groupby(
                sorted(enumerate(self.par), key=par), par):
            yield [i for i, par in group]

def sliding_window(n, seq):
    import collections
    import itertools
    return zip(*(collections.deque(itertools.islice(it, i), 0) or it
               for i, it in enumerate(itertools.tee(seq, n))))

Edge = collections.namedtuple('Edge', ['s', 't', 'cost'])

N = int(sys.stdin.readline())
xys = [[i] + list(map(int, line.split())) for i, line in enumerate(sys.stdin)]
edges = []
for (i1, x1, _), (i2, x2, _) in sliding_window(2, sorted(xys, key=lambda t: t[1])):
    edges.append(Edge(i1, i2, abs(x1 - x2)))
for (i1, _, y1), (i2, _, y2) in sliding_window(2, sorted(xys, key=lambda t: t[2])):
    edges.append(Edge(i1, i2, abs(y1 - y2)))
edges = sorted(edges, key=lambda e: e.cost)
uf = UnionFind(V)
min_cost = 0
for edge in edges:
    if not uf.are_same(edge.s, edge.t):
        uf.union(edge.s, edge.t)
        min_cost += edge.cost
print(min_cost)

Submission status: Runtime Error

Solution code:
import sys
import collections
import itertools

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

    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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def are_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def grouper(self):
        import itertools
        import operator
        par = operator.itemgetter(1)
        for _, group in itertools.groupby(
                sorted(enumerate(self.par), key=par), par):
            yield [i for i, par in group]

Edge = collections.namedtuple('Edge', ['s', 't', 'cost'])

N = int(sys.stdin.readline())
xys = [[i] + list(map(int, line.split())) for i, line in enumerate(sys.stdin)]
edges = []
for (i1, x1, y1), (i2, x2, y2) in itertools.combinations(xys, 2):
    e = Edge(i1, i2, min(abs(x1 - x2), abs(y1 - y2)))
    edges.append(e)
edges = sorted(edges, key=lambda e: e.cost)
uf = UnionFind(V)
min_cost = 0
for edge in edges:
    if not uf.are_same(edge.s, edge.t):
        uf.union(edge.s, edge.t)
        min_cost += edge.cost
print(min_cost)

Submission status: Runtime Error

Solution code:
import sys
import collections
import itertools

# COMMENT OUT BEFORE SUBMISSION
sys.stdin = f

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

    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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def are_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def grouper(self):
        import itertools
        import operator
        par = operator.itemgetter(1)
        for _, group in itertools.groupby(
                sorted(enumerate(self.par), key=par), par):
            yield [i for i, par in group]

Edge = collections.namedtuple('Edge', ['s', 't', 'cost'])

N = int(sys.stdin.readline())
xys = [[i] + list(map(int, line.split())) for i, line in enumerate(sys.stdin)]
edges = []
for (i1, x1, y1), (i2, x2, y2) in itertools.combinations(xys, 2):
    e = Edge(i1, i2, min(abs(x1 - x2), abs(y1 - y2)))
    edges.append(e)
edges = sorted(edges, key=lambda e: e.cost)
uf = UnionFind(V)
min_cost = 0
for edge in edges:
    if not uf.are_same(edge.s, edge.t):
        uf.union(edge.s, edge.t)
        min_cost += edge.cost
print(min_cost)

Submission status: Runtime Error

Solution code:
n = int(input())
p = [list(map(int, input().split())) for i in range(n)]
# x,yだけのリストを作る。座標順にソートもします。
x = sorted([[p[i][0], i] for i in range(n)])
y = sorted([[p[i][1], i] for i in range(n)])
# x,yについて隣り合ったものだけをedgeとしてみればよい（これもソートします）
edge = sorted([abs(x[i][0] - x[i-1][0]), x[i][1], x[i-1][1]] + [abs(y[i][0] - y[i-1][0]), y[i][1], y[i-1][1]])
# Union-Find
group = [i for i in range(n)]
def findParent(i):
    if i == group[i]:
        return i
    else:
        group[i] = findParent(group[i])
        return group[i]
def merge(i, j):
    i = findParent(i)
    j = findParent(j)
    group[i] = j
# クラスカル法で最小全域木の重みを求めます
ret = 0
# TLE対策
useedge = 0
for e in edge:
    weight, a, b = e
    if findParent(a) != findParent(b):
        merge(a, b)
        ret += weight
        useedge += 1
        if useedge == n-1:
            break
print(ret)

Submission status: Runtime Error

Solution code:
n = int(input())
p = [list(map(int, input().split())) for i in range(n)]
# x,yだけのリストを作る。座標順にソートもします。
x = sorted([[p[i][0], i] for i in range(n)])
y = sorted([[p[i][1], i] for i in range(n)])
# x,yについて隣り合ったものだけをedgeとしてみればよい（これもソートします）
edge = [0]*(2*n)
for i in range(n):
    edge[2*i] = [abs(x[i][0] - x[i-1][0]), x[i][1], x[i-1][1]])
    edge[2*i+1] = [abs(y[i][0] - y[i-1][0]), y[i][1], y[i-1][1]]
edge.sort()
# Union-Find
group = [i for i in range(n)]
def findParent(i):
    if i == group[i]:
        return i
    else:
        group[i] = findParent(group[i])
        return group[i]
def merge(i, j):
    i = findParent(i)
    j = findParent(j)
    group[i] = j
# クラスカル法で最小全域木の重みを求めます
ret = 0
for e in edge:
    weight, a, b = e
    if findParent(a) != findParent(b):
        merge(a, b)
        ret += weight
print(ret)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import heapq
N = input()
a = []
for i in range(N):
	x,y=map(int,raw_input().split())
	a.append((i,x,y))

#a => point,x,y
a1=sorted(a, key=lambda x: x[1])
a2=sorted(a, key=lambda x: x[2])


#Union Find
#初めは各頂点が根
par=[ i for i in range(N) ]
#木の根を求める
def root(x):
	if par[x]==x:
		return x
	else:
		r=root(par[x])
		#経路圧縮
		par[x]=r
		return r
#xとyが同じ集合に属するか
def same(x,y):
	return root(x)==root(y)

#xとyが同じ根に所属していた場合、連結
def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y:
		return
	else:
		par[x]=y


b=[]
for i in range(N-1):
	# len_x,x,y
	heapq.heappush( b, ( abs(a1[i+1][1]-a1[i][1]),a1[i][0],a1[i+1][0],  ))

for i in range(N-1):
	# len_y,x,y
	heapq.heappush( b, ( abs(a2[i+1][2]-a2[i][2]),a2[i][0],a2[i+1][0],  ))

#print "# b"
#print b


ans=0
cnt=0
for i in range(len(b)):
	if cnt==N-1:
		break
	val=heapq.heappop(b)
	#２点が同じ根でない場合は、木を結合する
	if not same(val[1],val[2]):
		unite(val[1],val[2])
		ans+=val[0]
		cnt+=1

print ans

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import heapq
N = input()
a = []
for i in range(N):
	x,y=map(int,raw_input().split())
	a.append((i,x,y))

#a => point,x,y
a1=sorted(a, key=lambda x: x[1])
a2=sorted(a, key=lambda x: x[2])


#Union Find
#初めは各頂点が根
par=[ i for i in range(N) ]
#木の根を求める
def root(x):
	if par[x]==x:
		return x
	else:
		r=root(par[x])
		#経路圧縮
		par[x]=r
		return r
#xとyが同じ集合に属するか
def same(x,y):
	return root(x)==root(y)

#xとyが同じ根に所属していた場合、連結
def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y:
		return
	else:
		par[x]=y


b=[]
for i in range(N-1):
	# len_x,x,y
	heapq.heappush( b, ( abs(a1[i+1][1]-a1[i][1]),a1[i][0],a1[i+1][0],  ))

for i in range(N-1):
	# len_y,x,y
	heapq.heappush( b, ( abs(a2[i+1][2]-a2[i][2]),a2[i][0],a2[i+1][0],  ))

#print "# b"
#print b


ans=0
for i in range(len(b)):
	val=heapq.heappop(b)
	if not same(val[1],val[2]):
		unite(val[1],val[2])
		ans+=val[0]

print ans

Submission status: Runtime Error

Solution code:
def list_to_dict(val_list):
  return list(zip(range(0,len(val_list)), val_list))


class Edge():
    def __init__(self,_start,_end,_cost):
        self.start = _start
        self.end = _end
        self.cost = _cost
    def __str__(self):
    	return ",".join([str(self.start),str(self.end),str(self.cost)])


n = int(input())
#頂点集合V
V = [[int(_) for _ in input().split()] for i in range(n)]
dicV = list_to_dict(V)
# プリム法

# 集合Eの生成
E_x = sorted(dicV, key=lambda x:x[1][0])
E_y = sorted(dicV, key=lambda x:x[1][1])

edges = []
for i in range(len(E_x)-1):
    edges.append(Edge(E_x[i][0],E_x[i+1][0],E_x[i+1][1][0]-E_x[i][1][0]))
    edges.append(Edge(E_y[i][0],E_y[i+1][0],E_y[i+1][1][1]-E_y[i][1][1]))

edges.sort(key=lambda x:x.cost)

vertexes = [i for i in range(n)]

V = set()
E = []
sums = 0

print(len(edges))

while(len(V) < n):
	minedge = edges[0]
	for edge in edges:
		if edge.start not in V and edge.end not in V:
			continue
		if edge.start in V and edge.end in V:
			edges.remove(edge)
		if edge.cost < minedge.cost:
			minedge = edge
	V.add(minedge.start)
	V.add(minedge.end)
	sums += minedge.cost
	edges.remove(minedge)

print(sums)

Submission status: Runtime Error

Solution code:
def list_to_dict(val_list):
  return list(zip(range(0,len(val_list)), val_list))


class Edge():
    def __init__(self,_start,_end,_cost):
        self.start = _start
        self.end = _end
        self.cost = _cost
    def __str__(self):
    	return ",".join([str(self.start),str(self.end),str(self.cost)])


n = int(input())
#頂点集合V
V = [[int(_) for _ in input().split()] for i in range(n)]
dicV = list_to_dict(V)
# プリム法

# 集合Eの生成
E_x = sorted(dicV, key=lambda x:x[1][0])
E_y = sorted(dicV, key=lambda x:x[1][1])

edges = []
for i in range(len(E_x)-1):
    edges.append(Edge(E_x[i][0],E_x[i+1][0],E_x[i+1][1][0]-E_x[i][1][0]))
    edges.append(Edge(E_y[i][0],E_y[i+1][0],E_y[i+1][1][1]-E_y[i][1][1]))

edges.sort(key=lambda x:x.cost)

vertexes = [i for i in range(n)]

V = set()
E = []
sums = 0

while(len(V) < n):
	minedge = edges[0]
	for edge in edges:
		if edge.start in V and edge.end in V:
			edges.remove(edge)
		if edge.cost < minedge.cost:
			minedge = edge
	V.add(minedge.start)
	V.add(minedge.end)
	sums += minedge.cost
	edges.remove(minedge)

print(sums)

Submission status: Runtime Error

Solution code:
N = int(input())

P = [n for n in range(N)]
points = []

def root(a):
  if P[a] == a:
    return a
  P[a] = root(P[a])
  return P[a]

def is_same_set(a, b):
  return root(a) == root(b)

def unite(a, b):
  P[root(a)] = root(b)


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

xs = sorted([(x, i) for i, x, y in points], key=lambda p: p[0])
xedges = [(xs[n][1], xs[n+1][1], xs[n+1][0]-xs[n][0] ) for n in range(N-1)]
ys = sorted([(y, i) for i, x, y in points], key=lambda p:p[0])
yedges = [(ys[n][1], ys[n+1][1], ys[n+1][0]-ys[n][0]) for n in range(N-1)]

edges = xedges + yedges
edges.sort(key=lambda x: x[2])
res = 0
for edge in edges:
  i, j, cost = edge
  if not is_same_set(i, j):
    unite(i, j)
    res += cost

print(res)

Submission status: Runtime Error

Solution code:
from operator import itemgetter
from queue import deque

N = int(input())

xin = []
yin = []

for _ in range(N):
    x, y = map(int, input().split())
    xin.append(x)
    yin.append(y)
    
xin = sorted(list(enumerate(xin)), key=itemgetter(1))
yin = sorted(list(enumerate(yin)), key=itemgetter(1))

xd = []
yd = []

for i in range(N-1):
    xd.append((xin[i+1][1] - xin[i][1], (xin[i][0], xin[i+1][0])))
    yd.append((yin[i+1][1] - yin[i][1], (yin[i][0], yin[i+1][0])))
    
xdq = deque(sorted(xd))
ydq = deque(sorted(yd))

par = list(range(N))

def find(x):
    if x == par[x]:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
    
def union(x, y):
    px, py = find(x), find(y)
    if px != py:
        par[px] = py
    
ans = 0

while xdq or ydq:
    if xdq and (not ydq or xdq[0] < ydq[0]):
        d, (i, j) = xdq.popleft()
    else:
        d, (i, j) = ydq.popleft()
        
    if find(i) != find(j):
        ans += d
        union(i, j)
        
print(ans)

Submission status: Runtime Error

Solution code:
from operator import itemgetter
from queue import deque

N = int(input())

xin, yin = [], []
for _ in range(N):
    x, y = map(int, input().split())
    xin.append(x)
    yin.append(y)

x = sorted(list(enumerate(xin)), key=itemgetter(1))
y = sorted(list(enumerate(yin)), key=itemgetter(1))

xds = []
yds = []

for i in range(N-1):
    xds.append((x[i+1][1] - x[i][1],(x[i][0], x[i+1][0])))
    yds.append((y[i+1][1] - y[i][1],(y[i][0], y[i+1][0])))
    
xdq = deque(sorted(xds))
ydq = deque(sorted(yds))

par = list(range(N))

def find(x):
    if x == par[x]:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
def union(x, y):
    px, py = find(x), find(y)
    par[px] = py

ans = 0    
while xdq or ydq:
    if xdq and (not ydq or xdq[0] < ydq[0]):
        d, (i, j) = xdq.popleft()
    else:
        d, (i, j) = ydq.popleft()
        
    if find(i) != find(j):
        ans += d
        union(i, j)
print(ans)

Submission status: Runtime Error

Solution code:
from operator import itemgetter
from queue import deque

N = int(input())

x_in = []
y_in = []

for _ in range(N):
    x, y = list(map(int, input().split(" ")))
    x_in.append(x)
    y_in.append(y)

x_in = sorted(list(enumerate(x_in)), key=itemgetter(1))
y_in = sorted(list(enumerate(y_in)), key=itemgetter(1))

xd = []
yd = []

for i in range(N-1):
    xd.append((x_in[i+1][1]-x_in[i][1], (x_in[i][0], x_in[i+1][0])))
    yd.append((y_in[i+1][1]-y_in[i][1], (y_in[i][0], y_in[i+1][0])))
    
xdq = deque(sorted(xd))
ydq = deque(sorted(yd))

par = list(range(N))

def find(x):
    if x == par[x]:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
def union(x, y):
    px, py = find(x), find(y)
    if px != py:
        par[px] = py
        
ans = 0

while xdq or ydq:
    if xdq and (not ydq or xdq[0] < ydq[0]):
        d, (i, j) = xdq.popleft()
    else:
        d, (i, j) = ydq.popleft()
        
    if find(i) != find(j):
        ans += d
        union(i, j)
        
print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

def cal(d,xl):
    N=len(xl)
    for i in range(N-1):
        r1=abs(xl[i+1][0]-xl[i][0])
        try:
            l=d[r1]
            l.append([xl[i+1][1],xl[i][1]])
            d[r1]=l
        except:
            d[r1]=[[xl[i+1][1],xl[i][1]]]
    return d
N=int(input())
N=10**5
x=[[0,0] for _ in range(N)]
y=[[0,0] for _ in range(N)]
for i in range(N):
    x[i][0],y[i][0]=list(map(int,input().split()))
    x[i][1],y[i][1]=i,i
x=sorted(x,key=lambda l: l[0])
y=sorted(y,key=lambda l: l[0])
a=cal(cal({},x),y)
p=UnionFind(N)
c=0
cost=0
edgecount=0
while True:
    if(edgecount==N-1):
        print(cost)
        break
    try:
        l=a[c]
        for item in l:
            if(p.union(item[0],item[1])):
                cost+=c
                edgecount+=1
            
        c+=1
    except:
        c+=1
        continue

Submission status: Runtime Error

Solution code:
class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):

        s1 = self.find(x)
        s2 = self.find(y)
        self.table[s1] = s2

n = input()
uf = UnionFind3(n)

cities = [map(int, raw_input().split(" ")) + [i] for i in range(n)]
cities_x = sorted(cities, key=lambda a: a[0])
cities_y = sorted(cities, key=lambda a: a[1])
road = [[cities_x[i + 1][0] - cities_x[i][0], cities_x[i][2], cities_x[i + 1][2]] for i in range(n - 1)]
road += [[cities_y[i + 1][1] - cities_y[i][1], cities_y[i][2], cities_y[i + 1][2]] for i in range(n - 1)]
sum = 0L
for (cost, i, j) in sorted(road):
    if uf.find(i) != uf.find(j):
        uf.union(i, j)
        sum += long(cost)
print sum

Submission status: Runtime Error

Solution code:
class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):

        s1 = self.find(x)
        s2 = self.find(y)
        self.table[s1] = s2

n = input()
uf = UnionFind3(n)

cities = [map(int, raw_input().split(" ")) + [i] for i in range(n)]
print cities
cities_x = sorted(cities, key=lambda a: a[0])
cities_y = sorted(cities, key=lambda a: a[1])
road = [[cities_x[i + 1][0] - cities_x[i][0], cities_x[i][2], cities_x[i + 1][2]] for i in range(n - 1)]
road += [[cities_y[i + 1][1] - cities_y[i][1], cities_y[i][2], cities_y[i + 1][2]] for i in range(n - 1)]
sum = 0
for (cost, i, j) in sorted(road):
    if uf.find(i) != uf.find(j):
        uf.union(i, j)
        sum += cost
print sum

Submission status: Runtime Error

Solution code:
class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):

        s1 = self.find(x)
        s2 = self.find(y)
        self.table[s1] = s2

n = input()
uf = UnionFind3(n)

cities = [map(long, raw_input().split(" ")) + [long(i)] for i in range(n)]
print cities
cities_x = sorted(cities, key=lambda a: a[0])
cities_y = sorted(cities, key=lambda a: a[1])
road = [[cities_x[i + 1][0] - cities_x[i][0], cities_x[i][2], cities_x[i + 1][2]] for i in range(n - 1)]
road += [[cities_y[i + 1][1] - cities_y[i][1], cities_y[i][2], cities_y[i + 1][2]] for i in range(n - 1)]
sum = 0
for (cost, i, j) in sorted(road):
    if uf.find(i) != uf.find(j):
        uf.union(i, j)
        sum += cost
print sum

Submission status: Runtime Error

Solution code:
class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):

        s1 = self.find(x)
        s2 = self.find(y)
        self.table[s1] = s2

n = input()
uf = UnionFind3(n)

cities = [map(long, raw_input().split(" ")) + [i] for i in range(n)]
cities_x = sorted(cities, key=lambda a: a[0])
cities_y = sorted(cities, key=lambda a: a[1])
road = [[cities_x[i + 1][0] - cities_x[i][0], cities_x[i][2], cities_x[i + 1][2]] for i in range(n - 1)]
road += [[cities_y[i + 1][1] - cities_y[i][1], cities_y[i][2], cities_y[i + 1][2]] for i in range(n - 1)]
sum = 0
for (cost, i, j) in sorted(road):
    if uf.find(i) != uf.find(j):
        uf.union(i, j)
        sum += cost
print sum

Submission status: Runtime Error

Solution code:
class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):

        s1 = self.find(x)
        s2 = self.find(y)
        self.table[s1] = s2

n = input()
uf = UnionFind3(n)

cities = [map(int, raw_input().split(" ")) + [i] for i in range(n)]
cities_x = sorted(cities, key=lambda a: a[0])
cities_y = sorted(cities, key=lambda a: a[1])
road = [[cities_x[i + 1][0] - cities_x[i][0], cities_x[i][2], cities_x[i + 1][2]] for i in range(n - 1)]
road += [[cities_y[i + 1][1] - cities_y[i][1], cities_y[i][2], cities_y[i + 1][2]] for i in range(n - 1)]
sum = 0
for (cost, i, j) in sorted(road):
    if uf.find(i) != uf.find(j):
        uf.union(i, j)
        sum += cost
print sum

Submission status: Runtime Error

Solution code:
import math

max_val = 1000000000

def solve():
    n = int(input())
    l = []
    mat = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        l.append(list(map(int,input().split())))
        for j in range(i+1):
            mat[i][j] = min(abs(l[i][0]-l[j][0]), abs(l[i][1]-l[j][1]))
            mat[j][i] = mat[i][j]
            if(i == j):
                mat[i][j] = max_val
                mat[j][i] = mat[i][j]

    ans = 0
    hist = [0]
    l = hist[-1]

    while(len(hist) < n):
        index = l.index(min(l))
        index_x = hist[int(index / n)]
        index_y = index % n

        hist.append(index_y)
        l[index] = max_val
        ans += mat[index_x][index_y]
        mat[index_x][index_y] = max_val
        mat[index_y][index_x] = max_val
        l.extend(mat[hist[-1]])
    
    return ans



if(__name__ == "__main__"):
    print(solve())

Submission status: Runtime Error

Solution code:
#Built?
import numpy as np
import sys

n = int(input())
p = []
for i in range(n):
    p.append(list(map(int, input().split())))
    
    
#最小木問題プリム法
c = p    #city point
v = []    #vertex
e = []    #edge
v.append(c[0])
c.remove(c[0])

sumcost=0
while 1:
    mincost = sys.float_info.max
    for vp in v:
        for cp in c:
            cost = min(abs(vp[0]-cp[0]),abs(vp[1]-cp[1]))
            if mincost > cost:
                mincost = cost
    if shortestlen > 0:
        sumcost+=mincost
    v.append(cp)
    c.remove(cp)
    if len(p) == 0:
        break
        
print(sumcost)

Submission status: Runtime Error

Solution code:
#Built?
#最小木問題
import numpy as np
import math as mt
import sys

n = int(input())
p = []
for i in range(n):
    p.append(list(map(int, input().split())))
    
#プリム法
c = p    #city point
v = []    #vertex
e = []    #edge
v.append(c[0])
c.remove(c[0])

sumcost=0
while 1:
    mincost = sys.float_info.max
    stA = None
    stB = None
    for vp in v:
        for cp in c:
            cost = min(abs(vp[0]-cp[0]),abs(vp[1]-cp[1]))
            if mincost > cost:
                mincost = cost
                stA = vp
                stB = cp
    if shortestlen > 0:
        e.append([stA,stB])
        sumcost+=mincost
    v.append(stB)
    c.remove(stB)
    if len(p) == 0:
        break
        
print(sumcost)

Submission status: Runtime Error

Solution code:
import numpy as np

import sys

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

howmuch = np.zeros((N, N))

towngroup = np.array(list(range(N)))

for i in range(N):
    for j in range(i, N):
        howmuch[i][j] = min(abs(x[i] - x[j]), abs(y[i] - y[j]))

cheapbridge = np.argsort(howmuch.flatten())

cost = 0

for i in cheapbridge[(N*(N+1))//2:]:
    a = i // N
    b = i % N
    if towngroup[a] == towngroup[b]:
        continue

    cost += min(abs(x[a] - x[b]), abs(y[a] - y[b]))

    towngroup[towngroup == towngroup[b]] = towngroup[a]

    if len(set(towngroup)) == 1:
        print(cost)
        sys.exit()

Submission status: Runtime Error

Solution code:
import numpy as np

import sys

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

howmuch = np.zeros((N, N))

towngroup = np.array(list(range(N)))

for i in range(N):
    for j in range(i, N):
        howmuch[i][j] = min(abs(x[i] - x[j]), abs(y[i] - y[j]))

cheapbridge = np.argsort(howmuch.flatten())

cost = 0

for i in cheapbridge[(N*(N+1))//2:]:
    a = i // N
    b = i % N
    if towngroup[a] == towngroup[b]:
        print('hoooo')
        continue

    cost += min(abs(x[a] - x[b]), abs(y[a] - y[b]))

    towngroup[towngroup == towngroup[b]] = towngroup[a]

    if len(set(towngroup)) == 1:
        print(cost)
        sys.exit()

Submission status: Runtime Error

Solution code:
class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]
 
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]
 
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        self.table[s1] = s2
       
n = input()
uf=UnionFind3(n)
 
 
cities = [map(int,raw_input().split(" "))+[i] for i in range(n)]
 
cities_x = sorted(cities, key=lambda a:a[0])
cities_y = sorted(cities, key=lambda a:a[1])
 
road = [[cities_x[i+1][0]-cities_x[i][0],cities_x[i][2],cities_x[i+1][2]] for i in range(n-1)]
road +=[[cities_y[i+1][1]-cities_y[i][1],cities_y[i][2],cities_y[i+1][2]] for i in range(n-1)]
 
sum = 0
for (cost,i,j) in sorted(road):
    if(uf.find(i)!=uf.find(j)):
        uf.union(i,j)
        sum += cost
print sum

Submission status: Runtime Error

Solution code:
class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]
 
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]
 
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        self.table[s1] = s2

n = input()
uf=UnionFind3(10001)
 

cities = [map(int,raw_input().split(" "))+[i] for i in range(n)]
 
cities_x = sorted(cities, key=lambda a:a[0])
cities_y = sorted(cities, key=lambda a:a[1])
 
road = [[cities_x[i+1][0]-cities_x[i][0],cities_x[i][2],cities_x[i+1][2]] for i in range(n-1)]
road +=[[cities_y[i+1][1]-cities_y[i][1],cities_y[i][2],cities_y[i+1][2]] for i in range(n-1)]
 
sum = 0
for (cost,i,j) in sorted(road):
    if(uf.find(i)!=uf.find(j)):
        uf.union(i,j)
        sum += cost
 
print sum

Submission status: Runtime Error

Solution code:
class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]
 
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]
 
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        self.table[s1] = s2
       
n = input()
uf=UnionFind3(n)
 

cities = [map(int,raw_input().split(" "))+[i] for i in range(n)]
 
cities_x = sorted(cities, key=lambda a:a[0])
cities_y = sorted(cities, key=lambda a:a[1])
 
road = [[cities_x[i+1][0]-cities_x[i][0],cities_x[i][2],cities_x[i+1][2]] for i in range(n-1)]
road +=[[cities_y[i+1][1]-cities_y[i][1],cities_y[i][2],cities_y[i+1][2]] for i in range(n-1)]
 
sum = 0
for (cost,i,j) in sorted(road):
    if(uf.find(i)!=uf.find(j)):
        uf.union(i,j)
        sum += cost
 print sum

Submission status: Runtime Error

Solution code:

def distance(P, p1, p2):
    return min(abs(P[p1][1]-P[p2][1]), abs(P[p1][2]-P[p2][2]))
def root(CI, p):
    if CI[p] == p:
        return p
    else:
        CI[p] = root(CI, CI[p])
        return CI[p] 

N = int(input())
P = [[j]+[int(i) for i in input().split(' ')] for j in range(N)]
sortX = sorted(P,key=lambda x:x[1])
sortY = sorted(P,key=lambda x:x[2])
EX = [[sortX[i][0], sortX[i+1][0], distance(P,sortX[i][0],sortX[i+1][0])] for i in range(N-1)]
EY = [[sortY[i][0], sortY[i+1][0], distance(P,sortY[i][0],sortY[i+1][0])] for i in range(N-1)]
E = EX + EY
E = sorted(E, key=lambda x:x[2])
CI = [i for i in range(N)]
disSum = 0
for e in E:
    s,l = min(e[0],e[1]),max(e[0],e[1])
#     if CI[s] != CI[l]:
#         CI = list(map(lambda x:CI[s] if x == CI[l] else x, CI))
#         disSum += e[2]
    if root(CI, s) != root(CI, l):
        CI[root(CI, l)] = root(CI, s)
        disSum += e[2]
print(disSum)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1e9)
class obj:
    def __init__(self, N):
        self.fa = [i for i in range(N)]
    def find(self, x):
        if x == self.fa[x]:
            return x
        else:
            self.fa[x] = self.find(self.fa[x])
            return self.fa[x]

N = int(input())
node = [{"x":0, "y":0, "id":i} for i in range(N)]
edge = [{"u":0, "v":0, "d":0} for i in range(2*(N-1))]
ob = obj(N)
for i in range(N):
    node[i]["x"], node[i]["y"] = map(int, input().split())
    node[i]["id"] = i

xnode = sorted(node, key=lambda x:x["x"])
for i in range(N-1):
    edge[i]["u"] = xnode[i]["id"]
    edge[i]["v"] = xnode[i+1]["id"]
    edge[i]["d"] = xnode[i+1]["x"] - xnode[i]["x"]
ynode = sorted(node, key=lambda x:x["y"])
for i in range(N-1):
    edge[i+N-1]["u"] = ynode[i]["id"]
    edge[i+N-1]["v"] = ynode[i+1]["id"]
    edge[i+N-1]["d"] = ynode[i+1]["y"] - ynode[i]["y"]
dedge = sorted(edge, key=lambda x:x["d"])
ans = 0
for i in range(2*(N-1)):
    if ob.find(dedge[i]["u"]) != ob.find(dedge[i]["v"]):
        ans += dedge[i]["d"]
        ob.fa[ob.fa[dedge[i]["u"]]] = ob.fa[dedge[i]["v"]]
print(ans)