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:
from operator import itemgetter

class UnionFind:  # 0-index
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n  # 親の番号 要素が根の場合は-(そのグループの要素数)を格納

    def find(self, x):  # 要素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が属するグループと要素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):  # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):  # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):  # 要素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 {root: self.members(root) for root in self.roots()}

# ---------------------- #

def kruskal(n, edges):  # edges := [(u, v, weight), ...] weightでソート済み O(E)
    uf = UnionFind(n)
    ret = 0
    for u, v, w in edges:
        if not uf.same(u, v):
            ret += w
            uf.union(u, v)
    return ret

# ---------------------- #

n = int(input())
XY = [tuple(int(x) for x in input().split()) for _ in range(n)]
edges = []
XY.sort()
for (x1, _), (x2, _) in zip(XY, XY[1:]):
    edges.append((x1, x2, abs(x2 - x1)))
XY.sort(key=itemgetter(1))
for (_, y1), (_, y2) in zip(XY, XY[1:]):
    edges.append((y1, y2, abs(y2 - y1)))

ans = kruskal(n, edges)
print(ans)

Submission status: Runtime Error

Solution code:
from copy import deepcopy as copy
from operator import itemgetter

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1]*(n+1)#それぞれの要素がどの要素の子であるか

    def find(self, x):
        if self.par[x] < 0:
            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:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        
        self.par[x] += self.par[y]
        self.par[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)#x,yが同じ集合に属するかどうか
    
    def size(self, x):
        return -self.par[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if root == self.find(i)]        

def main():
    n = int(input())
    bridge = [None]*n
    for i in range(n):
        bridge[i] = [int(x) for x in input().split()]+[i]

    judge = []

    bridge.sort()
    heapq.heapify(judge)
    for i in range(n-1):
        judge.append((bridge[i+1][0]-bridge[i][0], bridge[i][2], bridge[i+1][2]))

    bridge.sort(key=itemgetter(1))
    for i in range(n-1):
        judge.append((bridge[i+1][1]-bridge[i][1], bridge[i][2], bridge[i+1][2]))
    
    judge.sort()
    union = UnionFind(n)
    count = 0
    cost = 0
    while True:
        c, i, j = heapq.heappop(judge)
        if union.same(i, j):
            continue
        union.union(i, j)
        cost += c
        count += 1
        if count == n-1:
            break
    
    print(cost)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
from heapq import heappop, heappush,heapify

icase=0
if icase==0:
    n=int(input())
    xy=[[0]*2 for i in range(n)]
    for i in range(n):
        xy[i]=list(map(int,input().split()))
elif icase==1:    
    n=3
    xy=[[1, 5], [3, 9], [7, 8]]
elif icase==2:    
    n=6
    xy=[[8, 3], [4, 9], [12, 19], [18, 1], [13, 5], [7, 6]]

xy = list(map(list, set(map(tuple, xy))))
#xy.sort()

pair_lst = [i for i in range(n)]
que=[]
for i in range(n-1):
    for j in range(i+1,n):
        wi=min(abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1]))
#        que.append((wi,i,j))
        heappush(que,(wi,i,j))

def find(x):
    if x == pair_lst[x]:
        return x
    else:
        tmp = find(pair_lst[x])
        pair_lst[x] = tmp
        return tmp

icnt=0
length_sum = 0
while que:
    w, s, t = heappop(que)
    root_s = find(s)
    root_t = find(t)
    if root_s != root_t:
        pair_lst[root_s] = root_t
        length_sum += w
        icnt+=1
#        print(icnt)
        if icnt==n-1:
            break

print(length_sum)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
from heapq import heappop, heappush

icase=0
if icase==0:
    n=int(input())
    xy=[[0]*2 for i in range(n)]
    for i in range(n):
        xy[i]=list(map(int,input().split()))
elif icase==1:    
    n=3
    xy=[[1, 5], [3, 9], [7, 8]]
elif icase==2:    
    n=6
    xy=[[8, 3], [4, 9], [12, 19], [18, 1], [13, 5], [7, 6]]

xy = list(map(list, set(map(tuple, xy))))
xy.sort()
xy=xy[:n]

pair_lst = [i for i in range(n)]
que=[]
for i in range(n-1):
    for j in range(i+1,n):
        wi=min(abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1]))
        heappush(que,(wi,i,j))

