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:
import heapq
inf=10**9


def Prim():
    D=[inf for _ in range(n+1)]
    color=["white" for _ in range(n+1)]

    D[1]=0
    queue=[[0,1]]
    heapq.heapify(queue)
    while len(queue)>0:
        u=heapq.heappop(queue)[1]
        color[u]="black"

        V=[[i,j] for i,j in M[u] if color[j]!="black"]
        if len(V)>0:
            for i,j in V:
                if i<D[j]:
                    D[j]=i
                    color[j]="gray"
                    heapq.heappush(queue,[i,j])

    return D


n=int(input())
XY=[list(map(int,input().split()))+[i+1] for i in range(n)]
M=[[] for _ in range(n+1)]
A,B=sorted(XY),sorted(XY,key=lambda x:x[1])

for i in range(n):
    if i!=0:
        M[A[i][2]].append([min(abs(A[i-1][0]-A[i][0]),abs(A[i-1][1]-A[i][1])),A[i-1][2]])
        M[B[i][2]].append([min(abs(B[i][0] - B[i - 1][0]), abs(B[i][1] - B[i - 1][1])), B[i - 1][2]])
    if i!=n-1:
        M[A[i][2]].append([min(abs(A[i+1][0]-A[i][0]),abs(A[i+1][1]-A[i][1])),A[i+1][2]])
        M[B[i][2]].append([min(abs(B[i][0]-B[i+1][0]),abs(B[i][1]-B[i+1][1])),B[i+1][2]])

