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 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
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)

    #print (a,b,cost,p,ans)

    if ap != bp:
        ans += cost

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

Solution code:
import heapq

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

    heapq.heappush(line,[ xyi[i+1][0]-xyi[i][0] , xyi[i][2] , xyi[i+1][2] ])
    heapq.heappush(line,[ 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
ans = 0

while len(line) > 0:

    e = heapq.heappop(line)
    cost = e[0]
    a = e[1]
    b = e[2]

    ap = want_p(a)
    bp = want_p(b)

    #print (a,b,cost,p,ans)

    if ap != bp:
        ans += cost

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

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

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

Solution code:
from heapq import heappop,heappush
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)]
for i in range(n-1):
    p,q,r=a[i][0],a[i+1][0],a[i+1][1]-a[i][1]
    s[p].append([r,p,q])
    s[q].append([r,q,p])
a=sorted(a,key=lambda x:x[2])
for i in range(n-1):
    p,q,r=a[i][0],a[i+1][0],a[i+1][2]-a[i][2]
    s[p].append([r,p,q])
    s[q].append([r,q,p])
t=[1]*n
t[0],q,r=0,[],1
e=0
for i in s[0]:
    heappush(q,i)
while q and r!=n:
    b,c,d=heappop(q)
    if t[d]==1:
        t[d]=0
        for i in s[d]:
            if t[i[2]]==1:
                heappush(q,i)
        e+=b
        r+=1
print(e)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush
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)]
for i in range(n-1):
    p,q,r=a[i][0],a[i+1][0],a[i+1][1]-a[i][1]
    s[p].append([r,p,q])
    s[q].append([r,q,p])
a=sorted(a,key=lambda x:x[2])
for i in range(n-1):
    p,q,r=a[i][0],a[i+1][0],a[i+1][2]-a[i][2]
    s[p].append([r,p,q])
    s[q].append([r,q,p])
t=[1]*n
t[0],q=0,[]
e=0
for i in s[0]:
    heappush(q,i)
while q and t!=[0]*n:
    b,c,d=heappop(q)
    if t[d] or t[c]:
        if t[d]==1:
            for i in s[d]:
                heappush(q,i)
            t[d]=0
        if t[c]==1:
            for i in s[c]:
                heappush(q,i)
            t[c]=0
        e+=b
print(e)

Submission status: Time Limit Exceeded

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 = sorted(xquery)
  yquery = sorted(yquery)
  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))
    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))
    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: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import minimum_spanning_tree
import sys
input = sys.stdin.readline
def solve():
  n = int(input())
  D = [[0]*n for _ in range(n)]
  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))
    D[place][place2] = cost

    
    tx,ty,place = yquery[i]
    tx2,ty2,place2 = yquery[i+1]
    cost = min(abs(tx2-tx),abs(ty2-ty))
    D[place][place2] = cost
    
  D = minimum_spanning_tree(D)
  print(int(D.sum()))
solve()

Submission status: Time Limit Exceeded

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

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()


class Union_Find():
	def __init__(self, n):
		self.union = [i for i in range(n)]
		self.level = [0 for i in range(n)]

	def root(self, i, mode=0):
		keiro = [i]
		ans = i
		while ans != self.union[ans]:
			ans = self.union[ans]
			keiro.append(ans)
		if mode == 0:
			return ans
		else:
			return ans, keiro

	def unite(self, i, j):
		root_i, list_i = self.root(i, 1)
		root_j, list_j = self.root(j, 1)
		if root_i != root_j:
			if self.level[root_i] < self.level[root_j]:
				self.level[root_j] = max(self.level[root_i] + 1, self.level[root_j])
				for node in list_i:
					self.union[node] = root_j
			else:
				self.level[root_i] = max(self.level[root_j] + 1, self.level[root_i])
				for node in list_j:
					self.union[node] = root_i

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 = []
heapq.heapify(edge)
for i in range(N - 1):
	heapq.heappush(edge, [xy1[i + 1][0] - xy1[i][0], xy1[i + 1][1], xy1[i][1]])
	heapq.heappush(edge, [xy2[i + 1][0] - xy2[i][0], xy2[i + 1][1], xy2[i][1]])

UF = Union_Find(N)
road = 0
total = 0
while road < N - 1:
	edge_now = heapq.heappop(edge)
	if UF.root(edge_now[1]) != UF.root(edge_now[2]):
		road += 1
		total += edge_now[0]
		UF.unite(edge_now[1], edge_now[2])

print(total)

Submission status: Time Limit Exceeded

Solution code:
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)]

n = int(input())
arr = []
ans = 0
for i in range(n):
    arr.append([i] + list(map(int,input().split())))
x_sort = sorted(arr, key = lambda x:x[1])
y_sort = sorted(arr, key = lambda x:x[2])

import heapq as hq

q = []

for i in range(n-1):
    costx = x_sort[i+1][1] - x_sort[i][1]
    costy = y_sort[i+1][2] - y_sort[i][2]
    hq.heappush(q, [costx, x_sort[i][0], x_sort[i+1][0] ])
    hq.heappush(q, [costy, y_sort[i][0], y_sort[i+1][0] ])

