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: Accepted

Solution code:
import numpy as np 

class union_find:
	def __init__(self, size):
		# 負の値はルート (集合の代表) で集合の個数
		# 正の値は次の要素を表す
		self.size=size
		self.table = [-(i+1) for i in range(size)]
		self.num=[0 for i in range(size)]

	# 集合の代表を求める O(log(n))
	def find(self, x):
		if self.table[x] < 0:
			self.size+=-1
			return(x)
		else:
			# 経路の圧縮 木の高さ=2
			self.table[x] = self.find(self.table[x])
			return(self.table[x])

	# 併合 O(log(n))
	def unite(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 same(self, x, y):
		if self.find(x)==self.find(y):
			return(True)
		else:
			return(False)

	# 確定 O(nlog(n))
	def definite(self):
		for i in range(self.size):
			self.num[i]=self.find(i)
		return(True)


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

edge = []

argxl = np.argsort(xl)
argyl = np.argsort(yl)
soxl = np.sort(xl)
soyl = np.sort(yl)

for i in range(N-1):
	edge.append((soxl[i+1]-soxl[i], argxl[i], argxl[i+1]))
	edge.append((soyl[i+1]-soyl[i], argyl[i], argyl[i+1]))

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

uni = union_find(N)
res = 0
for dis, i, j in edge:
	if not uni.same(i,j):
		uni.unite(i,j)
		res += dis

print(res)

Submission status: Accepted

Solution code:
class DisjointSet(object):
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.num = n  # number of disjoint sets

    def union(self, x, y):
        self._link(self.find_set(x), self.find_set(y))

    def _link(self, x, y):
        if x == y:
            return
        self.num -= 1
        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def find_set(self, x):
        xp = self.parent[x]
        if xp != x:
            self.parent[x] = self.find_set(xp)
        return self.parent[x]

def read_data():
    N = int(input())
    xs = []
    ys = []
    for i in range(N):
        x, y = map(int, input().split())
        xs.append((x, i))
        ys.append((y, i))
    return N, xs, ys

def add_edges(xs):
    es = []
    prev_x, prev_i = xs[0]
    for x, i in xs[1:]:
        es.append((x - prev_x, prev_i, i))
        prev_x = x
        prev_i = i
    return es

def solve(N, xs, ys):
    xs.sort()
    ys.sort()
    es = add_edges(xs)
    es.extend(add_edges(ys))
    es.sort()
    ds = DisjointSet(N)
    cost = 0
    for d, i, j in es:
        if ds.find_set(i) == ds.find_set(j):
            continue
        ds.union(i, j)
        cost += d
    return cost

N, xs, ys = read_data()
print(solve(N, xs, ys))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


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 subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    N = I()
    a = []
    b = []
    for i in range(N):
        x,y = LI()
        a.append((x,i))
        b.append((y,i))
    a.sort()
    b.sort()
    t = []
    for i in range(1,N):
        t.append((a[i][0]-a[i-1][0], a[i][1], a[i-1][1]))
        t.append((b[i][0]-b[i-1][0], b[i][1], b[i-1][1]))
    t.sort()
    r = 0
    uf = UnionFind(N)
    for c,d,e in t:
        if uf.union(d,e):
            r += c

    return r

print(main())

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))
        
        self.n = len(labels)
        self.parents = [-1] * self.n
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}
    
    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]
    
    def union(self, x, y):
        super().union(self.d[x], self.d[y])
    
    def size(self, x):
        return super().size(self.d[x])
    
    def same(self, x, y):
        return super().same(self.d[x], self.d[y])
    
    def members(self, x):
        root = self.find(self.d[x])
        return [self.d_inv[i] for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [self.d_inv[i] for i, x in enumerate(self.parents) if x < 0]

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

    ufl = UnionFindLabel(nodes)
    nodes_sorted_by_x = sorted(nodes)
    nodes_sorted_by_y = sorted(nodes, key=lambda i: i[1])

    # edges = []
    # for i in range(N - 1):
    #     dx = abs(nodes_sorted_by_x[i][0] - nodes_sorted_by_x[i + 1][0])
    #     dy = abs(nodes_sorted_by_x[i][1] - nodes_sorted_by_x[i + 1][1])
    #     cost = min(dx, dy)
    #     edges.append((cost, nodes_sorted_by_x[i],  nodes_sorted_by_x[i + 1]))

    # for i in range(N - 1):
    #     dx = abs(nodes_sorted_by_y[i][0] - nodes_sorted_by_y[i + 1][0])
    #     dy = abs(nodes_sorted_by_y[i][1] - nodes_sorted_by_y[i + 1][1])
    #     cost = min(dx, dy)
    #     edges.append((cost, nodes_sorted_by_y[i],  nodes_sorted_by_y[i + 1]))

    # edges.sort()
        
    # ans = 0
    # for edge in edges:
    #     w, s, t = edge
    #     if not ufl.same(s, t):
    #         ans += w
    #         ufl.union(s, t)
    # print(ans)

    print(nodes_sorted_by_x)
    print(nodes_sorted_by_y)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))
        
        self.n = len(labels)
        self.parents = [-1] * self.n
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}
    
    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]
    
    def union(self, x, y):
        super().union(self.d[x], self.d[y])
    
    def size(self, x):
        return super().size(self.d[x])
    
    def same(self, x, y):
        return super().same(self.d[x], self.d[y])
    
    def members(self, x):
        root = self.find(self.d[x])
        return [self.d_inv[i] for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [self.d_inv[i] for i, x in enumerate(self.parents) if x < 0]

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

    ufl = UnionFindLabel(nodes)
    nodes_sorted_by_x = sorted(nodes)
    nodes_sorted_by_y = sorted(nodes, key=lambda i: i[1])

    edges = []
    for i in range(N - 1):
        dx = abs(nodes_sorted_by_x[i][0] - nodes_sorted_by_x[i + 1][0])
        dy = abs(nodes_sorted_by_x[i][1] - nodes_sorted_by_x[i + 1][1])
        cost = min(dx, dy)
        edges.append((cost, nodes_sorted_by_x[i],  nodes_sorted_by_x[i + 1]))

    for i in range(N - 1):
        dx = abs(nodes_sorted_by_y[i][0] - nodes_sorted_by_y[i + 1][0])
        dy = abs(nodes_sorted_by_y[i][1] - nodes_sorted_by_y[i + 1][1])
        cost = min(dx, dy)
        edges.append((cost, nodes_sorted_by_y[i],  nodes_sorted_by_y[i + 1]))

    edges.sort()
    
    print(nodes_sorted_by_x)
    print(nodes_sorted_by_y)

    # ans = 0
    # for edge in edges:
    #     w, s, t = edge
    #     if not ufl.same(s, t):
    #         ans += w
    #         ufl.union(s, t)
    # print(ans)

    # print(nodes_sorted_by_x)
    # print(nodes_sorted_by_y)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))
        
        self.n = len(labels)
        self.parents = [-1] * self.n
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}
    
    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]
    
    def union(self, x, y):
        super().union(self.d[x], self.d[y])
    
    def size(self, x):
        return super().size(self.d[x])
    
    def same(self, x, y):
        return super().same(self.d[x], self.d[y])
    
    def members(self, x):
        root = self.find(self.d[x])
        return [self.d_inv[i] for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [self.d_inv[i] for i, x in enumerate(self.parents) if x < 0]

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

    ufl = UnionFindLabel(nodes)
    nodes_sorted_by_x = sorted(nodes)
    nodes_sorted_by_y = sorted(nodes, key=lambda i: i[1])

    edges = []
    for i in range(N - 1):
        dx = abs(nodes_sorted_by_x[i][0] - nodes_sorted_by_x[i + 1][0])
        dy = abs(nodes_sorted_by_x[i][1] - nodes_sorted_by_x[i + 1][1])
        cost = min(dx, dy)
        edges.append((cost, nodes_sorted_by_x[i],  nodes_sorted_by_x[i + 1]))

    for i in range(N - 1):
        dx = abs(nodes_sorted_by_y[i][0] - nodes_sorted_by_y[i + 1][0])
        dy = abs(nodes_sorted_by_y[i][1] - nodes_sorted_by_y[i + 1][1])
        cost = min(dx, dy)
        edges.append((cost, nodes_sorted_by_y[i],  nodes_sorted_by_y[i + 1]))

    edges.sort()
    
    ans = 0
    for edge in edges:
        w, s, t = edge
        if not ufl.same(s, t):
            ans += w
            ufl.union(s, t)
    print(ans)

    # print(nodes_sorted_by_x)
    # print(nodes_sorted_by_y)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))
        
        self.n = len(labels)
        self.parents = [-1] * self.n
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}
    
    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]
    
    def union(self, x, y):
        super().union(self.d[x], self.d[y])
    
    def size(self, x):
        return super().size(self.d[x])
    
    def same(self, x, y):
        return super().same(self.d[x], self.d[y])
    
    def members(self, x):
        root = self.find(self.d[x])
        return [self.d_inv[i] for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [self.d_inv[i] for i, x in enumerate(self.parents) if x < 0]

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

    ufl = UnionFindLabel(nodes)
    nodes_sorted_by_x = sorted(nodes)
    nodes_sorted_by_y = sorted(nodes, key=lambda i: i[1])

    edges = []
    for i in range(len(nodes_sorted_by_x) - 1):
        dx = abs(nodes_sorted_by_x[i][0] - nodes_sorted_by_x[i + 1][0])
        dy = abs(nodes_sorted_by_x[i][1] - nodes_sorted_by_x[i + 1][1])
        cost = min(dx, dy)
        edges.append((cost, nodes_sorted_by_x[i],  nodes_sorted_by_x[i + 1]))

    for i in range(len(nodes_sorted_by_y) - 1):
        dx = abs(nodes_sorted_by_y[i][0] - nodes_sorted_by_y[i + 1][0])
        dy = abs(nodes_sorted_by_y[i][1] - nodes_sorted_by_y[i + 1][1])
        cost = min(dx, dy)
        edges.append((cost, nodes_sorted_by_y[i],  nodes_sorted_by_y[i + 1]))

    edges.sort()
    
    
    ans = 0
    for edge in edges:
        w, s, t = edge
        if not ufl.same(s, t):
            ans += w
            ufl.union(s, t)
    print(ans)

    # print(nodes_sorted_by_x)
    # print(nodes_sorted_by_y)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
city=[0]*N
for i in range(N):
    x,y=map(int,input().split())
    city[i]=(i,x,y)
city.sort(key=lambda x:x[1])
data=[(city[i][0],city[i+1][0],city[i+1][1]-city[i][1]) for i in range(N-1)]
city.sort(key=lambda x:x[2])
data+=[(city[i][0],city[i+1][0],city[i+1][2]-city[i][2]) for i in range(N-1)]
data.sort(key=lambda x:x[2])
f = list(range(N))
costs = [0] * N
def find(x):
    if f[x] != x:
        f[x] = find(f[x])
    return f[x]
res = 0
for i, j, k in data:
    fi, fj = find(i), find(j)
    if fi == fj:
        continue
    else:
        f[fi] = fj
        res += k
print(res)

Submission status: Runtime Error

Solution code:
from heapq import heappop,heappush
n=int(input())
s=[]
for i in range(n):
    s.append(list(map(int,input().split()))+[i])
x=sorted(s,key=lambda x:x[0])
y=sorted(s,key=lambda x:x[1])
t=[[]for i in range(n)]
for i in range(1,n):
    t[x[i-1][2]].append([x[i][0]-x[i-1][0],x[i][2]])
    t[x[i][2]].append([x[i][0]-x[i-1][0],x[i-1][2]])
    t[y[i-1][2]].append([y[i][1]-y[i-1][1],y[i][2]])
    t[y[i][2]].append([y[i][1]-y[i-1][1],y[i-1][2]])
s=[True]*n
s[0]=False
a=0
h=t[0]
heapify(h)
while h:
    p,q=heappop(h)
    if s[q]:
        s[q]=False
        a+=p
        for i,j in t[q]:
            if s[j]:
                heappush(h,[i,j])
print(a)

Submission status: Runtime Error

Solution code:
n=int(input())
s=[]
for i in range(n):
    a,b=map(int,input().split())
    s.append([a,b,i])
x=sorted(s)
y=sorted(s,key=lambda x:x[1])
t=[]
for i in range(1,n):
    t.append([x[i-1][2],x[i][2],x[i][0]-x[i-1][0]])
    t.append([y[i-1][2],y[i][2],y[i][1]-y[i-1][1]])
t=sorted(t,key=lambda x:x[2])
d=[i for i in range(n+1)]
p=[1]*(n+1)
def f(x):
    if x==d[x]:
        return x
    x=d[x]
    return f(d[x])
r=0
for a,b,c in t:
    a=f(a)
    b=f(b)
    if a!=b:
        if p[a]<p[b]:
            d[b]=a
            p[b]+=p[a]
            r+=c
        else:
            d[a]=b
            p[a]+=p[b]
            r+=c
print(r)

Submission status: Runtime Error

Solution code:
n=int(input())
s=[]
for i in range(n):
    a,b=map(int,input().split())
    s.append([a,b,i])
x=sorted(s)
y=sorted(s,key=lambda x:x[1])
print(x,y)
t=[]
for i in range(1,n):
    t.append([x[i-1][2],x[i][2],x[i][0]-x[i-1][0]])
    t.append([y[i-1][2],y[i][2],y[i][1]-y[i-1][1]])
t=sorted(t,key=lambda x:x[2])
d=[i for i in range(n+1)]
p=[1]*(n+1)
def f(x):
    if x==d[x]:
        return x
    x=d[x]
    return f(d[x])
r=0
for a,b,c in t:
    a=f(a)
    b=f(b)
    if a!=b:
        if p[a]<p[b]:
            d[b]=a
            p[b]+=p[a]
            r+=c
        else:
            d[a]=b
            p[a]+=p[b]
            r+=c
print(r)

Submission status: Runtime Error

Solution code:



class uf_tree():

    def __init__(self,n):
        self.n = n
        self.par = [i for i in range(n)]

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,child,mas):
        if self.root(child) == self.root(mas):
            return
        else:
            self.par[self.root(child)] = self.root(mas)

    def root(self,i):
        if self.par[i] == i:
            return i
        else:
            self.par[i] = self.root(self.par[i])
            return self.par[i]

    def same(self,x,y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False
def kruscal(n,edge_arr):
    edge_arr.sort(key=lambda x:x[2])
    ans = []
    tree = uf_tree(n)
    for e in edge_arr:
        s = e[0]-1
        g = e[1]-1
        if tree.same(s,g):
            continue
        else:
            ans.append(e)
            tree.unite(s,g)
    return ans

def main():
    n = int(input())
    p = []
    edge = []
    for i in range(n):
        x,y = map(int,input().split())
        p.append([x,y,i+1])

    p.sort(key = lambda x:x[0])
    for i in range(n-1):
        cost = min(abs(p[i+1][0]-p[i][0]),abs(p[i+1][1]-p[i][1]))
        edge.append([p[i][2],p[i+1][2],cost])

    p.sort(key = lambda x:x[1])
    for i in range(n-1):
        cost = min(abs(p[i+1][0]-p[i][0]),abs(p[i+1][1]-p[i][1]))
        edge.append([p[i][2],p[i+1][2],cost])

    ans = kruscal(n,edge)
    tot = 0
    for e in ans:
        tot += e[2]
    print(tot)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:



class uf_tree():

    def __init__(self,n):
        self.n = n
        self.par = [i for i in range(n)]

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,child,mas):
        if self.root(child) == self.root(mas):
            return
        else:
            self.par[self.root(child)] = self.root(mas)

    def root(self,i):
        if self.par[i] == i:
            return i
        else:
            self.par[i] = self.root(self.par[i])
            return self.par[i]

    def same(self,x,y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False
def kruscal(n,edge_arr):
    edge_arr.sort(key=lambda x:x[2])
    ans = []
    tree = uf_tree(n)
    for e in edge_arr:
        s = e[0]-1
        g = e[1]-1
        if tree.same(s,g):
            continue
        else:
            ans.append(e)
            tree.unite(s,g)
    return ans

def main():
    n = int(input())
    p = [[0,0,0] for i in range(n)]
    edge = []
    for i in range(n):
        x,y = map(int,input().split())
        p[i][0] = x
        p[i][1] = y
        p[i][2] = i+1

    p.sort(key = lambda x:x[0])
    for i in range(n-1):
        cost = min(abs(p[i+1][0]-p[i][0]),abs(p[i+1][1]-p[i][1]))
        edge.append([p[i][2],p[i+1][2],cost])

    p.sort(key = lambda x:x[1])
    for i in range(n-1):
        cost = min(abs(p[i+1][0]-p[i][0]),abs(p[i+1][1]-p[i][1]))
        edge.append([p[i][2],p[i+1][2],cost])

    ans = kruscal(n,edge)
    tot = 0
    for e in ans:
        tot += e[2]
    print(tot)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import heapq
import collections
import heapq
def input_as_int():
    return list(map(int,input().split()))


def get_comb(n):  # n C n まで

    fac = get_fact(n)
    com  = [["error" for _ in range(n+1)] for _ in range (n + 1)]
    for i in range(n + 1):
        for j in range(i + 1):
            if  i >= j:
                com[i][j] = fac[i] // (fac[i-j] * fac[j])

    return com


def get_fact(n):
    temp = 1
    fac = [1]
    for i in range(1, n + 1):
        temp *= i
        fac.append(temp)
    return fac

def prime_method(graph):
    start = graph[0]
    n = len(graph)
    went = [False] * n  # n個の点に行ったかという話
    edges = []
    for temp in start:
        heapq.heappush(edges, temp)
    went[0] = True
    cost = 0
    while len(edges) != 0:
        minedge = heapq.heappop(edges)
        if went[minedge[1]]:
            continue
        v = minedge[1]
        gv = graph[v]
        for temp in gv:
            if not went[temp[1]]:  # その頂点に行ってなければ
                heapq.heappush(edges, temp)
        went[v] = True
        cost += minedge[0]
    return cost
    # a[1] = [[2,3],[5,11]] → 点1からコスト2で頂点3に行ける辺、点1からコスト5で頂点11に行ける辺がある

def get_graph():
    n = input()
    graph = [input_as_int() for _ in range(n)]


    # a[1] = [[2,3],[5,11]] → 点1からコスト2で頂点3に行ける辺、点1からコスト5で頂点11に行ける辺がある


n = int(input())
cities  = [list(map(int,input().split(" "))) for i in range(n)]
for i in range(n):
    cities[i].append(i)
graph = [[] for _ in  range(n)]

cities.sort(key = lambda x:x[0][0])
citiesX = cities
s1,s2 = citiesX[0:-1],citiesX[1:]
for city1,city2 in zip(s1,s2):
    no1 = city1[2]
    no2 = city2[2]
    graph[no1].append([abs(city1[0] - city2[0]),no2])
    graph[no2].append([abs(city1[0] - city2[0]),no1])
cities.sort(key =lambda x:x[0][1])
s1 = cities[0:-1]
s2 = cities[1:]
for city1,city2 in zip(s1,s2):
    no1 = city1[2]
    no2 = city2[2]
    graph[no1].append([abs(city1[1] - city2[1]),no2])
    graph[no2].append([abs(city1[1] - city2[1]),no1])




print(prime_method(graph))

Submission status: Runtime Error

Solution code:
N=int(input())
city=[0]*N
for i in range(N):
    x,y=map(int,input().split())
    city[i]=(i,x,y)
city.sort(key=lambda x:x[1])
data=[(city[i][0],city[i+1][0],city[i+1][1]-city[i][1]) for i in range(N-1)]
city.sort(key=lambda x:x[2])
data+=[(city[i][0],city[i+1][0],city[i+1][2]-city[i][2]) for i in range(N-1)]
data.sort(key=lambda x:x[2])
root=[-1]*N
def search(i):
    global root
    if root[i]>=0:
        root[i]=search(root[i])
        return root[i]
    return i
cost=0
for i,j,k in data:
    ri=search(i)
    rj=search(j)
    if ri==rj:
        continue
    elif root[ri]>=root[rj]:
        cost+=k
        root[ri]+=root[rj]
        root[rj]=ri
    elif root[ri]<root[rj]:
        cost+=k
        root[rj]+=root[ri]
        root[ri]=rj
print(cost)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from typing import List, Tuple, Dict
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


class UnionFind:
    def __init__(self, N):
        # type: (int) -> None
        self.N = N
        self.parent = list(range(N))  # type: List[int]

    def root(self, x):
        # type: (int) -> int
        path_to_root = []
        while self.parent[x] != x:
            path_to_root.append(x)
            x = self.parent[x]
        for node in path_to_root:
            self.parent[node] = x  # パス圧縮
        return x

    def same(self, x, y):
        # type: (int, int) -> bool
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        # type: (int, int) -> None
        self.parent[self.root(x)] = self.root(y)

    def __str__(self):
        # type: () -> str
        groups = {}  # type: Dict[int, List[int]]
        for x in range(self.N):
            root = self.root(x)
            if root in groups.keys():
                groups[root].append(x)
            else:
                groups[root] = [x]
        result = ""
        for root in groups.keys():
            result += str(groups[root]) + "\n"
        return result


def kruskal(num_vertices, edges):
    # type: (int, List[Tuple[int, int, int]]) -> int
    """Kruscal法: 最小全域木を求める
    edgesについて破壊的なことに注意
    """
    total_weight = 0
    edges.sort(key=lambda e: e[2])
    u = UnionFind(num_vertices)
    for e in edges:
        x = e[0]
        y = e[1]
        weight = e[2]
        if u.same(x, y):
            continue
        u.unite(x, y)
        total_weight += weight
    return total_weight


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

edges = []
sorted_x = sorted(l, key=lambda c: c[1])
sorted_y = sorted(l, key=lambda c: c[2])

for e in range(N-1):
    i0, x0, y0 = sorted_x[e]
    i1, x1, y1 = sorted_x[e+1]
    edges.append((i0, i1, x1-x0))

    i0, x0, y0 = sorted_y[e]
    i1, x1, y1 = sorted_y[e+1]
    edges.append((i0, i1, y1-y0))

print(kruskal(N, edges))

Submission status: Runtime Error

Solution code:
n = int(input())
xs = []
ys = []

for i in range(n):
    x, y = map(int, input().split())
    xs.append((x, i))
    ys.append((y, i))


xs.sort()
ys.sort()

es = []

for i in range(n-1):
    es.append((xs[i+1][0] - xs[i][0], xs[i][1], xs[i+1][1]))
    es.append((ys[i+1][0] - ys[i][0], ys[i][1], ys[i+1][1]))

es.sort()


class UF:
    def __init__(self):
        self.p = {}
    def find(self, x):
        if x not in self.p:
            self.p[x] = x
        if x == self.p[x]:
            return x
        self.p[x] = self.find(self.p[x])
        return self.p[x]
    def merge(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.p[x] = y


uf= UF()
ans = 0
for d, i0, i1 in es:
    c0 = uf.find(i0)
    c1 = uf.find(i1)
    if c0 == c1:
        continue
    ans += d
    uf.merge(i0, i1)
print(ans)