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: Time Limit Exceeded

Solution code:
def main():
    import heapq
    class unionfind():
        #size:要素数,tree：unionfind木
        def __init__(self,size):#self,要素数
            self.size=size
            self.tree=[[i,1] for i in range(self.size)]#root,depth
        
        #rootを探す
        def root(self,index):
            if self.tree[index][0]==index:
                return index
            else:
                self.tree[index][0]=self.root(self.tree[index][0])
                return self.tree[index][0]
    
        #結合
        def unite(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1!=r2:
                d1,d2=self.tree[r1][1],self.tree[r2][1]
                if d1<=d2:
                    self.tree[r1][0]=r2
                    self.tree[r2][1]=max(d1+1,d2)
                else:
                    self.tree[r2][0]=r1
                    self.tree[r1][1]=max(d2+1,d1)
    
        #同じか判定
        def same(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            return r1==r2
    
        #連結成分の個数
        def component(self):
            return len({self.root(i) for i in range(self.size)})
    
    n=int(input())
    xy=[list(map(int,input().split())) for _ in [0]*n]
    xyz=[xy[i]+[i] for i in range(n)]
    x_sort=sorted(xyz,key=lambda x:x[0])
    y_sort=sorted(xyz,key=lambda x:x[1])
    g=[]
    for i in range(n-1):
        g.append([abs(x_sort[i+1][0]-x_sort[i][0]),x_sort[i][2],x_sort[i+1][2]])
        g.append([abs(y_sort[i+1][1]-y_sort[i][1]),y_sort[i][2],y_sort[i+1][2]])
    heapq.heapify(g)
    u=unionfind(n)
    cnt=0
    while g:
        d,i,j=heapq.heappop(g)
        if u.same(i,j)==False:
            cnt+=d
            u.unite(i,j)
    print(cnt)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])

def graphm():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((w,b))
        g[b].append((w,a))
    return n,m,g

def prim(n,g):
    edgelist = []
    used = [False for _ in range(n)]
    for edge in g[0]:
        heappush( edgelist, edge)
    used[0] = True
    res = 0 

    while len(edgelist)>0:
        minedge = heappop(edgelist)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = True
        for edge in g[v]:
            if not used[edge[1]]:
                heappush( edgelist, edge)
        res += minedge[0]
    return res

def main():
    n=inp()
    xy=[]
    for _ in range(n):
        x,y = inpm()
        xy.append((x,y))
    g=[[] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            w = min(abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1]))
            g[i].append((w,j))
            g[j].append((w,i))
    print( prim(n,g) )

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    while True:
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            n -= 1
            ans += d
        if n < 2: return ans
    return ans

n = int(input())
x, y = [None]*n, [None]*n
dist = [[0] * n for _ in range(n)]

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

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

edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

del x, y
print(kruskal(n, edge))

Submission status: Time Limit Exceeded

Solution code:
import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    for i in range(len(edge)):
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            n -= 1
            ans += d
        if n < 1: return ans
    return ans

n = int(input())
x, y = [None]*n, [None]*n
dist = [[0] * n for _ in range(n)]

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

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

edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

del x, y
print(kruskal(n, edge))

Submission status: Time Limit Exceeded

Solution code:
import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])
            
def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    for i in range(len(edge)):
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            n -= 1
            ans += d
            if n < 1: return ans
    return ans

n = int(input())
x, y = [None]*n, [None]*n
dist = [[0] * n for _ in range(n)]
 
for i in range(n):
    a, b = map(int, input().split())
    x[i] = (a, i)
    y[i] = (b, i)
    
x.sort(key=lambda x:x[0])
y.sort(key=lambda y:y[0])
 
edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))
    
del x, y
print(kruskal(n, edge))

Submission status: Time Limit Exceeded

Solution code:
import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    for i in range(len(edge)):
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            n -= 1
            ans += d
            if n < 1: return ans
    return ans

