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

Submission status: Time Limit Exceeded

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

#########################
n = int(input())
zahyo = []
for i in range(n):
    x,y = map(int,input().split())
    zahyo.append((x,y))
edge = [[] for i in range(n)]
#隣接リスト edge[i]:[コスト,行先]
for i in range(n-1):
    for j in range(i+1,n):
        c = min(abs(zahyo[i][0]-zahyo[j][0]),abs(zahyo[i][1]-zahyo[j][1]))
        edge[j].append((c,i))
        edge[i].append((c,j))
print(prim_heap())

Submission status: Time Limit Exceeded

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

#########################
n = int(input())
zahyo = []
for i in range(n):
    x,y = map(int,input().split())
    zahyo.append([x,y])
edge = [[] for i in range(n)]
#隣接リスト edge[i]:[コスト,行先]
for i in range(n-1):
    for j in range(i+1,n):
        c = min(abs(zahyo[i][0]-zahyo[j][0]),abs(zahyo[i][1]-zahyo[j][1]))
        edge[j].append([c,i])
        edge[i].append([c,j])
print(prim_heap())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
path = []

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

x_li = sorted(path)
y_li = sorted(path,key=lambda x:(x[1]))

inf = 10**18
cost = [[inf for i in range(n)]for j in range(n)]

for i in range(1,n):
    cost[x_li[i][2]][x_li[i-1][2]] = min(abs(x_li[i][0]-x_li[i-1][0]),abs(x_li[i][1]-x_li[i-1][1]))
    cost[x_li[i-1][2]][x_li[i][2]] = min(abs(x_li[i][0]-x_li[i-1][0]),abs(x_li[i][1]-x_li[i-1][1]))
    cost[y_li[i][2]][y_li[i-1][2]] = min(abs(y_li[i][0]-y_li[i-1][0]),abs(y_li[i][1]-y_li[i-1][1]))
    cost[y_li[i-1][2]][y_li[i][2]] = min(abs(y_li[i][0]-y_li[i-1][0]),abs(y_li[i][1]-y_li[i-1][1]))

def prim(n,cost):
    mincost = [float("inf")]*n
    used = [False] * n
    mincost[0] = 0
    res = 0   
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1 or mincost[i] < mincost[v]):
                v = i
        if v == -1:
            break
        used[v] = True
        res += mincost[v]
        for i in range(n):
            mincost[i] = min(mincost[i],cost[v][i])
    return res

print(prim(n,cost))

Submission status: Time Limit Exceeded

Solution code:
# atcoder problem solving

# Built?

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

edge = []

# x座標に関する辺の設定

d.sort(key=lambda x: x[1])

for i in range(N-1):
    a, px, py = d[i]
    b, qx, qy = d[i+1]
    dis = abs(px-qx)
    graph[a].append((dis, b))
    graph[b].append((dis, a))
    edge.append((dis, a, b))
    edge.append((dis, b, a))

# y座標に関する辺の設定

d.sort(key=lambda x: x[2])

for i in range(N-1):
    a, px, py = d[i]
    b, qx, qy = d[i+1]
    dis = abs(py-qy)
    graph[a].append((dis, b))
    graph[b].append((dis, a))
    edge.append((dis, a, b))
    edge.append((dis, b, a))


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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


# 最小全域木
def kruskal():
    res = 0
    G = UnionFind(N)
    edge.sort()
    for cost, p, q, in edge:
        if not G.same(p, q):
            G.union(p, q)
            res += cost
    return res


ans = kruskal()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# atcoder problem solving

# Built?

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

edge = []

# x座標に関する辺の設定

d.sort(key=lambda x: x[1])

for i in range(N-1):
    a, px, py = d[i]
    b, qx, qy = d[i+1]
    dis = abs(px-qx)
    graph[a].append((dis, b))
    graph[b].append((dis, a))
    edge.append((dis, a, b))
    edge.append((dis, b, a))

# y座標に関する辺の設定

d.sort(key=lambda x: x[2])

for i in range(N-1):
    a, px, py = d[i]
    b, qx, qy = d[i+1]
    dis = abs(py-qy)
    graph[a].append((dis, b))
    graph[b].append((dis, a))
    edge.append((dis, a, b))
    edge.append((dis, b, a))


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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


# 最小全域木（クラスかるほう）
def kruskal():
    res = 0
    G = UnionFind(N)
    edge.sort()
    for cost, p, q, in edge:
        if not G.same(p, q):
            G.union(p, q)
            res += cost
    return res


ans = kruskal()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N = int(input())
place = []
d = {}
j = 0
for i in range(N):
    x, y = map(int, input().split())
    place.append((x,y))
    if not (x,y) in d:
        d[(x,y)] = j
        j += 1
N = j

sort_x = sorted(place)
sort_y = sorted(place, key = lambda k:k[1])