def find(x):
    if x == pair_lst[x]:
        return x
    else:
        tmp = find(pair_lst[x])
        pair_lst[x] = tmp
        return tmp

length_sum = 0
while que:
    w, s, t = heappop(que)
    root_s = find(s)
    root_t = find(t)
    if root_s != root_t:
        pair_lst[root_s] = root_t
        length_sum += w

print(length_sum)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
from heapq import heappop, heappush

icase=0
if icase==0:
    n=int(input())
    xy=[[0]*2 for i in range(n)]
    for i in range(n):
        xy[i]=list(map(int,input().split()))
elif icase==1:    
    n=3
    xy=[[1, 5], [3, 9], [7, 8]]
elif icase==2:    
    n=6
    xy=[[8, 3], [4, 9], [12, 19], [18, 1], [13, 5], [7, 6]]

xy = list(map(list, set(map(tuple, xy))))
xy.sort()
xy=xy[:n*2]

pair_lst = [i for i in range(n)]
que=[]
for i in range(n-1):
    for j in range(i+1,n):
        wi=min(abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1]))
        heappush(que,(wi,i,j))

def find(x):
    if x == pair_lst[x]:
        return x
    else:
        tmp = find(pair_lst[x])
        pair_lst[x] = tmp
        return tmp

length_sum = 0
while que:
    w, s, t = heappop(que)
    root_s = find(s)
    root_t = find(t)
    if root_s != root_t:
        pair_lst[root_s] = root_t
        length_sum += w

print(length_sum)

Submission status: Runtime Error

Solution code:
import sys
import pprint
sys.path.append('C:\\ARIHON')

from Kraskal import compute_mst_kruskal
import UnionFind
import array
import collections
from operator import itemgetter
 
Edge = collections.namedtuple("Edge", "start end weight")

def main():
    n = int(input())
    l = []
    for i in range(n):
        x,y = map(int,input().split())
        l.append((x,y,i))
    
    edges = []

    lxsort = sorted(l,key=itemgetter(0))
    for i in range(n-1):
        edges.append(Edge(lxsort[i][2],lxsort[i+1][2],lxsort[i+1][0]-lxsort[i][0]))
    
    lysort = sorted(l,key=itemgetter(1))
    for i in range(n-1):
        edges.append(Edge(lysort[i][2],lysort[i+1][2],lysort[i+1][1]-lysort[i][1]))
    
    mst = compute_mst_kruskal(n,edges)

    print(sum(edge.weight for edge in mst))
 
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
finput=lambda:sys.stdin.readline().strip()