n = int(input())
x, y = [None]*n, [None]*n
dist = [[0] * n for _ in range(n)]

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

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

edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

del x, y
print(kruskal(n, edge))

Submission status: Time Limit Exceeded

Solution code:
import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    for i in range(len(edge)):
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            ans += d
    return ans

n = int(input())
x, y = [None]*n, [None]*n
dist = [[0] * n for _ in range(n)]

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

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

edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

del x, y
print(kruskal(n, edge))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    edge.sort(key=lambda x:x[0])
    for i in range(len(edge)):
        d, v, u = edge[i]
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            ans += d
    return ans

n = int(input())
x, y = [None]*n, [None]*n
dist = [[0] * n for _ in range(n)]

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

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

edge_x = []
edge_y = []
for i in range(n-1):
    edge_x.append((x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    edge_y.append((y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

del x, y
print(kruskal(n, edge_x+edge_y))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    uf = UnionFind(n)
    mst_edge = []
    edge.sort(key=lambda x:x[0])
    for i in range(len(edge)):
        d, v, u = edge[i]
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            mst_edge.append((v, u, d))
    
    return mst_edge  

n = int(input())
x, y = [None]*n, [None]*n
dist = [[0] * n for _ in range(n)]

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

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

edge_x = []
edge_y = []
for i in range(n-1):
    edge_x.append((x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    edge_y.append((y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

mst = kruskal(n, edge_x+edge_y)

print(sum([i[2] for i in mst]))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])
            
def kruskal(n, **args):
    uf = UnionFind(n)
    mst_edge = []
    
    edge = []
    if "dist" in args:
        for i in range(n):
            for t in range(i+1, n):
                edge.append((args["dist"][i][t], i, t))
    elif "edge" in args:
        edge = args["edge"]

    edge.sort(key=lambda x:x[0])
    for i in range(len(edge)):
        d, v, u = edge[i]
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            mst_edge.append((v, u, d))
    
    return mst_edge  
  
n = int(input())
x, y = [None]*n, [None]*n
dist = [[0] * n for _ in range(n)]

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

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

edge_x = []
edge_y = []
for i in range(n-1):
    edge_x.append((x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    edge_y.append((y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

mst = kruskal(n, edge=edge_x+edge_y)
print(sum([i[2] for i in mst]))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import heapq

N = int(input())
X = [[int(p) for p in input().split()] for _ in range(N)]

X.sort()
for i in range(N):
    X[i].append(i)
    
Y = sorted(X, key=itemgetter(1))

h = []
for i in range(N-1):
    heapq.heappush(h, (X[i+1][0]-X[i][0], i+1, i))
    heapq.heappush(h, (Y[i+1][1]-Y[i][1], Y[i+1][2], Y[i][2]))
    
    
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]
    
    
UF = UnionFind(N)
ans = 0
while h:
    t = heapq.heappop(h)
    if UF.isSameGroup(t[1], t[2]):
        continue
    ans += t[0]
    UF.unite(t[1], t[2])
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import heapq

N = int(input())
pos = [[int(p) for p in input().split()] for _ in range(N)]

pos.sort()
for i in range(N):
    pos[i].append(i)
    
Y = sorted(pos, key=itemgetter(1))
Y_idx = [0]*N
for i in range(N):
    Y_idx[Y[i][2]] = i
    
ans = 0
used = [0]*N
used[0] = 1
h = []
c = 1
idx = Y_idx[0]
heapq.heappush(h, (pos[c][0]-pos[c-1][0], 1))
if idx > 0:
    heapq.heappush(h, (Y[idx][1]-Y[idx-1][1], Y[idx-1][2]))
if idx < N-1:
    heapq.heappush(h, (Y[idx+1][1]-Y[idx][1], Y[idx+1][2]))
    
cnt = 0
while cnt < N-1:
    t = heapq.heappop(h)
    if used[t[1]] == 1:
        continue
    c = t[1]
    used[c] = 1
    cnt += 1
    ans += t[0]
    if c > 0 and used[c-1] == 0:
        heapq.heappush(h, (pos[c][0]-pos[c-1][0], c-1))
    if c < N-1 and used[c+1] == 0:
        heapq.heappush(h, (pos[c+1][0]-pos[c][0], c+1))
    idx = Y_idx[c]
    if idx > 0 and used[Y[idx-1][2]] == 0:
        heapq.heappush(h, (Y[idx][1]-Y[idx-1][1], Y[idx-1][2]))
    if idx < N-1 and used[Y[idx+1][2]] == 0:
        heapq.heappush(h, (Y[idx+1][1]-Y[idx][1], Y[idx+1][2]))
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
from heapq import heappop, heappush

#入力受け取り
def getlist():
	return list(map(int, input().split()))

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

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

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

    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

class Kruskal:
    def __init__(self, Q, n):
        self.uf = UnionFind(n)
        self.cost = 0
        self.Q = Q
        while self.Q:
            w, u, v = heappop(self.Q)
            if self.uf.same_check(u, v) != True:
                self.uf.union(u, v)
                self.cost += w

#処理内容
def main():
	N = int(input())
	Lx = []
	Ly = []
	for i in range(N):
	    x, y = list(map(int, input().split()))
	    Lx.append((x, i))
	    Ly.append((y, i))
	Lx = sorted(Lx)
	Ly = sorted(Ly)
	Q = []

	for i in range(N - 1):
	    u = Lx[i][1]
	    v = Lx[i + 1][1]
	    w = Lx[i + 1][0] - Lx[i][0]
	    heappush(Q, (w, u, v))
	    u = Ly[i][1]
	    v = Ly[i + 1][1]
	    w = Ly[i + 1][0] - Ly[i][0]
	    heappush(Q, (w, u, v))

	Km = Kruskal(Q, N)
	print(Km.cost)	

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

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)

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

townx = sorted(town)
towny = sorted(town,key = lambda t : t[1])

heap = []
heapq.heapify(heap)

for i in range(N-1):
    heapq.heappush(heap,[abs(townx[i][0]-townx[i+1][0]),townx[i][2],townx[i+1][2]])
    heapq.heappush(heap,[abs(towny[i][1]-towny[i+1][1]),towny[i][2],towny[i+1][2]])

uf = UnionFind(N)
ans = 0

while heap:
    cost,t1,t2 = heapq.heappop(heap)
    if uf.same(t1,t2):
        continue
    uf.union(t1,t2)
    ans += cost
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)


par  =[]
N = int(input())

graph = []

for _ in range(N):
    x, y = [int(s) for s in input().split()]
    graph.append((x, y))

sort_x = sorted(graph, key=lambda x: x[0])
sort_y = sorted(graph, key=lambda x: x[1])

edges = []

for i in range(len(sort_x)-1):
    a, b = sort_x[i]
    c, d = sort_x[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((a, c, w))
    a, b = sort_y[i]
    c, d = sort_y[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((b, d, w))


for i in range(10**9):
    par.append(i)



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

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

def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y

ans = 0
edges = sorted(edges, key=lambda x: x[2])
for edge in edges:
    if not same(edge[0], edge[1]):
        union(edge[0], edge[1])
        ans += edge[2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

def init(n):
    return list(range(n+1))

def find(lis, x):
    if lis[x] == x:
        return x
    else:
        lis[x] = find(lis, lis[x])
        return lis[x]

def sameset(lis, x, y):
    return find(lis, x) == find(lis, y)

def union(lis, x, y):
    x = find(lis, x)
    y = find(lis, y)
    if x != y:
        lis[x] = y

N = int(input())
union_find_tree = init(N)

town = []

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

x_sorted_town = sorted(town, key=lambda x: x[1])
y_sorted_town = sorted(town, key=lambda x: x[2])

graph = []

pre_tx = x_sorted_town[0]
pre_ty = y_sorted_town[0]
pre_nx = town[pre_tx[0]]
pre_ny = town[pre_ty[0]]
for tx, ty in zip(x_sorted_town[1:], y_sorted_town[1:]):
    nx = town[tx[0]]
    ny = town[ty[0]]
    wx = min(abs(tx[1] - pre_tx[1]), abs(nx[2] - pre_nx[2]))
    wy = min(abs(ty[2] - pre_ty[2]), abs(ny[1] - pre_ny[1]))
    graph.append((nx[0], pre_nx[0], wx))
    graph.append((ny[0], pre_ny[0], wy))
    pre_tx = tx
    pre_ty = ty
    pre_nx = nx
    pre_ny = ny

cost = 0
for (s,t,w) in sorted(graph, key=lambda x: x[2]):
    if not sameset(union_find_tree,s,t):
        union(union_find_tree,s,t)
        cost += w
print(cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
from collections import defaultdict

import collections
import itertools
import operator


class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]


'''
def init(n):
    return list(range(n+1))#
def find(lis, x):
    if lis[x] == x:
        return x
    else:
        lis[x] = find(lis, lis[x])
        return lis[x]

def sameset(lis, x, y):
    return find(lis, x) == find(lis, y)

def union(lis, x, y):
    x = find(lis, x)
    y = find(lis, y)
    if x != y:
        lis[x] = y
'''

N = int(input())
#union_find_tree = init(N)

town = []

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

x_sorted_town = sorted(town, key=lambda x: x[1])
y_sorted_town = sorted(town, key=lambda x: x[2])

graph = []

pre_tx = x_sorted_town[0]
pre_ty = y_sorted_town[0]
pre_nx = town[pre_tx[0]]
pre_ny = town[pre_ty[0]]
for tx, ty in zip(x_sorted_town[1:], y_sorted_town[1:]):
    nx = town[tx[0]]
    ny = town[ty[0]]
    wx = min(abs(tx[1] - pre_tx[1]), abs(nx[2] - pre_nx[2]))
    wy = min(abs(ty[2] - pre_ty[2]), abs(ny[1] - pre_ny[1]))
    graph.append((nx[0], pre_nx[0], wx))
    graph.append((ny[0], pre_ny[0], wy))
    pre_tx = tx
    pre_ty = ty
    pre_nx = nx
    pre_ny = ny

uf = UnionFind()

cost = 0
for (s,t,w) in sorted(graph, key=lambda x: x[2]):
    if not uf.are_same(s,t):
        uf.unite(s,t)
        cost += w
print(cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
from collections import defaultdict

def init(n):
    return list(range(n+1))

def find(lis, x):
    if lis[x] == x:
        return x
    else:
        lis[x] = find(lis, lis[x])
        return lis[x]

def sameset(lis, x, y):
    return find(lis, x) == find(lis, y)

def union(lis, x, y):
    x = find(lis, x)
    y = find(lis, y)
    if x != y:
        lis[x] = y

N = int(input())
union_find_tree = init(N)

town = []

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

x_sorted_town = sorted(town, key=lambda x: x[1])
y_sorted_town = sorted(town, key=lambda x: x[2])

graph = []

pre_tx = x_sorted_town[0]
pre_ty = y_sorted_town[0]
pre_nx = town[pre_tx[0]]
pre_ny = town[pre_ty[0]]
for tx, ty in zip(x_sorted_town[1:], y_sorted_town[1:]):
    nx = town[tx[0]]
    ny = town[ty[0]]
    wx = min(abs(tx[1] - pre_tx[1]), abs(nx[2] - pre_nx[2]))
    wy = min(abs(ty[2] - pre_ty[2]), abs(ny[1] - pre_ny[1]))
    graph.append((nx[0], pre_nx[0], wx))
    graph.append((ny[0], pre_ny[0], wy))
    pre_tx = tx
    pre_ty = ty
    pre_nx = nx
    pre_ny = ny

cost = 0
for (s,t,w) in sorted(graph, key=lambda x: x[2]):
    if not sameset(union_find_tree,s,t):
        union(union_find_tree,s,t)
        cost += w
print(cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
from collections import defaultdict

def init(n):
    return list(range(n+1))

def find(lis, x):
    if lis[x] == x:
        return x
    else:
        lis[x] = find(lis, lis[x])
        return lis[x]

def sameset(lis, x, y):
    return find(lis, x) == find(lis, y)

def union(lis, x, y):
    x = find(lis, x)
    y = find(lis, y)
    if x != y:
        lis[x] = y

N = int(input())
union_find_tree = init(N)

town = []

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

x_sorted_town = sorted(sorted(town, key=lambda x: x[2]), key=lambda x: x[1])
y_sorted_town = sorted(sorted(town, key=lambda x: x[1]), key=lambda x: x[2])

graph = []

pre_tx = x_sorted_town[0]
pre_ty = y_sorted_town[0]
pre_nx = town[pre_tx[0]]
pre_ny = town[pre_ty[0]]
for tx, ty in zip(x_sorted_town[1:], y_sorted_town[1:]):
    nx = town[tx[0]]
    ny = town[ty[0]]
    wx = min(abs(tx[1] - pre_tx[1]), abs(nx[2] - pre_nx[2]))
    wy = min(abs(ty[2] - pre_ty[2]), abs(ny[1] - pre_ny[1]))
    graph.append((nx[0], pre_nx[0], wx))
    graph.append((ny[0], pre_ny[0], wy))
    pre_tx = tx
    pre_ty = ty
    pre_nx = nx
    pre_ny = ny

cost = 0
for (s,t,w) in sorted(graph, key=lambda x: x[2]):
    if not sameset(union_find_tree,s,t):
        union(union_find_tree,s,t)
        cost += w
print(cost)

Submission status: Time Limit Exceeded

Solution code:
def find(A,x) -> int:
    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

def examD():
    N = I()
    x = [[] for _ in range(N)]; y = [[] for _ in range(N)]
    for i in range(N):
        a, b = LI()
        x[i] = (a-1,i)
        y[i] = (b-1,i)
    v = [ i for i in range(N)]
    x.sort(); y.sort()
    H = []
    heapify(H)
    for i in range(N - 1):
        x1, j1 = x[i]
        x2, j2 = x[i + 1]
        y1, k1 = y[i]
        y2, k2 = y[i + 1]
        heappush(H, (x2 - x1, j1, j2))
        heappush(H, (y2 - y1, k1, k2))
    ans = 0
#    print(H)
#    print(v)
    while H:
        w, s, t = heappop(H)
        if find(v, s) != find(v, t):
            union(v, s, t)
            ans += w
    print(ans)

import sys
import copy
import bisect
from heapq import *
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Time Limit Exceeded

Solution code:
def find(A,x) -> int:
    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

def examD():
    N = I()
    x = [[] for _ in range(N)]; y = [[] for _ in range(N)]
    for i in range(N):
        a, b = LI()
        x[i] = (a-1,i)
        y[i] = (b-1,i)
    v = [ i for i in range(N)]
    X = sorted(x,key=lambda x:x[0])
    Y = sorted(y,key=lambda x:x[0])
    H = []
    heapify(H)
    for i in range(N - 1):
        x1, j1 = X[i]
        x2, j2 = X[i + 1]
        y1, k1 = Y[i]
        y2, k2 = Y[i + 1]
        heappush(H, (x2 - x1, j1, j2))
        heappush(H, (y2 - y1, k1, k2))
    ans = 0
#    print(H)
#    print(v)
    while H:
        w, s, t = heappop(H)
        if find(v, s) != find(v, t):
            union(v, s, t)
            ans += w
    print(ans)

import sys
import copy
import bisect
from heapq import *
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()