print(sum(Prim()[1:]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heapify, heappush, heappop


class PrimNode:

    def __init__(self, index, cost):
        self.index = index
        self.cost = cost

    def __lt__(self, other):
        return self.cost < other.cost


def prim(N, adj_nodes, costs, initial=0):
    frontier = [PrimNode(initial, 0)]
    heapify(frontier)
    explored = [0 for _ in range(N)]
    mst_cost = 0
    while len(frontier) > 0:
        node = heappop(frontier)
        if explored[node.index] == 1:
            continue
        mst_cost += node.cost
        explored[node.index] = 1
        next_node_indices = adj_nodes[node.index]
        for next_node_index in next_node_indices:
            if explored[next_node_index] == 1:
                continue
            heappush(frontier, PrimNode(next_node_index, costs[(node.index, next_node_index)]))
    return mst_cost


class Point:

    def __init__(self, index, x, y):
        self.index = index
        self.x = x
        self.y = y


def create_graph(N, points):
    adj_nodes = defaultdict(list)
    costs = defaultdict(int)
    costs_defined = defaultdict(int)
    # Sort by `x` and create edges between adjacent nodes
    points = sorted(points, key=lambda p: p.x)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.x - p.x
        adj_nodes[p.index].append(next_p.index)
        adj_nodes[next_p.index].append(p.index)
        costs[(p.index, next_p.index)] = cost
        costs[(next_p.index, p.index)] = cost
        costs_defined[(p.index, next_p.index)] = 1
        costs_defined[(next_p.index, p.index)] = 1
    # Sort by `y` and create edges between adjacent nodes
    points = sorted(points, key=lambda p: p.y)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.y - p.y
        adj_nodes[p.index].append(next_p.index)
        adj_nodes[next_p.index].append(p.index)
        current_cost = costs[(p.index, next_p.index)]
        if costs_defined[(p.index, next_p.index)]:
            new_cost = min([cost, current_cost])
            costs[(p.index, next_p.index)] = new_cost
            costs[(next_p.index, p.index)] = new_cost
        else:
            costs[(p.index, next_p.index)] = cost
            costs[(next_p.index, p.index)] = cost  
    return adj_nodes, costs


def main():
    N = int(input())
    points = list()
    for index in range(N):
        x, y = list(map(int, input().split(' ')))
        points.append(Point(index, x, y))
    adj_nodes, costs = create_graph(N, points)
    ans = prim(N, adj_nodes, costs)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heapify, heappush, heappop


class PrimNode:

    def __init__(self, index, cost):
        self.index = index
        self.cost = cost

    def __lt__(self, other):
        return self.cost < other.cost


def prim(N, adj_nodes, costs, initial=0):
    frontier = [PrimNode(initial, 0)]
    heapify(frontier)
    explored = [0 for _ in range(N)]
    mst_cost = 0
    while len(frontier) > 0:
        node = heappop(frontier)
        if explored[node.index] == 1:
            continue
        mst_cost += node.cost
        explored[node.index] = 1
        next_node_indices = adj_nodes[node.index]
        for next_node_index in next_node_indices:
            if explored[next_node_index] == 1:
                continue
            heappush(frontier, PrimNode(next_node_index, costs[node.index][next_node_index]))
    return mst_cost


class Point:

    def __init__(self, index, x, y):
        self.index = index
        self.x = x
        self.y = y


def create_graph(N, points):
    L = 10**12  # large number
    adj_nodes = [[] for _ in range(N)]
    costs = [[L for _ in range(N)] for _ in range(N)]
    # Sort by `x` and create edges between adjacent nodes
    points = sorted(points, key=lambda p: p.x)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.x - p.x
        adj_nodes[p.index].append(next_p.index)
        adj_nodes[next_p.index].append(p.index)
        costs[p.index][next_p.index] = cost
        costs[next_p.index][p.index] = cost
    # Sort by `y` and create edges between adjacent nodes
    points = sorted(points, key=lambda p: p.y)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.y - p.y
        adj_nodes[p.index].append(next_p.index)
        adj_nodes[next_p.index].append(p.index)
        costs[p.index][next_p.index] = min([cost, costs[p.index][next_p.index]])
        costs[next_p.index][p.index] = min([cost, costs[next_p.index][p.index]])
    return adj_nodes, costs


def main():
    N = int(input())
    points = list()
    for index in range(N):
        x, y = list(map(int, input().split(' ')))
        points.append(Point(index, x, y))
    adj_nodes, costs = create_graph(N, points)
    ans = prim(N, adj_nodes, costs)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heapify, heappush, heappop


class PrimNode:

    def __init__(self, index, cost):
        self.index = index
        self.cost = cost

    def __lt__(self, other):
        return self.cost < other.cost


def prim(N, adj_nodes, costs, initial=0):
    frontier = [PrimNode(initial, 0)]
    heapify(frontier)
    explored = [0 for _ in range(N)]
    mst_cost = 0
    while len(frontier) > 0:
        node = heappop(frontier)
        if explored[node.index] == 1:
            continue
        mst_cost += node.cost
        explored[node.index] = 1
        next_node_indices = adj_nodes[node.index]
        for next_node_index in next_node_indices:
            if explored[next_node_index] == 1:
                continue
            heappush(frontier, PrimNode(next_node_index, costs[(node.index, next_node_index)]))
    return mst_cost


class Point:

    def __init__(self, index, x, y):
        self.index = index
        self.x = x
        self.y = y


def create_graph(N, points):
    L = 10**12  # large number
    adj_nodes = defaultdict(list)
    costs = defaultdict(lambda:L)
    # Sort by `x` and create edges between adjacent nodes
    points = sorted(points, key=lambda p: p.x)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.x - p.x
        adj_nodes[p.index].append(next_p.index)
        adj_nodes[next_p.index].append(p.index)
        costs[(p.index, next_p.index)] = cost
        costs[(next_p.index, p.index)] = cost
    # Sort by `y` and create edges between adjacent nodes
    points = sorted(points, key=lambda p: p.y)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.y - p.y
        adj_nodes[p.index].append(next_p.index)
        adj_nodes[next_p.index].append(p.index)
        costs[(p.index, next_p.index)] = min([cost, costs[(p.index, next_p.index)]])
        costs[(next_p.index, p.index)] = min([cost, costs[(next_p.index, p.index)]])
    return adj_nodes, costs


def main():
    N = int(input())
    points = list()
    for index in range(N):
        x, y = list(map(int, input().split(' ')))
        points.append(Point(index, x, y))
    adj_nodes, costs = create_graph(N, points)
    ans = prim(N, adj_nodes, costs)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappush, heappop


class PrimNode:

    def __init__(self, index, cost):
        self.index = index
        self.cost = cost

    def __lt__(self, other):
        return self.cost < other.cost


def prim(N, adj_nodes, costs, initial=0):
    frontier = [PrimNode(initial, 0)]
    explored = [0 for _ in range(N)]
    mst_cost = 0
    while len(frontier) > 0:
        node = heappop(frontier)
        if explored[node.index] == 1:
            continue
        mst_cost += node.cost
        explored[node.index] = 1
        next_node_indices = adj_nodes[node.index]
        for next_node_index in next_node_indices:
            if explored[next_node_index] == 1:
                continue
            heappush(frontier, PrimNode(next_node_index, costs[(node.index, next_node_index)]))
    return mst_cost


class Point:

    def __init__(self, index, x, y):
        self.index = index
        self.x = x
        self.y = y


def create_graph(N, points):
    L = 10**12  # large number
    adj_nodes = defaultdict(list)
    costs = defaultdict(lambda:L)
    # Sort by `x` and create edges between adjacent nodes
    points = sorted(points, key=lambda p: p.x)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.x - p.x
        adj_nodes[p.index].append(next_p.index)
        adj_nodes[next_p.index].append(p.index)
        costs[(p.index, next_p.index)] = cost
        costs[(next_p.index, p.index)] = cost
    # Sort by `y` and create edges between adjacent nodes
    points = sorted(points, key=lambda p: p.y)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.y - p.y
        adj_nodes[p.index].append(next_p.index)
        adj_nodes[next_p.index].append(p.index)
        costs[(p.index, next_p.index)] = min([cost, costs[(p.index, next_p.index)]])
        costs[(next_p.index, p.index)] = min([cost, costs[(next_p.index, p.index)]])
    return adj_nodes, costs


def main():
    N = int(input())
    points = list()
    for index in range(N):
        x, y = list(map(int, input().split(' ')))
        points.append(Point(index, x, y))
    adj_nodes, costs = create_graph(N, points)
    ans = prim(N, adj_nodes, costs)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappush, heappop


class PrimNode:

    def __init__(self, index, cost):
        self.index = index
        self.cost = cost

    def __lt__(self, other):
        return self.cost < other.cost


def prim(N, adj_nodes, costs, initial=0):
    frontier = [PrimNode(initial, 0)]
    explored = [0 for _ in range(N)]
    mst_cost = 0
    while len(frontier) > 0:
        node = heappop(frontier)
        if explored[node.index] == 1:
            continue
        mst_cost += node.cost
        explored[node.index] = 1
        next_node_indices = adj_nodes[node.index]
        for next_node_index in next_node_indices:
            if explored[next_node_index] == 1:
                continue
            heappush(frontier, PrimNode(next_node_index, costs[(node.index, next_node_index)]))
    return mst_cost


class Point:

    def __init__(self, index, x, y):
        self.index = index
        self.x = x
        self.y = y


def create_graph(N, points):
    L = 10**12  # large number
    adj_nodes = defaultdict(set)
    costs = defaultdict(lambda:L)
    # Sort by `x` and create edges between adjacent nodes
    points = sorted(points, key=lambda p: p.x)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.x - p.x
        adj_nodes[p.index].add(next_p.index)
        adj_nodes[next_p.index].add(p.index)
        costs[(p.index, next_p.index)] = cost
        costs[(next_p.index, p.index)] = cost
    # Sort by `y` and create edges between adjacent nodes
    points = sorted(points, key=lambda p: p.y)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.y - p.y
        adj_nodes[p.index].add(next_p.index)
        adj_nodes[next_p.index].add(p.index)
        costs[(p.index, next_p.index)] = min([cost, costs[(p.index, next_p.index)]])
        costs[(next_p.index, p.index)] = min([cost, costs[(next_p.index, p.index)]])
    return adj_nodes, costs


def main():
    N = int(input())
    points = list()
    for index in range(N):
        x, y = list(map(int, input().split(' ')))
        points.append(Point(index, x, y))
    adj_nodes, costs = create_graph(N, points)
    ans = prim(N, adj_nodes, costs)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import heapq
hqx=[]
hqy=[]
for i in range(n):
    x,y=map(int,input().split())
    heapq.heappush(hqx,(x,i))
    heapq.heappush(hqy,(y,i))
prex,prexi=heapq.heappop(hqx)
prey,preyi=heapq.heappop(hqy)
edges=[]#(cost,v1,v2)
for i in range(n-1):
    x,xi=heapq.heappop(hqx)
    y,yi=heapq.heappop(hqy)
    heapq.heappush(edges,(x-prex,prexi,xi))
    heapq.heappush(edges,(y-prey,preyi,yi))
    prex,prexi=x,xi
    prey,preyi=y,yi

frag=list(range(n+1))
fragnum=[0]*(n+1)

#以下でフラグ建設 フラグが同じなら同じチームである
def takefrag(p):
    stock=[]
    while frag[frag[p]]!=frag[p]:
        stock.append(p)
        p=frag[p]
    p=frag[p]
    for i in stock:
        frag[i]=p
    return p

count=0
ans=0
while True:
    cost,a,b=heapq.heappop(edges)
    f1,f2 = map(takefrag,(a,b))
    if f1!=f2:
        count+=1
        f1,f2 = min(f1,f2),max(f1,f2)
        frag[f1]=f2
        ans+=cost
    if count==n-1:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
import heapq
from collections import deque
import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize


# ===CODE===
def main():
    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())
    tree = UnionFind(n)

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

    edges_x.sort()
    edges_y.sort()

    edges = []
    for i in range(n - 1):
        tmp = abs(edges_x[i][0] - edges_x[i + 1][0])
        edges.append((tmp, edges_x[i][1], edges_x[i + 1][1]))
        tmp = abs(edges_y[i][0] - edges_y[i + 1][0])
        edges.append((tmp, edges_y[i][1], edges_y[i + 1][1]))

    edges.sort()

    ans = 0
    for d, s, t in edges:
        if not tree.same(s, t):
            tree.union(s, t)
            ans += d

    print(ans)


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

Submission status: Time Limit Exceeded

Solution code:
import heapq


class Prim():
    # 無向グラフであるという前提に注意
    def __init__(self, N):
        self.edge = [[] for i in range(N)]
        self.N = N

    def add(self, u, v, d):
        """
        u = from, v = to, d = cost
        0-indexedであることに注意、graph.add(u-1, v-1)とする必要がある
        """
        self.edge[u].append([d, v])  # コスト、e_toとなっていることに注意
        self.edge[v].append([d, u])

    def delete(self, u, v):
        self.edge[u] = [_ for _ in self.edge[u] if _[0] != v]
        self.edge[v] = [_ for _ in self.edge[v] if _[0] != u]

    def Prim(self):
        """
        return: 最小全域木のコストの和
        """
        used = [True] * self.N  # True:不使用
        edgelist = []
        for e in self.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 self.edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist, e)
            res += minedge[0]
        return res

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

