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:
from bisect import bisect_left,bisect_right
def find(i):
    j = i
    while j!=T[j][0]:
        j = T[j][0]
    T[i][0] = j
    return j
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        T[rt0][1] += T[rt1][1]
        return rt0
    else:
        T[rt0][0] = rt1
        T[rt1][1] += T[rt0][1]
        return rt1
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
distX = [[] for _ in range(N)]
for i in range(N):
    a = X[i][0]
    ind0 = bisect_left(A,(a,0))
    if ind0>0:
        d = A[ind0][0]-A[ind0-1][0]
        indx = A[ind0-1][1]
        distX[i].append((d,indx))
    ind1 = bisect_right(A,(a,N))
    if ind1<N:
        d = A[ind1][0]-A[ind1-1][0]
        indx = A[ind1][1]
        distX[i].append((d,indx))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
for i in range(N):
    b = X[i][1]
    ind0 = bisect_left(B,(b,0))
    if ind0>0:
        d = B[ind0][0]-B[ind0-1][0]
        indx = B[ind0-1][1]
        distY[i].append((d,indx))
    ind1 = bisect_right(B,(b,N))
    if ind1<N:
        d = B[ind1][0]-B[ind1-1][0]
        indx = B[ind1][1]
        distY[i].append((d,indx))
T = {i:[i,1] for i in range(N)}
for j in range(1,N):
    if A[j][0]==A[j-1][0]:
        union(find(A[j][1]),find(A[j-1][1]))
        find(A[j][1])
for j in range(1,N):
    if B[j][0]==B[j-1][0]:
        rt = find(B[j-1][1])
        rt0 = find(B[j][1])
        if rt!=rt0:
            union(rt,rt0)
            find(B[j][1])
            find(B[j-1][1])
D = []
for i in range(N):
    for d,j in distX[i]:
        D.append((d,i,j))
    for d,j in distY[i]:
        D.append((d,i,j))
