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:
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])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n = int(input())

def prim_heap():
    used = [False]*n
    edgelist = []
    for e in graph[0]:
        heapq.heappush(edgelist,e)
    used[0] = True
    ans = 0
    while edgelist:
        minedge = heapq.heappop(edgelist)
        v = minedge[1]
        if used[minedge[1]]:
            continue
        used[v] = True
        for e in graph[v]:
            if not used[e[1]]:
                heapq.heappush(edgelist,e)
        ans += minedge[0]
    return ans

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 = [[] for _ in range(n)]


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[i].append([m,j])
        graph[j].append([m,i])
S(graphx)
S(graphy)

print(prim_heap())

Submission status: Time Limit Exceeded

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


def main():
    N = int(input())
    X = []
    Y = []
    color = [-1 for i in range(N)]
    for i in range(N):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
    heap = []
    heapq.heappush(heap, (0, 0))
    count = 0
    while len(heap) != 0:
        d, now = heapq.heappop(heap)
        if color[now] == 1:
            continue
        color[now] = 1
        count += d
        for i in range(N):
            if color[i] == 1:
                continue
            a = min(abs(X[now] - X[i]), abs(Y[now] - Y[i]))
            heapq.heappush(heap, (a, i))
    print(count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def main():
    N = int(input())
    X = []
    Y = []
    color = [-1 for i in range(N)]
    for i in range(N):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
    heap = []
    heapq.heappush(heap, (0, 0))
    count = 0
    while len(heap) != 0:
        d, now = heapq.heappop(heap)
        if color[now] == 1:
            continue
        color[now] = 1
        count += d
        for i in range(N):
            if i == now:
                continue
            a = min(abs(X[now] - X[i]), abs(Y[now] - Y[i]))
            heapq.heappush(heap, (a, i))
    print(count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
towns = [list(map(int, input().split())) for _ in range(N)]

# 全ての町の間に道を作りたい
# ただし、もっともお金がかからないように、最低限の道だけ作りたい
# また、もっともお金がかからない = もっとも近いなので、最短の経路を見つけ出せば良い。
# 全ての道を出して、そこから最小全域木出せば良さそう

loads = []
inf = float('inf')

for i in range(N):
    for j in range(i, N):
        loads.append([i, j, min(abs(towns[i][0] - towns[j][0]), abs(towns[i][1] - towns[j][1]))])
loads.sort(key=lambda x: x[2])
# print(loads)

nodes = [i for i in range(N)]


def root(node):
    if nodes[node] == node:
        return node
    nodes[node] = root(nodes[node])
    return nodes[node]


cost = 0
for i, j, k in loads:
    if k == inf:
        continue
    if not root(i) == root(j):
        cost += k
        nodes[root(i)] = root(j)
# print(nodes)
print(cost)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

#print(G)

D=[[] for _ in range(n)]

xG=sorted(G,key=lambda x:x[1])
for index_x in range(n-1):
    nowx=xG[index_x]
    nextx=xG[index_x+1]
    distx=nextx[1]-nowx[1]
    D[nowx[0]].append([distx,nextx[0]])
    D[nextx[0]].append([distx,nowx[0]])

#print(xG)

yG=sorted(G,key=lambda x:x[2])
for index_y in range(n-1):
    nowy=yG[index_y]
    nexty=yG[index_y+1]
    disty=nexty[2]-nowy[2]
    D[nowy[0]].append([disty,nexty[0]])
    D[nexty[0]].append([disty,nowy[0]])

#print(yG)

#print(D)

def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in D[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 D[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

ans=prim_heap()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#UnionFind木とそれを利用したクラスカル法
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 same(self, x, y):
        return self.find(x) == self.find(y)

    def nums(self,x):
        return abs(self.parents[self.find(x)])

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

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

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


N = int(input())
A = [list(map(int, input().split()))+[i] for i in range(N)]
edge = []
A.sort()
for i in range(N-1):
    w = A[i+1][0]-A[i][0]
    edge.append((w,A[i][2],A[i+1][2]))
A.sort(key=lambda x:x[1])
for i in range(N-1):
    w = A[i+1][1]-A[i][1]
    edge.append((w,A[i][2],A[i+1][2]))

edge.sort()

uf = UnionFind(N)
ans = 0
for i in range(len(edge)):
    u,x,y = edge[i]
    if not uf.same(x,y):
        uf.union(x,y)
        ans += u
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#UnionFind木とそれを利用したクラスカル法
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 same(self, x, y):
        return self.find(x) == self.find(y)

    def nums(self,x):
        return abs(self.parents[self.find(x)])

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

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

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


N = int(input())
A = [list(map(int, input().split()))+[i] for i in range(N)]
edge = []
A.sort()
for i in range(N-1):
    w = min(abs(A[i+1][0]-A[i][0]),abs(A[i+1][1]-A[i][1]))
    edge.append((w,A[i][2],A[i+1][2]))
A.sort(key=lambda x:x[1])
for i in range(N-1):
    w = min(abs(A[i+1][0]-A[i][0]),abs(A[i+1][1]-A[i][1]))
    edge.append((w,A[i][2],A[i+1][2]))

edge.sort()

uf = UnionFind(N)
ans = 0
for i in range(len(edge)):
    u,x,y = edge[i]
    if not uf.same(x,y):
        uf.union(x,y)
        ans += u
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    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())

if __name__ == '__main__':
    main()

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 same(self, x, y):
        return self.find(x) == self.find(y)


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

e = []
for i in range(N-1):
    e.append([abs(x[i][0]-x[i+1][0]), x[i][1], x[i+1][1]])
    e.append([abs(y[i][0]-y[i+1][0]), y[i][1], y[i+1][1]])

e.sort()

uft = UnionFind(N)

ans = 0
for w, s, t in e:
    if not uft.same(s, t):
        uft.union(s, t)
        ans += w

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


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

e = []
for i in range(N-1):
    e.append([abs(x[i][0]-x[i+1][0]), x[i][1], x[i+1][1]])
    e.append([abs(y[i][0]-y[i+1][0]), y[i][1], y[i+1][1]])

e.sort()

v = {}
v[0] = 1
ans = 0
while len(v) < N:
    for w, s, t in e:
        if (s in v and t not in v) or (s not in v and t in v):
            v[s] = 1
            v[t] = 1
            ans += w
            break
print(ans)
'''
クラスカル
uft = UnionFindTree()
for i in range(N):
    uft.make(i)

ans = 0
for w, s, t in e:
    if not uft.same(s, t):
        uft.unite(s, t)
        ans += w

print(ans)
'''

Submission status: Time Limit Exceeded

Solution code:
import heapq


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


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

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

uft = UnionFindTree()
for i in range(N):
    uft.make(i)

ans = 0
while len(e) > 0:
    w, s, t = heapq.heappop(e)
    if not uft.same(s, t):
        uft.unite(s, t)
        ans += w

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


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

e = []
for i in range(N-1):
    e.append([abs(x[i][0]-x[i+1][0]), x[i][1], x[i+1][1]])
    e.append([abs(y[i][0]-y[i+1][0]), y[i][1], y[i+1][1]])

e.sort()
uft = UnionFindTree()
for i in range(N):
    uft.make(i)

ans = 0
for w, s, t in e:
    if not uft.same(s, t):
        uft.unite(s, t)
        ans += w

print(ans)

Submission status: Time Limit Exceeded

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

lx = sorted(l)
ly = sorted(l, key=lambda x: x[1])

e = []
for i in range(n-1):
    e.append([lx[i+1][0]-lx[i][0],lx[i+1][2],lx[i][2]])
    e.append([ly[i+1][1]-ly[i][1],ly[i+1][2],ly[i][2]])


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

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

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

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x

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

u = Unionfind(n)
count = 0
e.sort()
for i in e:
    if u.find(i[1]) != u.find(i[2]):
        u.union(i[1],i[2])
        count += i[0]
print(count)

Submission status: Time Limit Exceeded

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

import sys

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

X.sort()
Y.sort()

edge=[]

for i in range(N-1):
    x1,y1,x2,y2=X[i][0],X[i][1],X[i+1][0],X[i+1][1]
    if min(abs(x1-x2),abs(y1-y2))==abs(x1-x2):
        edge.append((abs(x1-x2),X[i][2],X[i+1][2]))

for i in range(N-1):
    x1,y1,x2,y2=Y[i][0],Y[i][1],Y[i+1][0],Y[i+1][1]
    if min(abs(x1-x2),abs(y1-y2))==abs(x1-x2):
        edge.append((abs(x1-x2),Y[i][2],Y[i+1][2]))

uf=UnionFindVerSize(N)
ans=0
edge.sort()
for i in range(len(edge)):
    cost,u,v=edge[i]
    if not uf.is_same_group(u,v):
        uf.unite(u,v)
        ans+=cost

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

N = int(input())
xy = sorted([list(map(int, input().split())) + [i] for i in range(N)])
E = []
for i in range(N-1):
  E.append((xy[i+1][0]-xy[i][0],xy[i][2],xy[i+1][2]))
xy.sort(key = itemgetter(1))
for i in range(N-1):
  E.append((xy[i+1][1]-xy[i][1],xy[i][2],xy[i+1][2]))
*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y

def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
    else:
        p[px] = py
    return 1

E.sort()
ans = 0
for c, v, w in E:
    if unite(v, w):
        ans += c
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1

N = int(input())
nodesX = []
nodesY = []
for i in range(1,N+1):
    x,y = map(int,input().split())
    nodesX.append((x,i))
    nodesY.append((y,i))
nodesX.sort()
nodesY.sort()
edges = []
for i in range(1,N):
    edges.append((nodesX[i][0]-nodesX[i-1][0],nodesX[i][1],nodesX[i-1][1]))
    edges.append((nodesY[i][0]-nodesY[i-1][0],nodesY[i][1],nodesY[i-1][1]))
edges.sort()
tree = UnionFind(N)
cost = 0
for w,s,t in edges:
    if tree.find(s)!= tree.find(t):
        tree.unite(s,t)
        cost += w
print(cost)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1
tree = UnionFind(N)

xList = []
yList = []
for i in range(1,N+1):
    x,y = map(int,input().split())
    xList.append((x,i))
    yList.append((y,i))
xList.sort()
yList.sort()
edges = []
for i in range(1,N):
    edges.append((xList[i][0]-xList[i-1][0],xList[i-1][1],xList[i][1]))
    edges.append((yList[i][0]-yList[i-1][0],yList[i-1][1],yList[i][1]))
edges.sort()
cost = 0
for e in edges:
    w,s,t = e
    if tree.find(s) != tree.find(t):
        tree.unite(s,t)
        cost += w

print(cost)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n=int(input())
x=[]
y=[]
for i in range(n):
  xx,yy=map(int,input().split())
  x.append([xx,i])
  y.append([yy,i])
x.sort()
y.sort()
px=[]
py=[]
for i in range(n-1):
  px.append([x[i+1][0]-x[i][0],x[i][1],x[i+1][1]])
  py.append([y[i+1][0]-y[i][0],y[i][1],y[i+1][1]])
p=px+py
x=[]
y=[]
px=[]
py=[]
heapq.heapify(p)
r=[i for i in range(n)]
rank=[1 for i in range(n)]
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rank[rx]>rank[ry]:
    r[rx]=ry
    rank[rx]+=rank[ry]
  else:
    r[ry]=rx
    rank[ry]+=rank[rx]
ans=0
while p:
  path=heapq.heappop(p)
  if root(path[1])==root(path[2]):
    continue
  union(path[1],path[2])
  ans+=path[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
n = int(input())
X = []
Y = []
for i in range(n):
  x,y = map(int,input().split())
  X.append((x,i))
  Y.append((y,i))

X.sort()
Y.sort()
G = [[] for _ in range(n)]

for i in range(n-1):
  cost = X[i+1][0] - X[i][0]
  G[X[i+1][1]].append([cost, X[i][1]])
  G[X[i][1]].append([cost, X[i+1][1]])
  
  cost = Y[i+1][0] - Y[i][0]
  G[Y[i+1][1]].append([cost, Y[i][1]])
  G[Y[i][1]].append([cost, Y[i+1][1]])  
  
  
visited = [0] * n
visited[0] = 1

pq = []
for c,t in G[0]:
  heappush(pq,(c,t))
  
ans = 0
while(pq):
  c, t = heappop(pq)
  if visited[t]:
    continue
  visited[t] = 1
  ans += c
  for c,s in G[t]:
    if visited[s] == 0:
      heappush(pq,(c,s))
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
n = int(input())
X = []
Y = []
for i in range(n):
  x,y = map(int,input().split())
  X.append((x,i))
  Y.append((y,i))

X = sorted(X)
Y = sorted(Y)
G = [[] for _ in range(n)]

for i in range(n-1):
  cost = X[i+1][0] - X[i][0]
  G[X[i+1][1]].append([cost, X[i][1]])
  G[X[i][1]].append([cost, X[i+1][1]])
  
  cost = Y[i+1][0] - Y[i][0]
  G[Y[i+1][1]].append([cost, Y[i][1]])
  G[Y[i][1]].append([cost, Y[i+1][1]])  
  
  
visited = [0] * n
visited[0] = 1

pq = []
for c,t in G[0]:
  heappush(pq,(c,t))
  
ans = 0
while(pq):
  c, t = heappop(pq)
  if visited[t]:
    continue
  visited[t] = 1
  ans += c
  for c,s in G[t]:
    if visited[s] == 0:
      heappush(pq,(c,s))
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
n = int(input())
X = []
Y = []
for i in range(n):
  x,y = map(int,input().split())
  X.append([x,i])
  Y.append([y,i])

X = sorted(X)
Y = sorted(Y)
G = [[] for _ in range(n)]

for i in range(n-1):
  cost = X[i+1][0] - X[i][0]
  G[X[i+1][1]].append([cost, X[i][1]])
  G[X[i][1]].append([cost, X[i+1][1]])
  
  cost = Y[i+1][0] - Y[i][0]
  G[Y[i+1][1]].append([cost, Y[i][1]])
  G[Y[i][1]].append([cost, Y[i+1][1]])  
  
  
visited = [0] * n
visited[0] = 1

pq = []
for c,t in G[0]:
  heappush(pq,[c,t])
  
ans = 0
while(pq):
  c, t = heappop(pq)
  if visited[t]:
    continue
  visited[t] = 1
  ans += c
  for c,s in G[t]:
    if visited[s] == 0:
      heappush(pq,[c,s])
      
print(ans)

Submission status: Time Limit Exceeded

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

N=int(input())

xylist,yxlist=[],[]
par_dic={}
for i in range(N):
  x,y=map(int,input().split())
  xylist.append((x,y))
  yxlist.append((y,x))
  par_dic[(x,y)]=(x,y)
xylist.sort()
yxlist.sort()
#print(xylist)

hq=[]
for i in range(1,N):
  x1,y1=xylist[i-1]
  x2,y2=xylist[i]
  heapq.heappush(hq,(min(abs(x2-x1),abs(y1-y2)),(x1,y1),(x2,y2)))
  y1,x1=yxlist[i-1]
  y2,x2=yxlist[i]
  heapq.heappush(hq,(min(abs(x2-x1),abs(y1-y2)),(x1,y1),(x2,y2)))
#print(hq)

def get_par(x):
  if x == par_dic[x]:
    return x
  else:
    par_dic[x] = get_par(par_dic[x])
    return par_dic[x]
def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_dic[par_y] = par_x
def is_same(x,y):
  return get_par(x) == get_par(y)

answer=0
while hq:
  d,p1,p2=heapq.heappop(hq)
  #print(d,p1,p2)
  if not is_same(p1,p2):
    merge(p1,p2)
    answer+=d
  
print(answer)

Submission status: Time Limit Exceeded

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

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

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)

        if x==y:return
        elif self.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

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

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

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

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

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


def kruskal():
    D,M=[],[]

    A,B=sorted(XY),sorted(XY, key=lambda x: x[1])
    for i in range(n-1):
        M.append([min(abs(A[i][0]-A[i+1][0]),abs(A[i][1]-A[i+1][1])),A[i][2],A[i+1][2]])
        M.append([min(abs(B[i][0]-B[i+1][0]),abs(B[i][1]-B[i+1][1])),B[i][2],B[i+1][2]])

    M.sort()
    for w,s,t in M:
        if UnionFind.isSameGroup(s,t) is False:
            UnionFind.Unite(s,t)
            D.append(w)

    return D


n=int(input())
XY=[list(map(int,input().split()))+[i+1] for i in range(n)]
UnionFind=UnionFind(n+1)
print(sum(kruskal()))

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"

        for i,j in M[u]:
            if i<D[j] and color[j]!="black":
                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:]))