G = Prim(N)

X = []
Y = []
for i in range(G.N):
    X.append((data[i][0],i))
    Y.append((data[i][1],i))

X = sorted(X)
Y = sorted(Y)

#辞書順で隣り合うものだけ考えれば良い

for i in range(G.N-1):
    G.add(X[i][1],X[i+1][1],X[i+1][0]-X[i][0])
    G.add(Y[i][1],Y[i+1][1],Y[i+1][0]-Y[i][0])

print(G.Prim())

Submission status: Time Limit Exceeded

Solution code:
import heapq


class Prim():
    # 無向グラフであるという前提に注意
    def __init__(self, N):
        self.edge = [[] for i in range(N)]
        self.N = N

    def add(self, u, v, d):
        """
        u = from, v = to, d = cost
        0-indexedであることに注意、graph.add(u-1, v-1)とする必要がある
        """
        self.edge[u].append([d, v])  # コスト、e_toとなっていることに注意
        self.edge[v].append([d, u])

    def delete(self, u, v):
        self.edge[u] = [_ for _ in self.edge[u] if _[0] != v]
        self.edge[v] = [_ for _ in self.edge[v] if _[0] != u]

    def Prim(self):
        """
        return: 最小全域木のコストの和
        """
        used = [True] * self.N  # True:不使用
        edgelist = []
        for e in self.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 self.edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist, e)
            res += minedge[0]
        return res

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