class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.ranks=[0]*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.ranks[x]<self.ranks[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
        if self.ranks[x]==self.ranks[y]:
            self.ranks[x]+=1
    
    def size(self,x):
        return -self.parents[self.find(x)]
    
    def issametree(self,x,y):
        return self.find(x)==self.find(y)

def main():
    n=int(finput())
    xy=dict((tuple(map(int,finput().split())),i) for i in range(n))
    coor=list(iter(xy))
    coor.sort(key=lambda e:e[0])
    cost = lambda e,f:min(abs(e[0]-f[0]),abs(e[1]-f[1]))
    ew={(0,0):0}
    if n>0:
        ew.update(dict(((xy[coor[i]],xy[coor[i+1]]),cost(coor[i],coor[i+1]))for i in range(n-1)))
        coor.sort(key=lambda e:e[1])
        ew.update(dict(((xy[coor[i]],xy[coor[i+1]]),cost(coor[i],coor[i+1]))for i in range(n-1)))
    edges=sorted(list(iter(ew)),key=lambda e:ew[e])
    v=Unionfind(n)
    totcost=0
    # print(ew)
    # print(edges)
    for edge in edges:
        if not v.issametree(edge[0],edge[1]):
            v.union(edge[0],edge[1])
            totcost+=ew[edge]
    print(totcost)
    
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
finput=lambda:sys.stdin.readline().strip()


class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.ranks=[0]*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.ranks[x]<self.ranks[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
        if self.ranks[x]==self.ranks[y]:
            self.ranks[x]+=1
    
    def size(self,x):
        return -self.parents[self.find(x)]
    
    def issametree(self,x,y):
        return self.find(x)==self.find(y)

def main():
    n=int(finput())
    xy=dict((tuple(map(int,finput().split())),i) for i in range(n))
    coor=sorted(list(iter(xy)),key=lambda e:e[0])
    cost = lambda e,f:min(abs(e[0]-f[0]),abs(e[1]-f[1]))
    ew={(0,0):0}
    ew.update(dict(((xy[coor[i]],xy[coor[i+1]]),cost(coor[i],coor[i+1]))for i in range(n-1)))
    coor.sort(key=lambda e:e[1])
    ew.update(dict(((xy[coor[i]],xy[coor[i+1]]),cost(coor[i],coor[i+1]))for i in range(n-1)))
    edges=sorted(list(iter(ew)),key=lambda e:ew[e])
    v=Unionfind(n)
    totcost=0
    # print(ew)
    # print(edges)
    for edge in edges:
        if not v.issametree(edge[0],edge[1]):
            v.union(edge[0],edge[1])
            totcost+=ew[edge]
    print(totcost)
    
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10**18)
finput=lambda:sys.stdin.readline().strip()

class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.ranks=[0]*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.ranks[x]<self.ranks[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
        if self.ranks[x]==self.ranks[y]:
            self.ranks[x]+=1
    
    def size(self,x):
        return -self.parents[self.find(x)]
    
    def issametree(self,x,y):
        return self.find(x)==self.find(y)

def main():
    n=int(finput())
    xy=dict((tuple(map(int,finput().split())),i) for i in range(n))
    coor=sorted(list(iter(xy)),key=lambda e:e[0])
    cost = lambda e,f:min(abs(e[0]-f[0]),abs(e[1]-f[1]))
    ew=dict(((xy[coor[i]],xy[coor[i+1]]),cost(coor[i],coor[i+1]))for i in range(n-1))
    coor.sort(key=lambda e:e[1])
    ew.update(dict(((xy[coor[i]],xy[coor[i+1]]),cost(coor[i],coor[i+1]))for i in range(n-1)))
    edges=sorted(list(iter(ew)),key=lambda e:ew[e])
    v=Unionfind(n)
    totcost=0
    # print(ew)
    # print(edges)
    for edge in edges:
        if not v.issametree(edge[0],edge[1]):
            v.union(edge[0],edge[1])
            totcost+=ew[edge]
    print(totcost)
    
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
sys.sys.setrecursionlimit(10**18)
finput=lambda:sys.stdin.readline().strip()

class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.ranks=[0]*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.ranks[x]<self.ranks[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
        if self.ranks[x]==self.ranks[y]:
            self.ranks[x]+=1
    
    def size(self,x):
        return -self.parents[self.find(x)]
    
    def issametree(self,x,y):
        return self.find(x)==self.find(y)

def main():
    n=int(finput())
    xy=dict((tuple(map(int,finput().split())),i) for i in range(n))
    coor=sorted(list(iter(xy)),key=lambda e:e[0])
    cost = lambda e,f:min(abs(e[0]-f[0]),abs(e[1]-f[1]))
    ew=dict(((xy[coor[i]],xy[coor[i+1]]),cost(coor[i],coor[i+1]))for i in range(n-1))
    coor.sort(key=lambda e:e[1])
    ew.update(dict(((xy[coor[i]],xy[coor[i+1]]),cost(coor[i],coor[i+1]))for i in range(n-1)))
    edges=sorted(list(iter(ew)),key=lambda e:ew[e])
    v=Unionfind(n)
    totcost=0
    # print(ew)
    # print(edges)
    for edge in edges:
        if not v.issametree(edge[0],edge[1]):
            v.union(edge[0],edge[1])
            totcost+=ew[edge]
    print(totcost)
    
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
finput=lambda:sys.stdin.readline().strip()
sys.setrecursionlimit(10*9)

class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.ranks=[0]*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.ranks[x]<self.ranks[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
        if self.ranks[x]==self.ranks[y]:
            self.ranks[x]+=1
    
    def size(self,x):
        return -self.parents[self.find(x)]
    
    def issametree(self,x,y):
        return self.find(x)==self.find(y)

def main():
    n=int(finput())
    xy=dict((tuple(map(int,finput().split())),i) for i in range(n))
    coor=sorted(list(iter(xy)),key=lambda e:e[0])
    cost = lambda e,f:min(abs(e[0]-f[0]),abs(e[1]-f[1]))
    ew=dict(((xy[coor[i]],xy[coor[i+1]]),cost(coor[i],coor[i+1]))for i in range(n-1))
    coor.sort(key=lambda e:e[1])
    ew.update(dict(((xy[coor[i]],xy[coor[i+1]]),cost(coor[i],coor[i+1]))for i in range(n-1)))
    edges=sorted(list(iter(ew)),key=lambda e:ew[e])
    v=Unionfind(n)
    totcost=0
    # print(ew)
    # print(edges)
    for edge in edges:
        if not v.issametree(edge[0],edge[1]):
            v.union(edge[0],edge[1])
            totcost+=ew[edge]
    print(totcost)
    
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
finput=lambda:sys.stdin.readline().strip()

class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.ranks=[0]*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.ranks[x]<self.ranks[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
        if self.ranks[x]==self.ranks[y]:
            self.ranks[x]+=1
    
    def size(self,x):
        return -self.parents[self.find(x)]
    
    def issametree(self,x,y):
        return self.find(x)==self.find(y)

def main():
    n=int(finput())
    xy=dict((tuple(map(int,finput().split())),i) for i in range(n))
    coor=sorted(list(iter(xy)),key=lambda e:e[0])
    cost = lambda e,f:min(abs(e[0]-f[0]),abs(e[1]-f[1]))
    ew=dict(((xy[coor[i]],xy[coor[i+1]]),cost(coor[i],coor[i+1]))for i in range(n-1))
    coor.sort(key=lambda e:e[1])
    ew.update(dict(((xy[coor[i]],xy[coor[i+1]]),cost(coor[i],coor[i+1]))for i in range(n-1)))
    edges=sorted(list(iter(ew)),key=lambda e:ew[e])
    v=Unionfind(n)
    totcost=0
    # print(ew)
    # print(edges)
    for edge in edges:
        if not v.issametree(edge[0],edge[1]):
            v.union(edge[0],edge[1])
            totcost+=ew[edge]
    print(totcost)
    
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc065/tasks/arc076_b
import copy


class UnionFind():
    def __init__(self, n):
        super().__init__()
        self.n = n
        self.parents = [i for i in range(n)]

    def root(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        self.parents[y] = x
        return True


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

# (start, end, cost)
edges = []

# x座標でソートしてx座標が隣り合う点にをedge候補に
rows_x = copy.deepcopy(rows)
rows_x.sort(key=lambda x: x[1])
for i in range(len(rows)-1):
    left = rows_x[i]
    right = rows_x[i+1]
    edges.append((left[0], right[0], right[1] - left[1]))

rows_y = copy.deepcopy(rows)
rows_y.sort(key=lambda x: x[2])
for i in range(len(rows)-1):
    down = rows_y[i]
    up = rows_y[i+1]
    edges.append((down[0], up[0], up[2] - down[2]))

# print(edges)

uf = UnionFind(n)

edges.sort(key=lambda edge: edge[2])

result = 0
for edge in edges:
    s, t, c = edge
    unioned = uf.union(s, t)
    if unioned:
        result += c

print(result)

Submission status: Runtime Error

Solution code:
from heapq import heappop,heappush
n=int(input())
pair=[i for i in range(n)]
e=[]
que=[]
que1=[]
for i in range(n):
  s,t=map(int,input().split())
  heappush(e,(s,t))
s,t=heappop(e)
heappush(que1,(t,s,0))
for i in range(n-1):
  s1,t1=heappop(e)
  heappush(que,(s1-s,i,i+1))
  s,t=s1,t1
  heappush(que1,(t,s,i+1))
t,s,i=heappop(que1)
for _ in range(n-1):
  t1,s1,j=heappop(que1)
  heappush(que,(t1-t,i,j))
  s,t,i=s1,t1,j
def find(x):
  if x==pair[x]:return x
  else:
    tmp=find(pair[x])
    pair[x]=tmp
    return tmp
ans=0
while que:
  w,s,t=heappop(que)
  root_s=find(s)
  root_t=find(t)
  if root_s!=root_t:
    pair[root_s]=root_t
    ans+=w
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
xy = []
for i in range(n):
    x, y = map(int, input().split())
    xy.append((i, x, y))
xx = sorted(xy, key=lambda x:x[1])
yy = sorted(xy, key=lambda x:x[2])
li = []
for i in range(n-1):
    li.append((xx[i][0], xx[i+1][0], xx[i+1][1]-xx[i][1]))
    li.append((yy[i][0], yy[i+1][0], yy[i+1][2]-yy[i][2]))
li.sort(key=lambda x:x[2])
class UnionFind():
    def __init__(self, li):
        self.li = li
    def root(self, x):
        if self.li[x]==x:
            return x
        self.li[x] = self.root(self.li[x])
        return self.li[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx==ry:
            return
        self.li[ry] = rx
    def same(self, x, y):
        return self.root(x)==self.root(y)
uf = UnionFind(list(range(n)))
ans = 0
for x, y, cost in li:
    if uf.same(x, y):
        continue
    uf.unite(x, y)
    ans += cost
print(ans)

Submission status: Runtime Error

Solution code:
#import sys
#input = sys.stdin.readline
N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]
x,y = zip(*xy)

#import random
#N = 20000
#x = [random.randint(0,0) for i in range(N)]
#y = [random.randint(0,0) for i in range(N)]

class UnionFind:
    def __init__(self,nodes):
        self.parents = {node : node for node in nodes}
    def root(self,x):
        if x == self.parents[x]:
            return x
        else:
            rt = self.root(self.parents[x])
            self.parents[x] = rt
            return rt
    def find(self,x,y):
        return self.root(x) == self.root(y)
    def union(self,x,y):
        self.parents[self.root(x)] = self.root(y)

xi = [(x,i+1) for i,x in enumerate(x)]
yi = [(y,i+1) for i,y in enumerate(y)]

xi.sort()
yi.sort()

diffx = [(x1-x0,i0,i1) for (x0,i0),(x1,i1) in zip(xi,xi[1:])]
diffy = [(y1-y0,i0,i1) for (y0,i0),(y1,i1) in zip(yi,yi[1:])]

diffx.extend(diffy)
diffx.sort()

uf = UnionFind(list(range(1,N+1)))
ans = 0
for d,i0,i1 in diffx:
    if not uf.find(i0,i1):
        ans += d
        uf.union(i0,i1)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]

class UnionFind:
    def __init__(self,nodes):
        self.parents = {node : node for node in nodes}
    def root(self,x):
        if x == self.parents[x]:
            return x
        else:
            rt = self.root(self.parents[x])
            self.parents[x] = rt
            return rt
    def find(self,x,y):
        return self.root(x) == self.root(y)
    def union(self,x,y):
        self.parents[self.root(x)] = self.root(y)
    def get(self):
        res = defaultdict(list)
        for node, parent in self.parents.items():
            res[self.root(node)].append(node)
        # return [*res.values()]
        return list(res.values())

x,y = zip(*xy)

xi = [(x,i+1) for i,x in enumerate(x)]
yi = [(y,i+1) for i,y in enumerate(y)]

xi.sort()
yi.sort()

diffx = [(x1-x0,i0,i1) for (x0,i0),(x1,i1) in zip(xi,xi[1:])]
diffx.sort()
diffy = [(y1-y0,i0,i1) for (y0,i0),(y1,i1) in zip(yi,yi[1:])]
diffy.sort()

diffx.extend(diffy)
diffx.sort()

uf = UnionFind(list(range(1,N+1)))
ans = 0
for d,i0,i1 in diffx:
    if not uf.find(i0,i1):
        ans += d
        uf.union(i0,i1)
print(ans)

Submission status: Runtime Error

Solution code:
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 same_check(self, x, y):
        return self.find(x) == self.find(y)

import copy
N = int(input())
A = [0] * N
for i in range(N):
  a, b = map(int, input().split())
  A[i] = [i, a, b]

B = copy.deepcopy(A)  
A = sorted(A, key = lambda x:x[1])
B = sorted(B, key = lambda x:x[2])
#print(A, B)

data = UnionFind(N + 1)
a, b = 1, 1
cost = 0
for i in range(N):
  #print(a, b, cost)
  one = abs(A[a][1] - A[a - 1][1])
  two = abs(B[b][2] - B[b - 1][2])
  if one > two:
    if not data.same_check(B[b][0], B[b - 1][0]):
      data.union(B[b][0], B[b - 1][0])
      cost += two
    b += 1
    
  else:
    if not data.same_check(A[a][0], A[a - 1][0]):
      data.union(A[a][0], A[a - 1][0])
      cost += one     
    a += 1
  
print(cost)

Submission status: Runtime Error

Solution code:
n = int(int, input().split())
machi = []
li_x = []
li_y = []
for i in range(n):
    x, y = map(int, input().split())
    li_x.append((x, i))
    li_y.append((y, i))
    machi.append((x, y, i))
li_x.sort()
li_y.sort()
edge = [[] for _ in range(n)]
for i in range(n-1):
    edge[li_x[i][1]].append((li_x[i+1][0]-li_x[i][0], li_x[i+1][1]))
    edge[li_x[i+1][1]].append((li_x[i+1][0]-li_x[i][0], li_x[i][1]))
    edge[li_y[i][1]].append((li_y[i+1][0]-li_y[i][0], li_y[i+1][1]))
    edge[li_y[i+1][1]].append((li_y[i+1][0]-li_y[i][0], li_y[i][1]))

import heapq
def prim_heap(edge, n):
    used = [True] * n # True ：　不使用husiyou
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist, e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist, e)
        res += minedge[0]
    return res
print(prim_heap(edge, n))

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] + [int(x) for x in input().split()] for i in range(n)]
f = []
t = []
d = []

ixy = sorted(ixy, key=lambda x:(x[1], x[2]))
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d.append(ixy[i+1][1] - ixy[i][1])
    f.append(j)
    f.append(k)

ixy = sorted(ixy, key=lambda x:(x[2], x[1]))
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d.append(ixy[i+1][2] - ixy[i][2])
    t.append(k)
    f.append(j)

csr_ = csr_matrix((d, (f, t)), shape=(n, n))
mst = minimum_spanning_tree(csr_).astype(int)
print(mst.sum())

Submission status: Runtime Error

Solution code:
n=int(input())
points=[list(map(int,input().split()))+[i] for i in range(n)]
points.sort(key = lambda x:x[1])
edge=[]
for i in range(n-1):
    edge.append((points[i][2],points[i+1][2],points[i+1][1]-points[i][1]))
points.sort()
for i in range(n-1):
    edge.append((points[i][2],points[i+1][2],points[i+1][0]-points[i][0]))
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for i in range(N)]
    
    def merge(self, a, b):
        if self.issame(a,b):
            return
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
        self.size[pb] += self.size[pa]
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
    
    def issame(self, x, y):
        return self.root(x) == self.root(y)
    
    def getsize(self, x):
        return self.size[self.root(x)]
edge.sort(key=lambda x:x[2])
uf=UnionFind(n)
ans=0
for ed in edge:
    if uf.issame(ed[0],ed[1]):continue
    ans+=ed[2]
    uf.merge(ed[0],ed[1])
print(ans)

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop
import networkx as nx
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N = INT()
xy = [LIST() for _ in range(N)]
ixy = list(enumerate(xy))
ixy.sort(key=lambda x:x[1][0])

g = nx.Graph()

for (i, (x, y)), (j, (x1, y1)) in zip(ixy, ixy[1:]):
	g.add_edge(i, j, weight=min(abs(x-x1), abs(y-y1)))

ixy.sort(key=lambda x:x[1][1])
for (i, (x, y)), (j, (x1, y1)) in zip(ixy, ixy[1:]):
	g.add_edge(i, j, weight=min(abs(x-x1), abs(y-y1)))

tree = nx.minimum_spanning_tree(g)
print(int(tree.size(weight='weight')))

Submission status: Runtime Error

Solution code:
n=int(input())
l=sorted([list(map(int,input().split()))+[i] for i in range(n)])
xs=[(x,i)for x,y,i in l]
ys=sorted([(x,i)for y,x,i in l])
edges={}
for i in range(1,n):
    a,s,d,f=*xs[i-1],*xs[i]
    if (s,f)in edges:
        edges[(s,f)]=min(edges[(s,f)],abs(a-d))
    else:edges[(s,f)]=abs(a-d)
    a,s,d,f=*ys[i-1],*ys[i]
    if (s,f)in edges:
        edges[(s,f)]=min(edges[(s,f)],abs(a-d))
    else:edges[(s,f)]=abs(a-d)
edges=sorted(edges.items(),key=lambda x:x[1])
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
uf=UnionFind(n)
ans=edges[0][1]
uf.unite(*edges[0][0])
for f,c in edges:
    if uf.same(*f):continue
    uf.unite(*f)
    ans+=c
print(ans)