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:
def want_p(n):
 
    Q = []
 
    while n != p[n]:
        Q.append(n)
        n = p[n]
 
    for i in Q:
        p[i] = n
 
    return n
 
 
N = int(input())
 
xyi = []
yxi = []
 
for i in range(N):
 
    x,y = map(int,input().split())
    xyi.append([x,y,i])
    yxi.append([y,x,i])
 
xyi.sort()
yxi.sort()
 
line = []
 
 
for i in range(N-1):
 
    line.append([ xyi[i+1][0]-xyi[i][0] , xyi[i][2] , xyi[i+1][2] ])
    line.append([ yxi[i+1][0]-yxi[i][0] , yxi[i][2] , yxi[i+1][2] ])
 
line.sort()
 
p = [i for i in range(N)]
rank = [1] * N
num = [1] * N
ans = 0
 
for j in range(len(line)):
 
    e = line[j]
    cost = e[0]
    a = e[1]
    b = e[2]
 
    ap = want_p(a)
    bp = want_p(b)
 
    if ap != bp:
        ans += cost

        k = num[ap]
        num[ap] += num[bp]
        num[bp] += k

        if num[ap] == N or num[bp] == N:
            break
 
        if rank[ap] > rank[bp]:
            p[bp] = ap
 
        elif rank[ap] == rank[bp]:
            p[bp] = ap
            rank[ap] += 1
 
        else:
            p[ap] = bp
 
print (ans)

Submission status: Accepted

Solution code:
n=int(input())
a=sorted([[i]+list(map(int,input().split()))for i in range(n)],key=lambda x:x[1])
s=[]
for i in range(n-1):
    s.append((a[i+1][1]-a[i][1],a[i][0],a[i+1][0]))
a=sorted(a,key=lambda x:x[2])
for i in range(n-1):
    s.append((a[i+1][2]-a[i][2],a[i][0],a[i+1][0]))
s.sort()
t=[i for i in range(n)]
def f(x):
    if x==t[x]:
        return x
    t[x]=f(t[x])
    return f(t[x])
c=0
for i,j,h in s:
    j,h=f(j),f(h)
    if h!=j:
        t[j]=h
        c+=i
print(c)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc065/submissions/5881131
import sys
input = sys.stdin.readline
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)

def MST(n, E):
    E = sorted(E, key=lambda x: x[2])
    uf = UnionFind(n)
    ct = 0
    for i,j,cost in E:
      if uf.same_check(i,j):
        continue
      else:
        uf.union(i,j)
        ct += cost
    return ct
  
def solve():
  N = int(input())
  X = []
  append=X.append
  for i in range(N):
    x, y = map(int, input().split())
    append((i, x, y))
 
  F = []
  append = F.append
  Y = sorted(X, key = lambda x: x[1])
  for i in range(len(Y)-1):
    append((Y[i][0], Y[i+1][0], abs(Y[i+1][1]-Y[i][1])))
 
  Y = sorted(X, key = lambda x: x[2])
  for i in range(len(Y)-1):
    append((Y[i][0], Y[i+1][0], abs(Y[i+1][2]-Y[i][2])))
 
  print(MST(N, F))

solve()

Submission status: Accepted

Solution code:
import heapq
import sys
input = sys.stdin.readline
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)

def solve():
  n = int(input())
  query = []
  xquery = []
  yquery = []
  for i in range(n):
    x,y = (int(i) for i in input().split())
    xquery.append((x,y,i))
    yquery.append((y,x,i))
  xquery.sort()
  yquery.sort()
  for i in range(n-1):
    tx,ty,place = xquery[i]
    tx2,ty2,place2 = xquery[i+1]
    cost = min(abs(tx2-tx),abs(ty2-ty))
    if place > place2:
      place,place2 = place2,place
    heapq.heappush(query,(cost,place,place2))
    
    ty,tx,place = yquery[i]
    ty2,tx2,place2 = yquery[i+1]
    cost = min(abs(tx2-tx),abs(ty2-ty))
    if place > place2:
      place,place2 = place2,place
    heapq.heappush(query,(cost,place,place2))
  ct = 0
  uf = UnionFind(n)

  while len(query) > 0:
    cost,place1,place2 = heapq.heappop(query)
    if uf.same_check(place1,place2):
      continue
    else:
      uf.union(int(place1),int(place2))
      ct += cost
  print(ct)
      