uf = UnionFind(n)
for rep in range(3*10**5):
    cost, a, b = hq.heappop(q)
    if uf.isSameGroup(a, b):
        continue
    else:
        uf.Unite(a, b)
        ans += cost
    if uf.Count(0) == n:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

import heapq
n = int(input())
l = [[0, 0] for i in range(n)]
for i in range(n):
  x, y = map(int, input().split())
  l[i][0] = x
  l[i][1] = y
  
graph = []
for i in range(n-1):
  x1, y1 = l[i]
  for j in range(i, n):
    x2, y2 = l[j]
    graph.append((min(abs(x1-x2), abs(y1-y2)), i, j))
    graph.append((min(abs(x1-x2), abs(y1-y2)), j, i))

#union find
def Find(x, par):
  if par[x] < 0:
    return x
  else:
    # 経路圧縮
    par[x] = Find(par[x], par)
    return par[x]

def Unite(x, y, par, rank):
  x = Find(x, par)
  y = Find(y, par)
  
  if x != y:
    # rankの低い方を高い方につなげる
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
def Size(x, par):
  return -par[Find(x)]

#print(graph)
graph.sort()
par = [-1]*n
rank = [0]*n

cost = 0

for d, p, q in graph:
  if not Same(p, q, par):
    cost += d
    Unite(p, q, par, rank)

print(cost)

Submission status: Time Limit Exceeded

Solution code:
#D問題

#UnionFind(normal)
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        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
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

    
"""
実装例
ABC126E 1or2

#E問題
#UnionFind(normal) 
UFコードは省略
    
if __name__ == "__main__":
  
    N,M = map(int,input().split())
    uf = UnionFind(N+1)
    for i in range(M):
        X,Y,Z = map(int,input().split())
        if not uf.isSameGroup(X,Y):
            uf.Unite(X,Y)
    ans=0
    for j in uf.root[1:N+1]:
        if j < 0:
            ans+=1
    print(ans)
"""

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]


uf = UnionFind(N)
V = [i for i in range(N)]
ans = 0
while E:
    w,s,t = heapq.heappop(E)
    if not uf.isSameGroup(s,t):
        uf.Unite(s,t)
        ans+=w
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#D問題

#UnionFind(normal)
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        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
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

    
"""
実装例
ABC126E 1or2

#E問題
#UnionFind(normal) 
UFコードは省略
    
if __name__ == "__main__":
  
    N,M = map(int,input().split())
    uf = UnionFind(N+1)
    for i in range(M):
        X,Y,Z = map(int,input().split())
        if not uf.isSameGroup(X,Y):
            uf.Unite(X,Y)
    ans=0
    for j in uf.root[1:N+1]:
        if j < 0:
            ans+=1
    print(ans)
"""

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 in range(N-1):
    x0,x1,i0,i1 = XY0[i][0],XY0[i+1][0],XY0[i][2],XY0[i+1][2]
    dx = x1-x0
    heapq.heappush(E,[dx,i0,i1])
    y0,y1,i0,i1 = XY1[i][1],XY1[i+1][1],XY1[i][2],XY1[i+1][2]
    dy = y1-y0
    heapq.heappush(E,[dy,i0,i1])


uf = UnionFind(N)
V = [i for i in range(N)]
ans = 0
while E:
    w,s,t = heapq.heappop(E)
    if not uf.isSameGroup(s,t):
        uf.Unite(s,t)
        ans+=w
        
print(ans)

Submission status: Time Limit Exceeded

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

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])
for i in range(n-1):
    e[p[i][0]].append([abs(p[i+1][1]-p[i][1]),p[i+1][0]])
    e[p[i+1][0]].append([abs(p[i+1][1]-p[i][1]),p[i][0]])

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

def Prim(n,edge):
    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: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

#D
def root(x):
    if x == par[x]:
        return x
    par[x] = root(par[x])
    return par[x]

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

def unite(x,y):
    x = root(x)
    y = root(y)
    par[x] = y
    
n = I()
v = LIR(n)
l = [None for i in range(2*n-2)]
for i in range(n):
    v[i].append(i)
par = [i for i in range(n)]
v.sort(key = lambda x:x[0])
for i in range(n-1):
    l[i] = [v[i][2],v[i+1][2],v[i+1][0]-v[i][0]]
v.sort(key = lambda x:x[1])
for i in range(n-1):
    l[i+n-1] = [v[i][2],v[i+1][2],v[i+1][1]-v[i][1]]
l.sort(key = lambda x:x[2])
k = 0
ans = 0
for i in range(2*n-2):
    x,y,c = l[i]
    if not same(x,y):
        k += 1
        ans += c
        unite(x,y)
    if k == n-1:break
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Time Limit Exceeded

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
        par[x] = y
        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: Time Limit Exceeded

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

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)
        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 not same(p0, p1):
            unite(p0, p1)
            a += 1
            ans += value
    print(ans)
    return

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