edge=[[] for i in range(N)]
flag = False
for x,y in sort_x:
    now = d[(x,y)]
    if flag:
        edge[before].append([x-before_x,now])
        edge[now].append([x-before_x,d[(before_x,before_y)]])
    else:
        flag = True
    before_x = x
    before_y = y
    before = now

flag = False
for x,y in sort_y:
    now = d[(x,y)]
    if flag:
        edge[before].append([y-before_y,now])
        edge[now].append([y-before_y,before])
    else:
        flag = True
    before_x = x
    before_y = y
    before = now

used = [True]*N
edgelist = []
for e in edge[0]:
    heapq.heappush(edgelist,e)
used[0] = False
res = 0

while len(edgelist) != 0:
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]:
            continue
    v = minedge[1]
    used[v] = False
    for e in edge[v]:
        if used[e[1]]:
            heapq.heappush(edgelist,e)
    res += minedge[0]

print(res)

Submission status: Time Limit Exceeded

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

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

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
from heapq import *
N = int(input())
X = [0]*N
Y = [0]*N
for i in range(N):
    x, y = map(int, input().split())
    X[i] = [i+1, x]
    Y[i] = [i+1, y]
X = sorted(X, key = lambda x:x[1])
Y = sorted(Y, key = lambda x:x[1])
H = []
heapify(H)
UF = UnionFind(N)
for i in range(N-1):
    heappush(H, (X[i+1][1]-X[i][1], X[i+1][0], X[i][0]))
    heappush(H, (Y[i+1][1]-Y[i][1], Y[i+1][0], Y[i][0]))