G = Prim(N)

for i in range(G.N-1):
    for j in range(i+1,G.N):
        G.add(i,j,min(abs(data[i][0]-data[j][0]),abs(data[i][1]-data[j][1])))

print(G.Prim())

Submission status: Time Limit Exceeded

Solution code:
def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
        else:
            par[a]=b
            if rank[a]==rank[b]:
                rank[b]+=1
def same(a,b):
    return find(a)==find(b)
def Kruskal(Edge,E):
    cost=0
    Edge.sort(key=lambda x:x[2])
    for i in range(E):
        f,t,c=Edge[i]
        if(not same(f,t)):
            union(f,t)
            cost+=c
    return cost

N=int(input())
par=[i for i in range(N)]
rank=[0 for _ in range(N)]
p=[tuple(map(int,input().split())) for i in range(N)]
dic={p[i]:i for i in range(N)}
xp=sorted(p,key=lambda x:x[0])
yp=sorted(p,key=lambda x:x[1])
Edge=[]
for i in range(N):
    if(i>0):
        Edge.append((dic[xp[i]],dic[xp[i-1]],abs(xp[i][0]-xp[i-1][0])))
    if(i<N-1):
        Edge.append((dic[xp[i]],dic[xp[i+1]],abs(xp[i][0]-xp[i+1][0])))