solve()

Submission status: Accepted

Solution code:
n=int(input())
lx=[]
ly=[]
for i in range(n):
    x,y=[int(j) for j in input().split()]
    lx.append((i,x,y))
    ly.append((i,x,y))
from operator import itemgetter
lx.sort(key=itemgetter(1))
ly.sort(key=itemgetter(2))
# 最小全域木
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
edge=set()
for i in range(n-1):
    i1,x1,y1=lx[i]
    i2,x2,y2=lx[i+1]
    d=min(abs(x1-x2),abs(y1-y2))
    edge.add((i1,i2,d))
for i in range(n-1):
    i1,x1,y1=ly[i]
    i2,x2,y2=ly[i+1]
    d=min(abs(x1-x2),abs(y1-y2))
    edge.add((i1,i2,d))
row,col,value = zip(*edge)
value = np.array(value,dtype=int)
graph = csr_matrix((value,(row,col)),shape=(n,n))

tree = minimum_spanning_tree(graph,overwrite = True).astype(int)
print(tree.sum())

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
from operator import itemgetter
import sys
input = sys.stdin.readline
n=int(input())
lx=[]
ly=[]
XY = [[i] + [int(x) for x in input().split()] for i in range(n)]
edge = set()
for key in [itemgetter(1),itemgetter(2)]:
    XY.sort(key = key)
    for i in range(n-1):
        i1,x1,y1 = XY[i]
        i2,x2,y2 = XY[i+1]
        d = min(abs(x1-x2),abs(y1-y2))
        edge.add((i1,i2,d))

row,col,value = zip(*edge)
value = np.array(value,dtype=int)
graph = csr_matrix((value,(row,col)),shape=(n,n))

tree = minimum_spanning_tree(graph,overwrite = True).astype(int)
print(tree.sum())

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
from operator import itemgetter
n=int(input())
lx=[]
ly=[]
XY = [[i] + [int(x) for x in input().split()] for i in range(n)]
edge = set()
for key in [itemgetter(1),itemgetter(2)]:
    XY.sort(key = key)
    for i in range(n-1):
        i1,x1,y1 = XY[i]
        i2,x2,y2 = XY[i+1]
        d = min(abs(x1-x2),abs(y1-y2))
        edge.add((i1,i2,d))

row,col,value = zip(*edge)
value = np.array(value,dtype=int)
graph = csr_matrix((value,(row,col)),shape=(n,n))

tree = minimum_spanning_tree(graph,overwrite = True).astype(int)
print(tree.sum())

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()


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

edge_list = [[] for _ in range(N)]

for i in range(N - 1):
	edge_list[xy1[i][1]].append((xy1[i + 1][0] - xy1[i][0], xy1[i + 1][1]))
	edge_list[xy1[i + 1][1]].append((xy1[i + 1][0] - xy1[i][0], xy1[i][1]))
	edge_list[xy2[i][1]].append((xy2[i + 1][0] - xy2[i][0], xy2[i + 1][1]))
	edge_list[xy2[i + 1][1]].append((xy2[i + 1][0] - xy2[i][0], xy2[i][1]))

judge = [0]*N
G = []
heapq.heapify(G)
for edge in edge_list[0]:
	heapq.heappush(G, edge)

judge[0] = 1
total = 0
num = 0
while num < N - 1:
	edge = heapq.heappop(G)
	if judge[edge[1]] == 0:
		judge[edge[1]] = 1
		total += edge[0]
		num += 1
		for add in edge_list[edge[1]]:
			if judge[add[1]] == 0:
				heapq.heappush(G, add)

print(total)

Submission status: Accepted

Solution code:

import collections
def main():

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

    edges = []
    city.sort(key = lambda x: x[0])
    for i in range(N-1):
        edges.append([city[i][2], city[i+1][2], abs(city[i][0]-city[i+1][0])])
    city.sort(key = lambda x: x[1])
    for i in range(N-1):
        edges.append([city[i][2], city[i+1][2], abs(city[i][1]-city[i+1][1])])
    edges.sort(key = lambda x: x[2])

    parent = [a for a in range(N)]
    def find(a):
        if parent[a] != a:
            parent[a] = find(parent[a])
        return parent[a]
    def union(a, b, c):
        pa, pb = find(a), find(b)
        if pa != pb:
            parent[pb] = pa
            return c, 1
        else:
            return 0, 0

    cost = 0
    connected = N
    for a, b, c in edges:
        cst, cmp = union(a, b, c)
        cost += cst
        connected -= cmp
        if connected == 1:
            return cost



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