ans = 0
while H:
    K = heappop(H)
    if not UF.same_check(K[1], K[2]):
        UF.union(K[1], K[2])
        ans += K[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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


ans = 0  
N = int(input())
xy_mat = [list(map(int, input().split())) for _ in range(N)]
UF = UnionFind(N)
xy_mat = np.array(xy_mat)
C_mat = []
for i in range(N):
    for j in range(N):
        C_mat.append([i, j, min(abs(xy_mat[i,1]-xy_mat[j,1]),abs(xy_mat[i,0]-xy_mat[j,0]))])


C_mat = np.array(C_mat)
C_mat_sort = C_mat[np.argsort(C_mat[:,2]),:]

for C in C_mat_sort:
    C = [int(i) for i in C]
    if not UF.same(C[0],C[1]):
        ans += C[2] 
        UF.union(C[0],C[1])
    if UF.group_count() == 1:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class UF:
    def __init__(self, N):
        self.state = [-1] * N
        self.rank = [0] * N
        self.num_group = N
    
    def get_parent(self, a):
        p = self.state[a]
        if p < 0:
            return a
        
        q = self.get_parent(p)
        self.state[a] = q
        return q

    def make_pair(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa == pb:
            return

        if self.rank[pa] > self.rank[pb]:
            pa, pb = pb, pa
            a, b = b, a
        elif self.rank[pa] == self.rank[pb]:
            self.rank[pb] += 1

        self.state[pb] += self.state[pa]
        self.state[pa] = pb
        self.state[a] = pb
        self.num_group -= 1
    
    def is_pair(self, a, b):
        return self.get_parent(a) == self.get_parent(b)

    def get_size(self, a):
        return -self.state[self.get_parent(a)]


def main():
    N = int(input())
    X = []
    Y = []
    for i in range(N):
        a, b = read_values()
        X.append((a, i))
        Y.append((b, i))
    
    X.sort()
    Y.sort()

    Q = []
    for i in range(N - 1):
        heapq.heappush(Q, (X[i + 1][0] - X[i][0], (X[i][1], X[i + 1][1])))
        heapq.heappush(Q, (Y[i + 1][0] - Y[i][0], (Y[i][1], Y[i + 1][1])))

    res = 0
    uf = UF(N)
    while uf.num_group != 1:
        c, (a, b) = heapq.heappop(Q)

        if not uf.is_pair(a, b):
            res += c
            uf.make_pair(a, b)

    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Xs = []
Ys = []
for i in range(N):
    x, y = map(int, input().split())
    Xs.append((x, i))
    Ys.append((y, i))
Xs.sort()
Ys.sort()
Edges = []
for i in range(1, N):
    (x1, v1), (x2, v2) = Xs[i-1], Xs[i]
    Edges.append((abs(x1-x2), v1, v2))
    (y1, v1), (y2, v2) = Ys[i-1], Ys[i]
    Edges.append((abs(y1-y2), v1, v2))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

import heapq
heapq.heapify(Edges)
uf = UnionFind(N)
ans = 0
while Edges:
    d, a, b = heapq.heappop(Edges)
    if not uf.same(a, b):
        ans += d
        uf.union(a, b)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[0]*N,[0]*N
dx,dy={},{}
for i in range(N):
    X[i],Y[i]=map(int,input().split())
    if X[i] in dx:
        dx[X[i]].append(i)
    else:
        dx[X[i]]=[i]
    if Y[i] in dy:
        dy[Y[i]].append(i)
    else:
        dy[Y[i]]=[i]
ux,uy=list(set(X)),list(set(Y))
ux.sort()
uy.sort()
uxi={x:i for i,x in enumerate(ux)}
uyi={y:i for i,y in enumerate(uy)}
edge=[[] for i in range(N)]
for i,(x,y) in enumerate(zip(X,Y)):
    for index in dx[x]+dy[y]:
        if index!=i:
            edge[i].append((0,index))
    if uxi[x]>=1:
        nx=ux[uxi[x]-1]
        for index in dx[nx]:
            if index!=i:
                edge[i].append((abs(nx-x),index))
                edge[index].append((abs(nx-x),i))
    if uyi[y]>=1:
        ny=uy[uyi[y]-1]
        for index in dy[ny]:
            if index!=i:
                edge[i].append((abs(ny-y),index))
                edge[index].append((abs(ny-y),i))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[0]*N,[0]*N
dx,dy={},{}
for i in range(N):
    X[i],Y[i]=map(int,input().split())
    if X[i] in dx:
        dx[X[i]].append(i)
    else:
        dx[X[i]]=[i]
    if Y[i] in dy:
        dy[Y[i]].append(i)
    else:
        dy[Y[i]]=[i]
ux,uy=list(set(X)),list(set(Y))
ux.sort()
uy.sort()
uxi={x:i for i,x in enumerate(ux)}
uyi={y:i for i,y in enumerate(uy)}
edge=[[] for i in range(N)]
for i,(x,y) in enumerate(zip(X,Y)):
    for index in dx[x]+dy[y]:
        edge[i].append((0,index))
    if uxi[x]>=1:
        nx=ux[uxi[x]-1]
        for index in dx[nx]:
            if index!=i:
                edge[i].append((abs(nx-x),index))
                edge[index].append((abs(nx-x),i))
    if uyi[y]>=1:
        ny=uy[uyi[y]-1]
        for index in dy[ny]:
            if index!=i:
                edge[i].append((abs(ny-y),index))
                edge[index].append((abs(ny-y),i))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[0]*N,[0]*N
dx,dy={},{}
for i in range(N):
    X[i],Y[i]=map(int,input().split())
    if X[i] in dx:
        dx[X[i]].append(i)
    else:
        dx[X[i]]=[i]
    if Y[i] in dy:
        dy[Y[i]].append(i)
    else:
        dy[Y[i]]=[i]
ux,uy=list(set(X)),list(set(Y))
ux.sort()
uy.sort()
uxi={x:i for i,x in enumerate(ux)}
uyi={y:i for i,y in enumerate(uy)}
edge=[[] for i in range(N)]
for i,(x,y) in enumerate(zip(X,Y)):
    for index in dx[x]+dy[y]:
        edge[i].append((0,index))
    if uxi[x]>=1:
        nx=ux[uxi[x]-1]
        for index in dx[nx]:
            if index!=i:
                edge[i].append((abs(nx-x),index))
    if uxi[x]<len(ux)-1:
        nx=ux[uxi[x]+1]
        for index in dx[nx]:
            if index!=i:
                edge[i].append((abs(nx-x),index))
    if uyi[y]>=1:
        ny=uy[uyi[y]-1]
        for index in dy[ny]:
            if index!=i:
                edge[i].append((abs(ny-y),index))
    if uyi[y]<len(uy)-1:
        ny=uy[uyi[y]+1]
        for index in dy[ny]:
            if index!=i:
                edge[i].append((abs(ny-y),index))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[0]*N,[0]*N
dx,dy=defaultdict(list),defaultdict(list)
for i in range(N):
    X[i],Y[i]=map(int,input().split())
    dx[X[i]].append(i)
    dy[Y[i]].append(i)
ux,uy=list(set(X)),list(set(Y))
ux.sort()
uy.sort()
uxi={x:i for i,x in enumerate(ux)}
uyi={y:i for i,y in enumerate(uy)}
edge=[[] for i in range(N)]
for i,(x,y) in enumerate(zip(X,Y)):
    for index in dx[x]+dy[y]:
        edge[i].append((0,index))
    if uxi[x]>=1:
        nx=ux[uxi[x]-1]
        for index in dx[nx]:
            if index!=i:
                edge[i].append((abs(nx-x),index))
    if uxi[x]<len(ux)-1:
        nx=ux[uxi[x]+1]
        for index in dx[nx]:
            if index!=i:
                edge[i].append((abs(nx-x),index))
    if uyi[y]>=1:
        ny=uy[uyi[y]-1]
        for index in dy[ny]:
            if index!=i:
                edge[i].append((abs(ny-y),index))
    if uyi[y]<len(uy)-1:
        ny=uy[uyi[y]+1]
        for index in dy[ny]:
            if index!=i:
                edge[i].append((abs(ny-y),index))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[0]*N,[0]*N
dx,dy=defaultdict(list),defaultdict(list)
for i in range(N):
    X[i],Y[i]=map(int,input().split())
    dx[X[i]].append(i)
    dy[Y[i]].append(i)
ux,uy=list(set(X)),list(set(Y))
ux.sort()
uy.sort()
uxi={x:i for i,x in enumerate(ux)}
uyi={y:i for i,y in enumerate(uy)}
edge=[[] for i in range(N)]
for i,(x,y) in enumerate(zip(X,Y)):
    for index in dx[x]+dy[y]:
        edge[i].append((0,index))
    if uxi[x]>=1:
        for index in dx[ux[uxi[x]-1]]:
            if index!=i:
                edge[i].append((abs(ux[uxi[x]-1]-x),index))
    if uxi[x]<len(ux)-1:
        for index in dx[ux[uxi[x]+1]]:
            if index!=i:
                edge[i].append((abs(ux[uxi[x]+1]-x),index))
    if uyi[y]>=1:
        for index in dy[uy[uyi[y]-1]]:
            if index!=i:
                edge[i].append((abs(uy[uyi[y]-1]-y),index))
    if uyi[y]<len(uy)-1:
        for index in dy[uy[uyi[y]+1]]:
            if index!=i:
                edge[i].append((abs(uy[uyi[y]+1]-y),index))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[0]*N,[0]*N
dx,dy=defaultdict(list),defaultdict(list)
for i in range(N):
    X[i],Y[i]=map(int,input().split())
    dx[X[i]].append(i)
    dy[Y[i]].append(i)
ux,uy=list(set(X)),list(set(Y))
ux.sort()
uy.sort()
uxi={x:i for i,x in enumerate(ux)}
uyi={y:i for i,y in enumerate(uy)}
edge=[[] for i in range(N)]
for i,(x,y) in enumerate(zip(X,Y)):
    for index in dx[x]+dy[y]:
        edge[i].append((0,index))
    if uxi[x]>=1:
        for index in dx[ux[uxi[x]-1]]:
            edge[i].append((abs(ux[uxi[x]-1]-x),index))
    if uxi[x]<len(ux)-1:
        for index in dx[ux[uxi[x]+1]]:
            edge[i].append((abs(ux[uxi[x]+1]-x),index))
    if uyi[y]>=1:
        for index in dy[uy[uyi[y]-1]]:
            edge[i].append((abs(uy[uyi[y]-1]-y),index))
    if uyi[y]<len(uy)-1:
        for index in dy[uy[uyi[y]+1]]:
            edge[i].append((abs(uy[uyi[y]+1]-y),index))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))