for i in range(N):
    if(i>0):
        Edge.append((dic[yp[i]],dic[yp[i-1]],abs(yp[i][1]-yp[i-1][1])))
    if(i<N-1):
        Edge.append((dic[yp[i]],dic[yp[i+1]],abs(yp[i][1]-yp[i+1][1])))
Edge.sort(key=lambda x:x[2])

print(Kruskal(Edge,len(Edge)))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import namedtuple
from heapq import heappush, heappop

input = stdin.readline


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

  def is_same(self, a, b):
    return self.find(a) == self.find(b)

  def unite(self, a, b):
    a = self.find(a)
    b = self.find(b)  
    if self.rank[a] < self.rank[b]:
      a, b = b, a
    self.par[b] = a
    if self.rank[a] == self.rank[b]:
      self.rank[a] += 1

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

Edge = namedtuple('Edge', 'w s t')
X = namedtuple('X', 'x i')
Y = namedtuple('Y', 'y i')

N = int(input())

edges = []
xg = []
yg = []

for i in range(N):
  x, y = map(int, input().split())
  xg.append(X(x, i))
  yg.append(Y(y, i))

xg.sort()
yg.sort()

for i in range(N - 1):
  x1, a = xg[i]
  x2, b = xg[i + 1]
  heappush(edges, Edge(abs(x1 - x2), a, b))

for i in range(N - 1):
  y1, a = yg[i]
  y2, b = yg[i + 1]
  heappush(edges, Edge(abs(y1 - y2), a, b))

u = UnionFind(N)
cost = 0

while edges:
  w, s, t = heappop(edges)
  if u.is_same(s, t):
    continue
  u.unite(s, t)
  cost += w

print(cost)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import namedtuple
from heapq import heappush, heappop

input = stdin.readline


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

  def is_same(self, a, b):
    return self.find(a) == self.find(b)

  def unite(self, a, b):
    a = self.find(a)
    b = self.find(b)  
    if self.size[a] < self.size[b]:
      a, b = b, a
    self.par[b] = a
    self.size[a] += self.size[b]

  def size_of(self, a):
    return self.size[self.find(a)]

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