Submission status: Accepted

Solution code:
from operator import itemgetter
from bisect import bisect_left, bisect_right
import heapq as hp
import sys
input = sys.stdin.readline

#import numpy as np
#import matplotlib.pyplot as plt

'''
def graph_ABC065D(N, max_xy):
    print(N)
    XY = []
    for _ in range(N):
        xi = np.random.randint(0, max_xy)
        yi = np.random.randint(0, max_xy)
        XY.append([xi, yi])
        print(xi, yi)
    return N, XY


def plot(N, XY, max_xy):
    X, Y = zip(*XY)
    plt.scatter(X, Y)
    plt.grid(b=True)
    plt.xlim((0, max_xy))
    plt.ylim((0, max_xy))
    plt.xticks(np.arange(0, max_xy, 1))
    plt.yticks(np.arange(0, max_xy, 1))
    plt.show()
'''

def main():
    N = int(input())
    XY = [list(map(int, input().split())) for _ in range(N)]

    Xs = []
    Ys = []
    for i, (x, y) in enumerate(XY):
        Xs.append((i, x))
        Ys.append((i, y))
    Xs.sort(key=itemgetter(1))
    Ys.sort(key=itemgetter(1))

    Ix, X = zip(*Xs)
    Iy, Y = zip(*Ys)
    # Ix, Iy are indexes of XY
    Rx = [None]*N
    Ry = [None]*N
    for i, (ix, iy) in enumerate(zip(Ix, Iy)):
        Rx[ix] = i
        Ry[iy] = i

    # take nearest 4s
    graph = [[] for _ in range(N)]
    for i, (x, y) in enumerate(XY):
        nexts = set()
        ix = Rx[i]
        if ix != 0:
            nexts.add(Ix[ix-1])
        if ix != N-1:
            nexts.add(Ix[ix+1])
        
        iy = Ry[i]
        if iy != 0:
            nexts.add(Iy[iy-1])
        if iy != N-1:
            nexts.add(Iy[iy+1])
        
        for n in nexts:
            d = min(abs(XY[n][0]-XY[i][0]), abs(XY[n][1]-XY[i][1]))
            graph[i].append((d, n))



    checked = [False for _ in range(N)]
    checked[0] = True 
    q = [] # しまっていく優先度付きキュー
    for d, n in graph[0]:
        hp.heappush(q, (d, n))
    ans = 0

    #print(graph)
    while q:
        nd, np = hp.heappop(q) # 一番距離が近いものを取ってくる
        #print(nd, np, q)
        if checked[np]: # 追加した後の残骸は見ない
            continue
        ans += nd
        #print(ans)
        checked[np] = True
        for d, p in graph[np]:
            if not checked[p]:
                hp.heappush(q, (d, p))

    print(ans)
            

if __name__ == "__main__":
    #print('input data')
    #N = 9
    #max_xy = 20
    #N, XY = graph_ABC065D(N, max_xy)
    #print('answer')
    #main(N, XY)
    #plot(N, XY, max_xy)

    main()

Submission status: Accepted

Solution code:
import sys,bisect as bs,collections as cl,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
n = onem()
data = []
edges = []
for i in range(n):
    kkk = l()
    data.append([i]+ kkk)
ddd = sorted(data,key = lambda x:x[1])
bbb = sorted(data,key = lambda x:x[2])

Ne = cl.defaultdict(list)
for i in range(1,n):
    Ne[ddd[i-1][0]].append((ddd[i][0],ddd[i][1]-ddd[i-1][1]))
    Ne[ddd[i][0]].append((ddd[i-1][0],ddd[i][1]-ddd[i-1][1]))
    Ne[bbb[i-1][0]].append((bbb[i][0],bbb[i][2]-bbb[i-1][2]))
    Ne[bbb[i][0]].append((bbb[i-1][0],bbb[i][2]-bbb[i-1][2]))