Submission status: Time Limit Exceeded

Solution code:
import heapq

def prim_heap(N, edge):
    used = [False] * N
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist, e)
    used[0] = True
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heapq.heappush(edgelist, e)
        res += minedge[0]
    return res

N = int(input())

x_list = []
y_list = []

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

    x_list.append([x, i])
    y_list.append([y, i])

x_list.sort()
y_list.sort()

edge = [[] for _ in range(N)]
 
for i in range(1, N):
    x_dif = x_list[i][0] - x_list[i-1][0]
    y_dif = y_list[i][0] - y_list[i-1][0]

    edge[x_list[i][1]].append([x_dif, x_list[i-1][1]])
    edge[x_list[i-1][1]].append([x_dif, x_list[i][1]])
    edge[y_list[i][1]].append([y_dif, y_list[i-1][1]])
    edge[y_list[i-1][1]].append([y_dif, y_list[i][1]])

print(prim_heap(N, edge))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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


n = int(input())
graphx = []
graphy = []

for i in range(n):
    x,y = map(int,input().split())
    graphx.append([x,y,i])
    graphy.append([x,y,i])
graphx = sorted(graphx, key=lambda x:x[0])
graphy = sorted(graphy, key=lambda x:x[1])
graph = []

def S(G):
    for k in range(n-1):
        i,j = G[k][2], G[k+1][2]
        x0,y0,x1,y1 = G[k][0],G[k][1],G[k+1][0],G[k+1][1]
        m = min(abs(x0-x1),abs(y0-y1))
        graph.append([m,i,j])


S(graphx)
S(graphy)

graph.sort()
#print(graph)

ans = 0
uf = UnionFind(n)
for l in graph:
    if not uf.same(l[1],l[2]):
        ans += l[0]
        uf.union(l[1],l[2])
    if uf.group_count() == 1:
        print(ans)
        quit()