Edge = namedtuple('Edge', 'w s t')
X = namedtuple('X', 'x i')
Y = namedtuple('Y', 'y i')

N = int(input())

edges = []
xg = []
yg = []

for i in range(N):
  x, y = map(int, input().split())
  xg.append(X(x, i))
  yg.append(Y(y, i))

xg.sort()
yg.sort()

for i in range(N - 1):
  x1, a = xg[i]
  x2, b = xg[i + 1]
  heappush(edges, Edge(abs(x1 - x2), a, b))

for i in range(N - 1):
  y1, a = yg[i]
  y2, b = yg[i + 1]
  heappush(edges, Edge(abs(y1 - y2), a, b))

u = UnionFind(N)
cost = 0

while edges:
  if u.size_of(0) >= N:
    break

  w, s, t = heappop(edges)
  if u.is_same(s, t):
    continue
  u.unite(s, t)
  cost += w

print(cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import namedtuple
from heapq import heappush, heappop

input = sys.stdin.readline

INF = sys.maxsize

P = namedtuple('P', 'cost v')
Edge = namedtuple('Edge', 'cost to')
X = namedtuple('X', 'x i')
Y = namedtuple('Y', 'y i')

N = int(input())

G = [[] for _ in range(N)]
xg = []
yg = []

for i in range(N):
  x, y = map(int, input().split())
  xg.append(X(x, i))
  yg.append(Y(y, i))

xg.sort()
yg.sort()

for i in range(N - 1):
  x1, a = xg[i]
  x2, b = xg[i + 1]
  y1, c = yg[i]
  y2, d = yg[i + 1]
  G[a].append(Edge(abs(x1 - x2), b))
  G[b].append(Edge(abs(x1 - x2), a))
  G[c].append(Edge(abs(y1 - y2), d))
  G[d].append(Edge(abs(y1 - y2), c))

total = 0
costs = [INF] * N
costs[0] = 0  # 集合Xからの最短距離
used = set()

q = [P(0, 0)]

while q: 
  p = heappop(q)

  if len(used) >= N:
    break

  if p.v in used and p.cost >= costs[p.v]:
    continue

  costs[p.v] = 0
  total += p.cost
  used.add(p.v)

  for cost, to in G[p.v]:
    if costs[to] > costs[p.v] + cost:
      costs[to] = costs[p.v] + cost
      heappush(q, P(costs[to], to))

print(total)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import namedtuple
from heapq import heappush, heappop

INF = sys.maxsize

P = namedtuple('P', 'cost v')
Edge = namedtuple('Edge', 'cost to')
X = namedtuple('X', 'x i')
Y = namedtuple('Y', 'y i')

N = int(input())

G = [[] for _ in range(N)]
xg = []
yg = []

for i in range(N):
  x, y = map(int, input().split())
  xg.append(X(x, i))
  yg.append(Y(y, i))

xg.sort()
yg.sort()

for i in range(N - 1):
  x1, a = xg[i]
  x2, b = xg[i + 1]
  y1, c = yg[i]
  y2, d = yg[i + 1]
  G[a].append(Edge(abs(x1 - x2), b))
  G[b].append(Edge(abs(x1 - x2), a))
  G[c].append(Edge(abs(y1 - y2), d))
  G[d].append(Edge(abs(y1 - y2), c))

total = 0
costs = [INF] * N
costs[0] = 0  # 集合Xからの最短距離
used = set()

q = [P(0, 0)]

while q: 
  p = heappop(q)

  if len(used) >= N:
    break

  if p.v in used and p.cost >= costs[p.v]:
    continue

  costs[p.v] = 0
  total += p.cost
  used.add(p.v)

  for cost, to in G[p.v]:
    if costs[to] > costs[p.v] + cost:
      costs[to] = costs[p.v] + cost
      heappush(q, P(costs[to], to))

print(total)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import namedtuple
from heapq import heappush, heappop

INF = sys.maxsize

P = namedtuple('P', 'cost v')
Edge = namedtuple('Edge', 'cost to')
X = namedtuple('X', 'x i')
Y = namedtuple('Y', 'y i')

N = int(input())

G = [[] for _ in range(N)]
xg = []
yg = []

for i in range(N):
  x, y = map(int, input().split())
  xg.append(X(x, i))
  yg.append(Y(y, i))

xg.sort()
yg.sort()

for i in range(N - 1):
  x1, a = xg[i]
  x2, b = xg[i + 1]
  G[a].append(Edge(abs(x1 - x2), b))
  G[b].append(Edge(abs(x1 - x2), a))

for i in range(N - 1):
  y1, a = yg[i]
  y2, b = yg[i + 1]
  G[a].append(Edge(abs(y1 - y2), b))
  G[b].append(Edge(abs(y1 - y2), a))

total = 0
costs = [INF] * N
costs[0] = 0  # 集合Xからの最短距離
used = set()

q = [P(0, 0)]

while q: 
  p = heappop(q)

  if p.v in used and p.cost >= costs[p.v]:
    continue

  costs[p.v] = 0
  total += p.cost
  used.add(p.v)

  for cost, to in G[p.v]:
    if costs[to] > costs[p.v] + cost:
      costs[to] = costs[p.v] + cost
      heappush(q, P(costs[to], to))

print(total)

Submission status: Time Limit Exceeded

Solution code:
from collections import namedtuple
from heapq import heappush, heappop


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

  def is_same(self, a, b):
    return self.find(a) == self.find(b)

  def unite(self, a, b):
    a = self.find(a)
    b = self.find(b)  
    if self.size[a] < self.size[b]:
      a, b = b, a
    self.par[b] = a
    self.size[a] += self.size[b]

  def size_of(self, a):
    return self.size[self.find(a)]

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

Edge = namedtuple('Edge', 'w s t')
X = namedtuple('X', 'x i')
Y = namedtuple('Y', 'y i')

N = int(input())

edges = []
xg = []
yg = []

for i in range(N):
  x, y = map(int, input().split())
  xg.append(X(x, i))
  yg.append(Y(y, i))

xg.sort()
yg.sort()

for i in range(N - 1):
  x1, a = xg[i]
  x2, b = xg[i + 1]
  heappush(edges, Edge(abs(x1 - x2), a, b))

for i in range(N - 1):
  y1, a = yg[i]
  y2, b = yg[i + 1]
  heappush(edges, Edge(abs(y1 - y2), a, b))

u = UnionFind(N)
cost = 0

while edges:
  if u.size_of(0) >= N:
    break

  w, s, t = heappop(edges)
  if u.is_same(s, t):
    continue
  u.unite(s, t)
  cost += w

print(cost)

Submission status: Time Limit Exceeded

Solution code:
from collections import namedtuple


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

  def is_same(self, a, b):
    return self.find(a) == self.find(b)

  def unite(self, a, b):
    a = self.find(a)
    b = self.find(b)  
    if self.size[a] < self.size[b]:
      a, b = b, a
    self.par[b] = a
    self.size[a] += self.size[b]

  def size_of(self, a):
    return self.size[self.find(a)]

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

Edge = namedtuple('Edge', 'w s t')
X = namedtuple('X', 'x i')
Y = namedtuple('Y', 'y i')

N = int(input())

edges = []
xg = []
yg = []

for i in range(N):
  x, y = map(int, input().split())
  xg.append(X(x, i))
  yg.append(Y(y, i))

xg.sort()
yg.sort()

for i in range(N - 1):
  x1, a = xg[i]
  x2, b = xg[i + 1]
  edges.append(Edge(abs(x1 - x2), a, b))

for i in range(N - 1):
  y1, a = yg[i]
  y2, b = yg[i + 1]
  edges.append(Edge(abs(y1 - y2), a, b))

edges.sort()

u = UnionFind(N)
cost = 0

for w, s, t in edges:
  if u.is_same(s, t):
    continue
  u.unite(s, t)
  cost += w

print(cost)