is_used = [False for i in range(n+1)]
h = []
hq.heappush(h,(0,1))
ans = 0

while h:
    d,n = hq.heappop(h)
    if is_used[n]:
        continue
    ans += d
    is_used[n] = True
    for z,x in Ne[n]:

        if not is_used[z]:
            hq.heappush(h,(x,z))

print(ans)

Submission status: Accepted

Solution code:
def find(u,x):
    if u[x]<0:
        return x
    u[x] = find(u,u[x])
    return u[x]

def unite(u,a,b):
    a = find(u,a)
    b = find(u,b)
    if a == b:
        return False
    if u[b] < u[a]:
        a,b = b,a
    u[a] += u[b]
    u[b] = a
    return True

def same(u,x,y):
    return find(u,x) == find(u,y)

n = int(input())
l = list()
for i in range(n):
  x,y = map(int,input().split())
  l.append((x,y,i))
l.sort()
uf = [-1]*(n+1)
ed = list()
for i in range(n-1):
  ed.append((l[i][2],l[i+1][2],l[i+1][0]-l[i][0]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
  ed.append((l[i][2],l[i+1][2],l[i+1][1]-l[i][1]))
ed.sort(key=lambda x:x[2])
ans = 0
for x,y,d in ed:
  if not same(uf,x,y):
    unite(uf,x,y)
    ans += d
print(ans)

Submission status: Accepted

Solution code:
#D問題
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

import heapq

N = int(input())

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

XY0.sort()
XY1 = sorted(XY1, key=lambda x: x[1])

E = []
for i,x in enumerate(XY0):
    if i == 0:
        ox = x[0]
        oi = x[2]
    else:
        dx = x[0]-ox
        ox = x[0]
        heapq.heappush(E,[dx,oi,x[2]])
        oi = x[2]

for i,y in enumerate(XY1):
    if i == 0:
        oy = y[1]
        oi = y[2]
    else:
        dy = y[1]-oy
        oy = y[1]
        heapq.heappush(E,[dy,oi,y[2]])
        oi = y[2]



V = [i for i in range(N)]
ans = 0
while E:
    w,s,t = heapq.heappop(E)
    if find(V,s) != find(V,t):
        union(V,s,t)
        ans+=w
        
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
T=[list(map(int,input().split()))+[i] for i in range(N)]

E=[]

T.sort()
for i in range(1,N):
    E.append((T[i][0]-T[i-1][0],T[i-1][2],T[i][2]))

T.sort(key=lambda x:x[1])
for i in range(1,N):
    E.append((T[i][1]-T[i-1][1],T[i-1][2],T[i][2]))

# UnionFind

Group=[i for i in range(N)]# グループ分け.Group[i]=jのときiとjは同じグループ

def find(x):# find(a)=find(b)のとき同じグループ
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):  # xとyが同じグループになるよう更新
    if find(x) != find(y):
        Group[find(y)]=Group[find(x)]=min(find(y),find(x))


E.sort()
ANS=0
for c,x,y in E:
    if find(x)!=find(y):
        Union(x,y)
        ANS+=c

print(ANS)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

from heapq import heappop,heappush

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

e = [[] for _ in range(n)]

p = sorted(p,key=lambda x:x[1])
n0,x0,y0 = p[0]
for i in range(n-1):
    n1,x1,y1 = p[i+1]
    e[n0].append((min(abs(x1-x0),abs(y1-y0)),n1))
    e[n1].append((min(abs(x1-x0),abs(y1-y0)),n0))
    n0,x0,y0 = n1,x1,y1

p = sorted(p,key=lambda x:x[2])
n0,x0,y0 = p[0]
for i in range(n-1):
    n1,x1,y1 = p[i+1]
    e[n0].append((min(abs(x1-x0),abs(y1-y0)),n1))
    e[n1].append((min(abs(x1-x0),abs(y1-y0)),n0))
    n0,x0,y0 = n1,x1,y1

def Prim(n,edge):
    #edge[source] = [(cost_1,target_1),(cost_2,target_2),...]
    used = [False] * n
    q = []
    #e = [cost,target]
    for e in edge[0]:
        heappush(q,e)
    used[0] = True
    res = 0
    while q:
        c,v = heappop(q)
        if used[v]:
            continue
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(q,e)
        res += c
    return res

print(Prim(n,e))

Submission status: Accepted

Solution code:
from heapq import heappop,heappush

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

e = [[] for _ in range(n)]

p = sorted(p,key=lambda x:x[1])
n0,x0,y0 = p[0]
for i in range(n-1):
    n1,x1,y1 = p[i+1]
    e[n0].append((min(abs(x1-x0),abs(y1-y0)),n1))
    e[n1].append((min(abs(x1-x0),abs(y1-y0)),n0))
    n0,x0,y0 = n1,x1,y1

p = sorted(p,key=lambda x:x[2])
n0,x0,y0 = p[0]
for i in range(n-1):
    n1,x1,y1 = p[i+1]
    e[n0].append((min(abs(x1-x0),abs(y1-y0)),n1))
    e[n1].append((min(abs(x1-x0),abs(y1-y0)),n0))
    n0,x0,y0 = n1,x1,y1

def Prim(n,edge):
    #edge[source] = [(cost_1,target_1),(cost_2,target_2),...]
    used = [False] * n
    q = []
    #e = [cost,target]
    for e in edge[0]:
        heappush(q,e)
    used[0] = True
    res = 0
    while q:
        c,v = heappop(q)
        if used[v]:
            continue
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(q,e)
        res += c
    return res

print(Prim(n,e))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

from heapq import heappop,heappush

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

e = [[] for _ in range(n)]

p = sorted(p,key=lambda x:x[1])
n0,x0,y0 = p[0]
for i in range(n-1):
    n1,x1,y1 = p[i+1]
    e[n0].append([min(abs(x1-x0),abs(y1-y0)),n1])
    e[n1].append([min(abs(x1-x0),abs(y1-y0)),n0])
    n0,x0,y0 = n1,x1,y1

p = sorted(p,key=lambda x:x[2])
n0,x0,y0 = p[0]
for i in range(n-1):
    n1,x1,y1 = p[i+1]
    e[n0].append([min(abs(x1-x0),abs(y1-y0)),n1])
    e[n1].append([min(abs(x1-x0),abs(y1-y0)),n0])
    n0,x0,y0 = n1,x1,y1

def Prim(n,edge):
    #edge[source] = [[cost_1,target_1],[cost_2,target_2],...]
    used = [False] * n
    q = []
    #e = [cost,target]
    for e in edge[0]:
        heappush(q,e)
    used[0] = True
    res = 0
    while q:
        c,v = heappop(q)
        if used[v]:
            continue
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(q,e)
        res += c
    return res

print(Prim(n,e))

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
import heapq

def solve():
    input = sys.stdin.readline
    N = int(input())
    town = dict()
    road = [None] * N
    roadx, roady = [None] * N, [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        town[(x, y, i)] = i
        road[i] = (x, y, i)
        roadx[i] = (x, y, i)
        roady[i] = (x, y, i)
    roadx.sort()
    roadx_id = dict()
    roady.sort(key = itemgetter(1))
    roady_id = dict()
    for i in range(N):
        roadx_id[roadx[i]] = i
        roady_id[roady[i]] = i

    visited = [False] * N
    q = []
    heapq.heapify(q)
    heapq.heappush(q, (0, 0)) #(cost, town_id)
    cost = 0
    while q:
        add_cost, id = heapq.heappop(q)
        #print(add_cost, id, cost)
        #print(visited)
        if not visited[id]:
            cost += add_cost
            visited[id] = True
            for s in range(2):
                nx = roadx_id[road[id]] + (-1) ** s #roadxにおけるid
                if 0 <= nx < N:
                    if not visited[town[roadx[nx]]]: heapq.heappush(q, (min(abs(road[id][0] - roadx[nx][0]), abs(road[id][1] - roadx[nx][1])), town[roadx[nx]]))
                
                ny = roady_id[road[id]] + (-1) ** s #roadyにおけるid
                if 0 <= ny < N:
                    if not visited[town[roady[ny]]]: heapq.heappush(q, (min(abs(road[id][1] - roady[ny][1]), abs(road[id][1] - roady[ny][1])), town[roady[ny]]))
    
    print(cost)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N=int(input())
x,y=map(list,zip(*[list(map(int,input().split())) for i in range(N)]))
x=sorted(zip(x,range(N)))
y=sorted(zip(y,range(N)))
from heapq import heappop,heappush
qx,qy=[(10**9+1,0,0)],[(10**9+1,0,0)]
for i in range(N-1):
    heappush(qx,(x[i+1][0]-x[i][0],x[i][1],x[i+1][1]))
    heappush(qy,(y[i+1][0]-y[i][0],y[i][1],y[i+1][1]))
r=0
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
u=UnionFind(N)
while u.size(0)<N:
    d,i,j=heappop(qx) if qx[0]<qy[0] else heappop(qy)
    if u.unite(i,j):
        r+=d
print(r)

Submission status: Accepted

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

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

    return

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

#C
def C():
    return

#D
def D():
    def find(x):
        if x == par[x]:
            return x
        par[x] = find(par[x])
        return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y: return False
        if x < y: x, y = y, x
        par[y] = x
        return True
    n = II()
    par = [i for i in range(n)]
    xy = LIR(n)
    for i in range(n):
        xy[i].append(i)
    xy.sort(key=lambda x: x[0])
    edg = [None] * (2 * n - 2)
    a = 0
    for i in range(n-1):
        edg[i] = [xy[i + 1][0] - xy[i][0], xy[i][2], xy[i + 1][2]]
    xy.sort(key=lambda x: x[1])
    for i in range(n-1):
        edg[n + i - 1] = [xy[i + 1][1] - xy[i][1], xy[i][2], xy[i + 1][2]]
    ans = 0
    a = 0
    edg.sort(key=lambda x: x[0])
    for i in range(2 * n - 2):
        value, p0, p1 = edg[i]
        if a == n - 1:
            break
        if unite(p0, p1):
            a += 1
            ans += value
    print(ans)
    return

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

Submission status: Accepted

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

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

    return

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

#C
def C():
    return

#D
def D():
    def find(x):
        if x == par[x]:
            return x
        par[x] = find(par[x])
        return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y: return False
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
        return True
    n = II()
    par = [i for i in range(n)]
    rank = [0] * n
    xy = LIR(n)
    for i in range(n):
        xy[i].append(i)
    xy.sort(key=lambda x: x[0])
    edg = [None] * (2 * n - 2)
    a = 0
    for i in range(n-1):
        edg[i] = [xy[i + 1][0] - xy[i][0], xy[i][2], xy[i + 1][2]]
    xy.sort(key=lambda x: x[1])
    for i in range(n-1):
        edg[n + i - 1] = [xy[i + 1][1] - xy[i][1], xy[i][2], xy[i + 1][2]]
    ans = 0
    a = 0
    edg.sort(key=lambda x: x[0])
    for i in range(2 * n - 2):
        value, p0, p1 = edg[i]
        if a == n - 1:
            break
        if unite(p0, p1):
            a += 1
            ans += value
    print(ans)
    return

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

Submission status: Accepted

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

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

    return

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

#C
def C():
    return

#D
def D():
    def find(x):
        if x == par[x]:
            return x
        par[x] = find(par[x])
        return par[x]
    def same(x, y):
        return find(x) == find(y)
    def unite(x, y):
        x = find(x)
        y = find(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
        return True
    n = II()
    par = [i for i in range(n)]
    rank = [0] * n
    xy = LIR(n)
    for i in range(n):
        xy[i].append(i)
    xy.sort(key=lambda x: x[0])
    edg = [None] * (2 * n - 2)
    a = 0
    for i in range(n-1):
        edg[i] = [xy[i + 1][0] - xy[i][0], xy[i][2], xy[i + 1][2]]
    xy.sort(key=lambda x: x[1])
    for i in range(n-1):
        edg[n + i - 1] = [xy[i + 1][1] - xy[i][1], xy[i][2], xy[i + 1][2]]
    ans = 0
    a = 0
    edg.sort(key=lambda x: x[0])
    for i in range(2 * n - 2):
        value, p0, p1 = edg[i]
        if a == n - 1:
            break
        if not same(p0, p1):
            unite(p0, p1)
            a += 1
            ans += value
    print(ans)
    return

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