D = sorted(D,key=lambda x:x[0])
cnt = 0
for d,i,j in D:
    rt = find(i)
    rt0 = find(j)
    if rt!= rt0:
        cnt += d
        union(rt,rt0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect_right
def find(i):
    j = i
    while j!=T[j][0]:
        j = T[j][0]
    T[i][0] = j
    return j
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        T[rt0][1] += T[rt1][1]
        return rt0
    else:
        T[rt0][0] = rt1
        T[rt1][1] += T[rt0][1]
        return rt1
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
distX = [[] for _ in range(N)]
for i in range(N):
    a = X[i][0]
    ind0 = bisect_left(A,(a,0))
    if ind0>0:
        d = A[ind0][0]-A[ind0-1][0]
        indx = A[ind0-1][1]
        distX[i].append((d,indx))
    ind1 = bisect_right(A,(a,N))
    if ind1<N:
        d = A[ind1][0]-A[ind1-1][0]
        indx = A[ind1][1]
        distX[i].append((d,indx))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
for i in range(N):
    b = X[i][1]
    ind0 = bisect_left(B,(b,0))
    if ind0>0:
        d = B[ind0][0]-B[ind0-1][0]
        indx = B[ind0-1][1]
        distY[i].append((d,indx))
    ind1 = bisect_right(B,(b,N))
    if ind1<N:
        d = B[ind1][0]-B[ind1-1][0]
        indx = B[ind1][1]
        distY[i].append((d,indx))
T = {i:[i,1] for i in range(N)}
for j in range(1,N):
    if A[j][0]==A[j-1][0]:
        union(find(A[j][1]),find(A[j-1][1]))
    find(A[j][1])
for j in range(1,N):
    if B[j][0]==B[j-1][0]:
        rt = find(B[j-1][1])
        rt0 = find(B[j][1])
        if rt!=rt0:
            union(rt,rt0)
        find(B[j][1])
        find(B[j-1][1])
D = []
for i in range(N):
    for d,j in distX[i]:
        D.append((d,i,j))
    for d,j in distY[i]:
        D.append((d,i,j))
D = sorted(D,key=lambda x:x[0])
cnt = 0
for d,i,j in D:
    rt = find(i)
    rt0 = find(j)
    if rt!= rt0:
        cnt += d
        union(rt,rt0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect_right
def find(i):
    j = i
    while j!=T[j][0]:
        j = T[j][0]
    T[i][0] = j
    return j
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        T[rt0][1] += T[rt1][1]
        return rt0
    else:
        T[rt0][0] = rt1
        T[rt1][1] += T[rt0][1]
        return rt1
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
distX = [[] for _ in range(N)]
for i in range(N):
    a = X[i][0]
    ind0 = bisect_left(A,(a,0))
    if ind0>0:
        d = A[ind0][0]-A[ind0-1][0]
        indx = A[ind0-1][1]
        distX[i].append((d,indx))
    ind1 = bisect_right(A,(a,N))
    if ind1<N:
        d = A[ind1][0]-A[ind1-1][0]
        indx = A[ind1][1]
        distX[i].append((d,indx))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
for i in range(N):
    b = X[i][1]
    ind0 = bisect_left(B,(b,0))
    if ind0>0:
        d = B[ind0][0]-B[ind0-1][0]
        indx = B[ind0-1][1]
        distY[i].append((d,indx))
    ind1 = bisect_right(B,(b,N))
    if ind1<N:
        d = B[ind1][0]-B[ind1-1][0]
        indx = B[ind1][1]
        distY[i].append((d,indx))
T = {i:[i,1] for i in range(N)}
for j in range(1,N):
    if A[j][0]==A[j-1][0]:
        union(find(A[j][1]),find(A[j-1][1]))
for i in range(N):
    find(i)
for j in range(1,N):
    if B[j][0]==B[j-1][0]:
        rt = find(B[j-1][1])
        rt0 = find(B[j][1])
        if rt!=rt0:
            union(rt,rt0)
D = []
for i in range(N):
    for d,j in distX[i]:
        D.append((d,i,j))
    for d,j in distY[i]:
        D.append((d,i,j))
D = sorted(D,key=lambda x:x[0])
cnt = 0
for d,i,j in D:
    rt = find(i)
    rt0 = find(j)
    if rt!= rt0:
        cnt += d
        union(rt,rt0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect_right
def find(i):
    j = i
    while j!=T[j][0]:
        j = T[j][0]
    T[i][0] = j
    return j
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        T[rt0][1] += T[rt1][1]
        return rt0
    else:
        T[rt0][0] = rt1
        T[rt1][1] += T[rt0][1]
        return rt1
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
distX = [[] for _ in range(N)]
for i in range(N):
    a = X[i][0]
    ind0 = bisect_left(A,(a,0))
    if ind0>0:
        d = A[ind0][0]-A[ind0-1][0]
        indx = A[ind0-1][1]
        distX[i].append((d,indx))
    ind1 = bisect_right(A,(a,N))
    if ind1<N:
        d = A[ind1][0]-A[ind1-1][0]
        indx = A[ind1][1]
        distX[i].append((d,indx))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
for i in range(N):
    b = X[i][1]
    ind0 = bisect_left(B,(b,0))
    if ind0>0:
        d = B[ind0][0]-B[ind0-1][0]
        indx = B[ind0-1][1]
        distY[i].append((d,indx))
    ind1 = bisect_right(B,(b,N))
    if ind1<N:
        d = B[ind1][0]-B[ind1-1][0]
        indx = B[ind1][1]
        distY[i].append((d,indx))
T = {i:[i,1] for i in range(N)}
for j in range(1,N):
    if A[j][0]==A[j-1][0]:
        rt = find(A[j-1][1])
        T[A[j][1]][0] = rt
        T[rt][1] += 1
for j in range(1,N):
    if B[j][0]==B[j-1][0]:
        rt = find(B[j-1][1])
        rt0 = find(B[j][1])
        if rt!=rt0:
            union(rt,rt0)
D = []
for i in range(N):
    for d,j in distX[i]:
        D.append((d,i,j))
    for d,j in distY[i]:
        D.append((d,i,j))
D = sorted(D,key=lambda x:x[0])
cnt = 0
for d,i,j in D:
    rt = find(i)
    rt0 = find(j)
    if rt!= rt0:
        cnt += d
        union(rt,rt0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect_right
def find(i):
    while i!=T[i][0]:
        i = T[i][0]
    return i
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        T[rt0][1] += T[rt1][1]
        return rt0
    else:
        T[rt0][0] = rt1
        T[rt1][1] += T[rt0][1]
        return rt1
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
distX = [[] for _ in range(N)]
for i in range(N):
    a = X[i][0]
    ind0 = bisect_left(A,(a,0))
    if ind0>0:
        d = A[ind0][0]-A[ind0-1][0]
        indx = A[ind0-1][1]
        distX[i].append((d,indx))
    ind1 = bisect_right(A,(a,N))
    if ind1<N:
        d = A[ind1][0]-A[ind1-1][0]
        indx = A[ind1][1]
        distX[i].append((d,indx))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
for i in range(N):
    b = X[i][1]
    ind0 = bisect_left(B,(b,0))
    if ind0>0:
        d = B[ind0][0]-B[ind0-1][0]
        indx = B[ind0-1][1]
        distY[i].append((d,indx))
    ind1 = bisect_right(B,(b,N))
    if ind1<N:
        d = B[ind1][0]-B[ind1-1][0]
        indx = B[ind1][1]
        distY[i].append((d,indx))
T = {i:[i,1] for i in range(N)}
hist = [0 for _ in range(N)]
for i in range(N):
    if hist[i]==1:continue
    a = X[i][0]
    ind0 = bisect_left(A,(a,0))
    ind1 = bisect_right(A,(a,N))
    rt = A[ind0][1]
    hist[rt] = 1
    j = ind0+1
    while j<ind1:
        hist[A[j][1]] = 1
        rt0 = find(A[j][1])
        rt = union(rt,rt0)
        j += 1
hist = [0 for _ in range(N)]
for i in range(N):
    if hist[i]==1:continue
    b = X[i][1]
    ind0 = bisect_left(B,(b,0))
    ind1 = bisect_right(B,(b,N))
    hist[B[ind0][1]] = 1
    rt = find(B[ind0][1])
    j = ind0+1
    while j<ind1:
        hist[B[j][1]] = 1
        rt0 = find(B[j][1])
        if rt==rt0:
            j += 1
        else:
            rt = union(rt,rt0)
            j += 1
G = {}
for i in range(N):
    x = find(i)
    if x not in G:
        G[x] = []
    G[x].append(i)
D = []
for i in range(N):
    for d,j in distX[i]:
        D.append((d,i,j))
    for d,j in distY[i]:
        D.append((d,i,j))
D = sorted(D,key=lambda x:x[0])
cnt = 0
for d,i,j in D:
    rt = find(i)
    rt0 = find(j)
    if rt!= rt0:
        cnt += d
        union(rt,rt0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from operator import itemgetter

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for _ in range(n)]

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

    def root(self, x):
        if self.par[x]<0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:
            return

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

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

    def size(self,x):
        return -self.par[self.root(x)]

def kruskal(e,n):
    l = []
    for v in range(n):
        for u,c in e[v]:
            l.append((c,v,u))
    l.sort()

    uf = UnionFind(n)
    cost = 0
    res = []
    for c,v,u in l:
        if uf.same(v,u):
            continue
        res.append((v,u,c))
        cost += c
        uf.unite(v,u)
    return res,cost


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

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

ixy.sort(key=itemgetter(1,2))
for i in range(n-1):
    v,a,b = ixy[i]
    u,c,d = ixy[i+1]
    e[v].append((u,min(abs(a-c),abs(b-d))))
    e[u].append((v,min(abs(a-c),abs(b-d))))

ixy.sort(key=itemgetter(2,1))
for i in range(n-1):
    v,a,b = ixy[i]
    u,c,d = ixy[i+1]
    e[v].append((u,min(abs(a-c),abs(b-d))))
    e[u].append((v,min(abs(a-c),abs(b-d))))

r,cost = kruskal(e,n)
print(cost)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect_right
import heapq
def find(i):
    while i!=T[i][0]:
        i = T[i][0]
    return i
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        T[rt0][1] += T[rt1][1]
        return rt0
    else:
        T[rt0][0] = rt1
        T[rt1][1] += T[rt0][1]
        return rt1
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
distX = [[] for _ in range(N)]
for i in range(N):
    a = X[i][0]
    ind0 = bisect_left(A,(a,0))
    if ind0>0:
        d = A[ind0][0]-A[ind0-1][0]
        indx = A[ind0-1][1]
        distX[i].append((d,indx))
    ind1 = bisect_right(A,(a,N))
    if ind1<N:
        d = A[ind1][0]-A[ind1-1][0]
        indx = A[ind1][1]
        distX[i].append((d,indx))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
for i in range(N):
    b = X[i][1]
    ind0 = bisect_left(B,(b,0))
    if ind0>0:
        d = B[ind0][0]-B[ind0-1][0]
        indx = B[ind0-1][1]
        distY[i].append((d,indx))
    ind1 = bisect_right(B,(b,N))
    if ind1<N:
        d = B[ind1][0]-B[ind1-1][0]
        indx = B[ind1][1]
        distY[i].append((d,indx))
T = {i:[i,1] for i in range(N)}
hist = [0 for _ in range(N)]
for i in range(N):
    if hist[i]==1:continue
    a = X[i][0]
    ind0 = bisect_left(A,(a,0))
    ind1 = bisect_right(A,(a,N))
    rt = A[ind0][1]
    hist[rt] = 1
    j = ind0+1
    while j<ind1:
        hist[A[j][1]] = 1
        rt0 = find(A[j][1])
        rt = union(rt,rt0)
        j += 1
hist = [0 for _ in range(N)]
for i in range(N):
    if hist[i]==1:continue
    b = X[i][1]
    ind0 = bisect_left(B,(b,0))
    ind1 = bisect_right(B,(b,N))
    hist[B[ind0][1]] = 1
    rt = find(B[ind0][1])
    j = ind0+1
    while j<ind1:
        hist[B[j][1]] = 1
        rt0 = find(B[j][1])
        if rt==rt0:
            j += 1
        else:
            rt = union(rt,rt0)
            j += 1
G = {}
for i in range(N):
    x = find(i)
    if x not in G:
        G[x] = []
    G[x].append(i)
rt = find(0)
heap = [(0,rt)]
hist = {g:0 for g in G}
cnt = 0
while heap:
    d,x = heapq.heappop(heap)
    rt0 = find(x)
    if hist[rt0]==1:continue
    hist[rt0] = 1
    cnt += d
    for y in G[rt0]:
        for z in distX[y]:
            heapq.heappush(heap,z)
        for z in distY[y]:
            heapq.heappush(heap,z)
    if rt!=rt0:
        rt = union(rt,rt0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect_right
import heapq
def find(i):
    while i!=T[i][0]:
        i = T[i][0]
    return i
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        T[rt0][1] += T[rt1][1]
        return rt0
    else:
        T[rt0][0] = rt1
        T[rt1][1] += T[rt0][1]
        return rt1
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
distX = [[] for _ in range(N)]
for i in range(N):
    a = X[i][0]
    ind0 = bisect_left(A,(a,0))
    if ind0>0:
        d = A[ind0][0]-A[ind0-1][0]
        indx = A[ind0-1][1]
        distX[i].append((d,indx))
    ind1 = bisect_right(A,(a,N))
    if ind1<N:
        d = A[ind1][0]-A[ind1-1][0]
        indx = A[ind1][1]
        distX[i].append((d,indx))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
for i in range(N):
    b = X[i][1]
    ind0 = bisect_left(B,(b,0))
    if ind0>0:
        d = B[ind0][0]-B[ind0-1][0]
        indx = B[ind0-1][1]
        distY[i].append((d,indx))
    ind1 = bisect_right(B,(b,N))
    if ind1<N:
        d = B[ind1][0]-B[ind1-1][0]
        indx = B[ind1][1]
        distY[i].append((d,indx))
T = {i:[i,1] for i in range(N)}
hist = [0 for _ in range(N)]
for i in range(N):
    if hist[i]==1:continue
    a = X[i][0]
    ind0 = bisect_left(A,(a,0))
    ind1 = bisect_right(A,(a,N))
    rt = A[ind0][1]
    hist[rt] = 1
    j = ind0+1
    while j<ind1:
        rt0 = find(A[j][1])
        hist[A[j][1]] = 1
        rt = union(rt,rt0)
        j += 1
hist = [0 for _ in range(N)]
for i in range(N):
    if hist[i]==1:continue
    b = X[i][1]
    ind0 = bisect_left(B,(b,0))
    ind1 = bisect_right(B,(b,N))
    hist[B[ind0][1]] = 1
    rt = find(B[ind0][1])
    j = ind0+1
    while j<ind1:
        hist[B[j][1]] = 1
        rt0 = find(B[j][1])
        if rt==rt0:
            j += 1
        else:
            rt = union(rt,rt0)
            j += 1
G = {}
for i in range(N):
    x = find(i)
    if x not in G:
        G[x] = []
    G[x].append(i)
rt = find(0)
heap = [(0,rt)]
hist = {g:0 for g in G}
cnt = 0
while heap:
    d,x = heapq.heappop(heap)
    rt0 = find(x)
    if hist[rt0]==1:continue
    hist[rt0] = 1
    cnt += d
    for y in G[rt0]:
        for z in distX[y]:
            heapq.heappush(heap,z)
        for z in distY[y]:
            heapq.heappush(heap,z)
    if rt!=rt0:
        rt = union(rt,rt0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#最小領域木
#ABC065D - Built?
#https://atcoder.jp/contests/abc065/tasks/arc076_b

#自己考察

n = int(input())
lst = [list(map(int,input().split())) for _ in range(n)]
cad = []

for i in range(n):
    for j in range(i,n):
        tmp = min(abs(lst[i][0]-lst[j][0]),abs(lst[i][1]-lst[j][1]))
        cad.append([tmp,i,j])
        
cad.sort()

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

h = UnionFind(n)
cost = 0
for i in range(len(cad)):
    a = cad[i][1]
    b = cad[i][2]
    c = cad[i][0]
    if  not h.same(a,b):
        h.union(a,b)
        cost += c

print(cost)

Submission status: Time Limit Exceeded

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

# 最小全域木
# プリム法 #
# 部分木から、最小コストの辺を貪欲に追加

# Kruskal法 #
# クラスカル法 #
# 辺でソートして、最小コストの辺から、ループにならないよう貪欲に追加
# UnionFindを使う


N = int(input())

# x,yでそれぞれソート
POINT_x = []
POINT_y = []
for _ in range(N):
    x, y = map(int, input().split())
    POINT_x.append((x, y))
    POINT_y.append((x, y))

POINT_x = sorted(POINT_x, key=lambda x: x[0])
POINT_y = sorted(POINT_y, key=lambda x: x[1])

EDGE = defaultdict(list)
for i in range(N):
    p = POINT_x[i]

    if i != 0:
        prev = POINT_x[i-1]
        EDGE[p].append((abs(p[0]-prev[0]), prev))

    if i != N-1:
        nxt = POINT_x[i+1]
        EDGE[p].append((abs(p[0]-nxt[0]), nxt))

for i in range(N):
    p = POINT_y[i]

    if i != 0:
        prev = POINT_y[i-1]
        EDGE[p].append((abs(p[1]-prev[1]), prev))

    if i != N-1:
        nxt = POINT_y[i+1]
        EDGE[p].append((abs(p[1]-nxt[1]), nxt))


INF = 10 ** 12
mincost = [INF] * N
used = defaultdict(lambda: False)

point = POINT_x[0]
used[point] = True
q = []
ans = 0

for e in EDGE[point]:
    heapq.heappush(q, e)

while(True):
    update = False
    for _ in range(len(q)):
        cost, point = heapq.heappop(q)
        if used[point]:
            continue

        update = True
        ans += cost
        used[point] = True

        for e in EDGE[point]:
            heapq.heappush(q, e)

    if not update:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)
from collections import defaultdict
# d = defaultdict(list)

from itertools import combinations
# comb = combinations(range(N), 2)

from functools import reduce
from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.N = n
        self.parent = list(range(n))
        self.rank = [1 for _ in range(n)]

    def findRoot(self, i):
        if self.parent[i] == i:  # 親が自分ならroot
            return i
        else:
            self.parent[i] = self.findRoot(self.parent[i])  # 親をrootに付け替える
            return self.parent[i]

    def unite(self, i, j):
        i_root = self.findRoot(i)
        j_root = self.findRoot(j)
        if i_root == j_root:
            return

        if self.rank[i_root] > self.rank[j_root]:  # ランクが高い方を親にする。
            self.parent[j_root] = i_root
        elif self.rank[i_root] == self.rank[j_root]:
            self.parent[j_root] = i_root
            self.rank[i_root] += 1
        else:
            self.parent[i_root] = j_root

        return i

    def isSame(self, i, j):
        return self.findRoot(i) == self.findRoot(j)

    def setGroup(self, elements):
        reduce(self.unite, elements)

    def getElementCount(self):  # 要素ごとにそれが属してる集合の要素数を取る
        roots = [self.findRoot(i) for i in range(self.N)]
        counts = Counter(roots)
        return [counts[r] for r in roots]

    def getRootCount(self):  # ルートごとにそれが属してる集合の要素数を取る
        roots = [self.findRoot(i) for i in range(self.N)]
        counts = Counter(roots)
        return counts


def resolve():
    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    grid = [[int(x) for x in sys.stdin.readline().split()] + [i]
            for i in range(N)]  # int grid

    logger.debug('{}'.format([]))

    edge_list = []
    # x でソート
    grid = sorted(grid, key=lambda xy: xy[0])
    for i in range(N - 1):
        xi, yi, vi = grid[i]
        xj, yj, vj = grid[i + 1]
        edge_list.append((min(abs(xi - xj), abs(yi - yj)), vi, vj))

    # y でソート
    grid = sorted(grid, key=lambda xy: xy[1])

    for i, j in combinations(range(N), 2):
        xi, yi, vi = grid[i]
        xj, yj, vj = grid[i + 1]
        edge_list.append((min(abs(xi - xj), abs(yi - yj)), vi, vj))

    edge_list = sorted(edge_list)

    union_find = UnionFind(N)

    total_cost = 0
    for edge in edge_list:
        cost, i, j = edge
        if not union_find.isSame(i, j):
            union_find.unite(i, j)
            total_cost += cost

    print(total_cost)


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1 5
3 9
7 8"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """6
8 3
4 9
12 19
18 1
13 5
7 6"""
        output = """8"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2
0 0
0 0"""
        output = """0"""
        self.assertIO(input, output)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)
from collections import defaultdict
# d = defaultdict(list)

from itertools import combinations
# comb = combinations(range(N), 2)

from functools import reduce
from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.N = n
        self.parent = list(range(n))
        self.rank = [1 for _ in range(n)]

    def findRoot(self, i):
        if self.parent[i] == i:  # 親が自分ならroot
            return i
        else:
            self.parent[i] = self.findRoot(self.parent[i])  # 親をrootに付け替える
            return self.parent[i]

    def unite(self, i, j):
        i_root = self.findRoot(i)
        j_root = self.findRoot(j)
        if i_root == j_root:
            return

        if self.rank[i_root] > self.rank[j_root]:  # ランクが高い方を親にする。
            self.parent[j_root] = i_root
        elif self.rank[i_root] == self.rank[j_root]:
            self.parent[j_root] = i_root
            self.rank[i_root] += 1
        else:
            self.parent[i_root] = j_root

        return i

    def isSame(self, i, j):
        return self.findRoot(i) == self.findRoot(j)

    def setGroup(self, elements):
        reduce(self.unite, elements)

    def getElementCount(self):  # 要素ごとにそれが属してる集合の要素数を取る
        roots = [self.findRoot(i) for i in range(self.N)]
        counts = Counter(roots)
        return [counts[r] for r in roots]

    def getRootCount(self):  # ルートごとにそれが属してる集合の要素数を取る
        roots = [self.findRoot(i) for i in range(self.N)]
        counts = Counter(roots)
        return counts


def resolve():
    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    grid = [[int(x) for x in sys.stdin.readline().split()]
            for _ in range(N)]  # int grid

    logger.debug('{}'.format([]))

    edge_list = []
    for i, j in combinations(range(N), 2):
        xi, yi = grid[i]
        xj, yj = grid[j]
        edge_list.append((min(abs(xi - xj), abs(yi - yj)), i, j))

    edge_list = sorted(edge_list)

    union_find = UnionFind(N)

    total_cost = 0
    for edge in edge_list:
        cost, i, j = edge
        if not union_find.isSame(i, j):
            union_find.unite(i, j)
            total_cost += cost

    print(total_cost)


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1 5
3 9
7 8"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """6
8 3
4 9
12 19
18 1
13 5
7 6"""
        output = """8"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2
0 0
0 0"""
        output = """0"""
        self.assertIO(input, output)

Submission status: Time Limit Exceeded

Solution code:
# D - Built?

class UnionFind(object):
    def __init__(self, n=1):
        self.root = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find_root(self, x):
        if self.root[x] == x:
            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:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.root[y] = x

    def is_same_root(self, x, y):
        return self.find_root(x) == self.find_root(y)

# edges : [[start, end, edge_weight], ...]
def kruskal(max_v, edges):
    uf = UnionFind(max_v)
    edges_of_kruskal = []
    edges.sort(key = lambda x: x[2])
    for e in edges:
        if not uf.is_same_root(e[0], e[1]):
            uf.unite(e[0], e[1])
            edges_of_kruskal.append(e)
    return edges_of_kruskal


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

edges = []
xyi.sort(key = lambda x:x[0])
for j in range(N):
    if 0 < j:
        edges.append([xyi[j-1][2], xyi[j][2], xyi[j][0]-xyi[j-1][0]])
    if j < N-1:
        edges.append([xyi[j][2], xyi[j+1][2], xyi[j+1][0]-xyi[j][0]])

xyi.sort(key=lambda x: x[1])
for j in range(N):
    if 0 < j:
        edges.append([xyi[j-1][2], xyi[j][2], xyi[j][1]-xyi[j-1][1]])
    if j < N-1:
        edges.append([xyi[j][2], xyi[j+1][2], xyi[j+1][1]-xyi[j][1]])

edges = kruskal(N, edges)
print(sum([edges[x][2] for x in range(len(edges))]))

Submission status: Time Limit Exceeded

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

dist = []

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

root = [i for i in range(N + 1)]
comp_size = [1] * (N+1)
 
def root_find(x):
  if x == root[x]:
    return x
  else:
    z = root_find(root[x])
    root[x] = z
    return z

def merge(x, y):
  rx = root_find(x)
  ry = root_find(y)
  sx = comp_size[rx]
  sy = comp_size[ry]
  if rx != ry:
    if sx >= sy:
      root[ry] = rx
      comp_size[rx] = sx + sy
    else:
      root[rx] = ry
      comp_size[ry] = sx + sy
      
answer = 0
for d, (a, b) in dist:
  if root_find(a) != root_find(b):
    merge(a, b)
    answer += d

print(answer)