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

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    x, a, b = LI()
    if b <= a:
        print("delicious")
    elif b <= a + x:
        print("safe")
    else:
        print("dangerous")

    return

#B
def B():
    n = II()
    a = IR(n)
    check = [False] * (n + 1)
    check[1] = True
    now = a[0]
    for i in range(1,n+1):
        if check[now]:
            break
        if now == 2:
            print(i)
            return
        check[now] = True
        now = a[now - 1]
    print(-1)
    return

#C
def C():
    return

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

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

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.size = n
        self.data = [-1 for _ in range(n)]
        self.sizes = [1 for _ in range(n)]

    def __len__(self):
        return self.size

    def root(self, i):
        """0 <= i < n"""
        if self.data[i] < 0:
            return i
        self.data[i] = self.root(self.data[i])
        return self.data[i]

    def connected(self, i, j):
        return self.root(i) == self.root(j)

    def groupsize(self, i):
        return self.sizes[self.root(i)]

    def roots(self):
        """O(n)"""
        return [i for i, v in enumerate(self.data) if v < 0]

    def unite(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if i == j:
            return
        if (-self.data[i]) < (-self.data[j]):
            self.data[i] = j
            self.sizes[j] += self.sizes[i]
        elif (-self.data[i]) > (-self.data[j]):
            self.data[j] = i
            self.sizes[i] += self.sizes[j]
        else:
            self.data[i] += -1
            self.data[j] = i
            self.sizes[i] += self.sizes[j]


N = int(input())
XY = []
XI = []
YI = []
for i in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    XI.append((x, i))
    YI.append((y, i))
XI.sort()
YI.sort()
DIJ = []
for i in range(N - 1):
    DIJ.append((XI[i+1][0] - XI[i][0], XI[i][1], XI[i+1][1]))
    DIJ.append((YI[i+1][0] - YI[i][0], YI[i][1], YI[i+1][1]))
DIJ.sort(reverse=True)
uf = UnionFind(N)
ans = 0
while len(DIJ):
    d, i, j = DIJ.pop()
    if uf.connected(i, j):
        continue
    uf.unite(i, j)
    ans += d
    if uf.groupsize(i) == N:
        break
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


import heapq
def prim_heap(n, edges):  # n: 最大の頂点番号+1, edges[頂点番号]=[[重み, 行き先],[重み, 行き先],...]. 無向グラフの場合は相方向有向グラフの表記にしておく。
    seen = [False] * n #True:不使用
    edgelist = []  # heapq
    for e in edges[0]:  # 頂点 0 から伸びる辺をすべて heapq に入れる。
        heapq.heappush(edgelist,(e, 0))  # 一応、どこから来たかの情報を持っておく。
    seen[0] = True  # 頂点 0 は見たと記録する。
    res_edges = []  # 辺を記録するためのリスト。
    res = 0  # 最小全域木の辺の重みの合計。
    while len(edgelist) != 0:
        minedge, start = heapq.heappop(edgelist)  # edgelist から最小の辺を1つ取り出す。
        if seen[minedge[1]]:  # その辺の行き先がすでに見た先だったら棄却して次へ。
            continue
        v = minedge[1]  # 行き先を v とする。
        seen[v] = True  # 頂点 v は見たと記録する。
        for e in edges[v]:  # 頂点 v から伸びる辺すべてについて、もしその行き先を見ていなかったら heapq に追加する。
            if not seen[e[1]]:
                heapq.heappush(edgelist,(e, v))
        res_edges.append((start, v, minedge[0]))  # Edge: (from, to, weight)
        res += minedge[0]  # いま使った辺の重みを結果に加える。
    # print(res_edges)  # 最小全域木の辺を print する。
    # return res_edges  # 最小全域木の辺を返す。
    return res  # 最小全域木の全体の重みを返す。



def main(): 
    N = II()
    pos_li = []
    for i in range(N):
        x,y = LI()
        pos_li.append((x,y,i))
    edges = [[] for _ in range(N)]
    # # すべての頂点を結ぶグラフを作ってその最小全域木を取ると、時間が足りない（二重ループが O(10^10)）。
    # for i in range(N):
    #     for j in range(N):
    #         weight = min(abs(pos_li[i][0] - pos_li[j][0]), abs(pos_li[i][1] - pos_li[j][1]))
    #         edges[i].append([weight, j])
    #         edges[j].append([weight, i])
    # # なので、座標でソートして、最も近い4点のみへ辺を伸ばす。
    pos_li.sort(key=lambda x: x[0])
    for k in range(N-1):
        x1, y1, p1 = pos_li[k]
        x2, y2, p2 = pos_li[k+1]
        weight = abs(x1-x2)
        edges[p1].append([weight, p2])
        edges[p2].append([weight, p1])

    pos_li.sort(key=lambda x: x[1])
    for k in range(N-1):
        x1, y1, p1 = pos_li[k]
        x2, y2, p2 = pos_li[k+1]
        weight = abs(y1-y2)
        edges[p1].append([weight, p2])
        edges[p2].append([weight, p1])

    # print(edges)
    print(prim_heap(N, edges))

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


import heapq
def prim_heap(n, edges):  # n: 最大の頂点番号+1, edges[頂点番号]=[[重み, 行き先],[重み, 行き先],...]. 無向グラフの場合は相方向有向グラフの表記にしておく。
    seen = [False] * n #True:不使用
    edgelist = []  # heapq
    for e in edges[0]:  # 頂点 0 から伸びる辺をすべて heapq に入れる。
        heapq.heappush(edgelist,e)
    seen[0] = True  # 頂点 0 は見たと記録する。
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)  # edgelist から最小の辺を1つ取り出す。
        if seen[minedge[1]]:  # その辺の行き先がすでに見た先だったら棄却して次へ。
            continue
        v = minedge[1]  # 行き先を v とする。
        seen[v] = True  # 頂点 v は見たと記録する。
        for e in edges[v]:  # 頂点 v から伸びる辺すべてについて、もしその行き先を見ていなかったら heapq に追加する。
            if not seen[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]  # いま使った辺の重みを結果に加える。
    return res  # 最小全域木の全体の重みを出力する。



def main(): 
    N = II()
    pos_li = []
    for i in range(N):
        x,y = LI()
        pos_li.append((x,y,i))
    edges = [[] for _ in range(N)]
    # # すべての頂点を結ぶグラフを作ってその最小全域木を取ると、時間が足りない（二重ループが O(10^10)）。
    # for i in range(N):
    #     for j in range(N):
    #         weight = min(abs(pos_li[i][0] - pos_li[j][0]), abs(pos_li[i][1] - pos_li[j][1]))
    #         edges[i].append([weight, j])
    #         edges[j].append([weight, i])
    # # なので、座標でソートして、最も近い4点のみへ辺を伸ばす。
    pos_li.sort(key=lambda x: x[0])
    for k in range(N-1):
        x1, y1, p1 = pos_li[k]
        x2, y2, p2 = pos_li[k+1]
        weight = abs(x1-x2)
        edges[p1].append([weight, p2])
        edges[p2].append([weight, p1])

    pos_li.sort(key=lambda x: x[1])
    for k in range(N-1):
        x1, y1, p1 = pos_li[k]
        x2, y2, p2 = pos_li[k+1]
        weight = abs(y1-y2)
        edges[p1].append([weight, p2])
        edges[p2].append([weight, p1])

    # print(edges)
    print(prim_heap(N, edges))

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


import heapq
def prim_heap(n, edges):  # n: 最大の頂点番号+1, edges[頂点番号]=[[重み, 行き先],[重み, 行き先],...]. 無向グラフの場合は相方向有向グラフの表記にしておく。
    seen = [False] * n #True:不使用
    edgelist = []  # heapq
    for e in edges[0]:  # 頂点 0 から伸びる辺をすべて heapq に入れる。
        heapq.heappush(edgelist,e)
    seen[0] = True  # 頂点 0 は見たと記録する。
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)  # edgelist から最小の辺を1つ取り出す。
        if seen[minedge[1]]:  # その辺の行き先がすでに見た先だったら棄却して次へ。
            continue
        v = minedge[1]  # 行き先を v とする。
        seen[v] = True  # 頂点 v は見たと記録する。
        for e in edges[v]:  # 頂点 v から伸びる辺すべてについて、もしその行き先を見ていなかったら heapq に追加する。
            if not seen[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]  # いま使った辺の重みを結果に加える。
    return res  # 最小全域木の全体の重みを出力する。



def main(): 
    N = II()
    pos_li = []
    for i in range(N):
        x,y = LI()
        pos_li.append((x,y,i))
    edges = [[] for _ in range(N)]
    # # すべての頂点を結ぶグラフを作ってその最小全域木を取ると、時間が足りない（二重ループが O(10^10)）。
    # for i in range(N):
    #     for j in range(N):
    #         weight = min(abs(pos_li[i][0] - pos_li[j][0]), abs(pos_li[i][1] - pos_li[j][1]))
    #         edges[i].append([weight, j])
    #         edges[j].append([weight, i])
    # # なので、座標でソートして、最も近い4点のみへ辺を伸ばす。
    pos_li.sort(key=lambda x: x[0])
    for k in range(N-1):
        x1, y1, p1 = pos_li[k]
        x2, y2, p2 = pos_li[k+1]
        weight = abs(x1-x2)
        edges[p1].append([weight, p2])
        edges[p2].append([weight, p1])

    pos_li.sort(key=lambda x: x[1])
    for k in range(N-1):
        x1, y1, p1 = pos_li[k]
        x2, y2, p2 = pos_li[k+1]
        weight = abs(y1-y2)
        edges[p1].append([weight, p2])
        edges[p2].append([weight, p1])

    # print(edges)
    print(prim_heap(N, edges))


main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
from operator import itemgetter
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
class UnionFind():
    def __init__(self, n):
        self.par = [-1 for i in range(n)]

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.par[x] > self.par[y]: # merge technique
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x

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

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

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

edge = []
points.sort(key=itemgetter(0))
for i in range(1, n):
    dist = points[i][0] - points[i-1][0]
    edge.append((points[i][2], points[i-1][2], dist))
    edge.append((points[i-1][2], points[i][2], dist))

points.sort(key=itemgetter(1))
for i in range(1, n):
    dist = points[i][1] - points[i-1][1]
    edge.append((points[i][2], points[i-1][2], dist))
    edge.append((points[i-1][2], points[i][2], dist))

# print(edge)
edge.sort(key=itemgetter(2))
uf = UnionFind(n)
ans = 0
for u, v, cost in edge:
    if not uf.same(u, v):
        ans += cost
        uf.unite(u, v)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
class UnionFind():
    def __init__(self, n):
        self.par = [-1 for i in range(n)]

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.par[x] > self.par[y]: # merge technique
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x

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

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

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

edge = []
points.sort()
for i in range(1, n):
    dist = points[i][0] - points[i-1][0]
    edge.append((points[i][2], points[i-1][2], dist))
    edge.append((points[i-1][2], points[i][2], dist))

points.sort(key=lambda x: x[1])
for i in range(1, n):
    dist = points[i][1] - points[i-1][1]
    edge.append((points[i][2], points[i-1][2], dist))
    edge.append((points[i-1][2], points[i][2], dist))

# print(edge)
edge.sort(key=lambda x: x[2])
uf = UnionFind(n)
ans = 0
for u, v, cost in edge:
    if not uf.same(u, v):
        ans += cost
        uf.unite(u, v)
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納　par[x] == x の時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0)
        self.rank = [0] * (n+1)
        # 各々の集合の要素数（根が代表して値を持っておく）
        self.count = [1] * (n+1)

    # 検索
    def find(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        # 根でないなら親の要素で再検索
        else:
            # 検索する過程で親を更新
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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


    # 同じ集合に属しているか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 属している集合の要素数
    def size(self,x):
        q = UnionFind.find(self,x)
        return self.count[q]
import sys
input = sys.stdin.readline
n = int(input())
data = [list(map(int,input().split()))+[i] for i in range(n)]

data.sort()
edge = []
append = edge.append
for i in range(1,n):
    append([data[i][0]-data[i-1][0],data[i][2],data[i-1][2]])
data.sort(key=lambda x:x[1])
for i in range(1,n):
    append([data[i][1]-data[i-1][1],data[i][2],data[i-1][2]])

edge.sort()
uf = UnionFind(n)
ans = 0
for x,y,z in edge:
    if not uf.same_check(y,z):
        uf.union(y,z)
        ans += x

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
xys = []
for i in range(N):
  x, y = map(int, input().split())
  xys.append((x, y))
Isx = sorted(range(N), key=lambda i: (xys[i][0], xys[i][1]))
Isy = sorted(range(N), key=lambda i: (xys[i][1], xys[i][0]))
#print(Isx)
#print(Isy)
M = set()
for i in range(1, N):
  p, q = Isx[i-1], Isx[i]
  a, b = xys[p]
  c, d = xys[q]
  cost = min(abs(a-c), abs(b-d))
  M.add((cost, p, q))
for i in range(1, N):
  p, q = Isy[i-1], Isy[i]
  a, b = xys[p]
  c, d = xys[q]
  cost = min(abs(a-c), abs(b-d))
  M.add((cost, p, q))
#print(M)
S = list(M)
S.sort(reverse=True)
#print(S)
r = 0
UF = list(range(N))
def par(m):
  if UF[m] == m:
    return m
  ret = par(UF[m])
  UF[m] = ret
  return ret
while S:
  cost, p, q = S.pop()
  i = par(p)
  j = par(q)
  if i != j:
    r += cost
    UF[i] = j
  #print(UF)
print(r)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


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


graph = [[] for i in range(n)]


coordinate_list.sort(key = lambda x: x[1][0])
for i in range(n - 1):
    cost = coordinate_list[i + 1][1][0] - coordinate_list[i][1][0]
    graph[coordinate_list[i][0]] += [(cost, coordinate_list[i+1][0])]
    graph[coordinate_list[i + 1][0]] += [(cost, coordinate_list[i][0])]


coordinate_list.sort(key = lambda x: x[1][1])
for i in range(n - 1):
    cost = coordinate_list[i + 1][1][1] - coordinate_list[i][1][1]
    graph[coordinate_list[i][0]] += [(cost, coordinate_list[i+1][0])]
    graph[coordinate_list[i + 1][0]] += [(cost, coordinate_list[i][0])]


is_used = [0] * n
que = []
ret = 0
heappush(que, (0, 0))


for i in range(n):
    while True:
        add_cost, add_v = heappop(que)
        if not is_used[add_v]:
            break
    is_used[add_v] = 1
    ret += add_cost
    for cost, to_v in graph[add_v]:
        if not is_used[to_v]:
            heappush(que, (cost, to_v))


print(ret)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

v = []

xy.sort(key=lambda x: x[1])
pi, px, py = xy[0]
for i in range(1, N) :
    ci, cx, cy = xy[i]
    v.append((min(cx-px, abs(cy-py)), pi, ci))
    pi, px, py = ci, cx, cy
    
xy.sort(key=lambda x: x[2])
pi, px, py = xy[0]
for i in range(1, N) :
    ci, cx, cy = xy[i]
    v.append((min(cy-py, abs(cx-px)), pi, ci))
    pi, px, py = ci, cx, cy

class UnionFind() :
    def __init__(self, N) :
        self.par = [-1] * N
        
    def root(self, x) :
        while self.par[x] >= 0:
            x = self.par[x]
        return x

    def unite(self, x,y) :
        rx = self.root(x)
        ry = self.root(y)

        if rx != ry :
            if self.par[rx] > self.par[ry] :
                self.par[rx] = ry
            else :
                if self.par[rx] == self.par[ry] :
                    self.par[rx] -= 1
                self.par[ry] = rx
    
    def same(self, x, y) :
        return self.root(x) == self.root(y)

uf = UnionFind(N)
counter = 0
s = 0

v.sort()
for v_ in v :
    c, a, b = v_
    if not uf.same(a, b) :
        uf.unite(a, b)
        counter += 1
        s += c
        if counter == N - 1 :
            break
            
print(s)

Submission status: Accepted

Solution code:
from scipy.sparse import*;N=int(input());Z=[[i]+list(map(int,input().split()))for i in range(N)]
def X(k):Z.sort(key=lambda a:a[k]);return{(min(abs(b-e),abs(c-f)),a,d)for(a,b,c),(d,e,f)in zip(Z,Z[1:])}
d,*x=zip(*X(1)|X(2));print(int(csgraph.minimum_spanning_tree(csr_matrix((d,x),(N,N))).sum()))

Submission status: Accepted

Solution code:
from scipy.sparse import*;N=int(input());Z=[[i]+list(map(int,input().split()))for i in range(N)];P=set()
for j in[1,2]:
 Z.sort(key=lambda a:a[j])
 for i in range(1,N):a,b,c=Z[i-1];d,e,f=Z[i];P.add((min(abs(e-b),abs(f-c)),a,d))
d,i,j=zip(*P);print(int(csgraph.minimum_spanning_tree(csr_matrix((d,(i,j)),(N,N))).sum()))

Submission status: Accepted

Solution code:
from scipy.sparse import*;N=int(input());Z=[[i]+list(map(int,input().split()))for i in range(N)];P=set()
for j in[1,2]:
 Z.sort(key=lambda a:a[j])
 for i in range(1,N):
  a,b,c=Z[i-1]
  d,e,f=Z[i]
  P.add((min(abs(e-b),abs(f-c)),a,d))
d,i,j=zip(*P);print(int(csgraph.minimum_spanning_tree(csr_matrix((d,(i,j)),(N,N))).sum()))

Submission status: Accepted

Solution code:
from scipy.sparse import*;N=int(input());Z=[[i]+list(map(int,input().split()))for i in range(N)];P=set()
for j in[1,2]:Z.sort(key=lambda a:a[j]);P|={(min(abs(Z[i][1]-Z[i-1][1]),abs(Z[i][2]-Z[i-1][2])),Z[i-1][0],Z[i][0])for i in range(1,N)}
d,i,j=zip(*P);print(int(csgraph.minimum_spanning_tree(csr_matrix((d,(i,j)),(N,N))).sum()))

Submission status: Accepted

Solution code:
from scipy.sparse import *;N=int(input());Z=[[i]+list(map(int,input().split())) for i in range(N)];P=set()
for j in [1,2]:Z.sort(key=lambda a:a[j]);P|={(min(abs(Z[i][1]-Z[i-1][1]),abs(Z[i][2]-Z[i-1][2])),Z[i-1][0],Z[i][0]) for i in range(1,N)}
d,i,j=zip(*P);print(int(csgraph.minimum_spanning_tree(csr_matrix((d,(i,j)),(N,N))).sum()))

Submission status: Accepted

Solution code:
from scipy.sparse import *;N=int(input());Z=[[i]+list(map(int,input().split())) for i in range(N)];P=set()
for j in [1,2]:
 Z.sort(key=lambda a:a[j])
 for i in range(1,N):
  a,b,c=Z[i-1]
  d,e,f=Z[i]
  P.add((min(abs(e-b),abs(f-c)),a,d))
d,i,j=zip(*P);print(int(csgraph.minimum_spanning_tree(csr_matrix((d,(i,j)),(N,N))).sum()))

Submission status: Accepted

Solution code:
from scipy.sparse import *
N=int(input())
Z=[[i]+list(map(int,input().split())) for i in range(N)]
P=set()
for j in [1,2]:
 Z.sort(key=lambda a:a[j])
 for i in range(1,N):
  a,b,c=Z[i-1]
  d,e,f=Z[i]
  P.add((min(abs(e-b),abs(f-c)),a,d))
d,i,j=zip(*P)
print(int(csgraph.minimum_spanning_tree(csr_matrix((d,(i,j)),(N,N))).sum()))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import coo_matrix

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

P = set()
for j in [1, 2]:
  iXY.sort(key=lambda a: a[j])
  for i in range(1, N):
    i0, x0, y0 =  iXY[i - 1]
    i1, x1, y1 =  iXY[i]
    P.add((min(abs(x1 - x0), abs(y1 - y0)), i0, i1))

d, i, j = zip(*P)
G = coo_matrix((d, (i, j)), shape=(N, N))
mst = minimum_spanning_tree(G)
print(int(mst.sum()))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix

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

P = set()
for j in [1, 2]:
  iXY.sort(key=lambda a: a[j])
  for i in range(1, N):
    i0, x0, y0 =  iXY[i - 1]
    i1, x1, y1 =  iXY[i]
    P.add((min(abs(x1 - x0), abs(y1 - y0)), i0, i1))

d, i, j = zip(*P)
G = csr_matrix((d, (i, j)), shape=(N, N))
mst = minimum_spanning_tree(G)
print(int(mst.sum()))

Submission status: Accepted

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

N = int(input())
Vx = [None] * N
Vy = [None] * N
for i in range(N):
    x, y = map(int, input().split())
    Vx[i] = (i, x)
    Vy[i] = (i, y)
Vx.sort(key=lambda v: v[1])
Vy.sort(key=lambda v: v[1])
E = defaultdict(list)
for j in range(N-1):
    E[Vx[j][0]].append((Vx[j+1][1] - Vx[j][1], Vx[j+1][0]))
    E[Vx[j+1][0]].append((Vx[j+1][1] - Vx[j][1], Vx[j][0]))
    E[Vy[j][0]].append((Vy[j + 1][1] - Vy[j][1], Vy[j + 1][0]))
    E[Vy[j+1][0]].append((Vy[j + 1][1] - Vy[j][1], Vy[j][0]))
used = [False] * N

# def prim
ans = 0
q = []
heappush(q, (0, 0))
while q:
    dist, now = heappop(q)
    if used[now]:
        continue
    used[now] = True
    ans += dist
    for w, nxt in E[now]:
        if not used[nxt]:
            heappush(q, (w, nxt))
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

G = [set() for _ in range(N)]
for k in [1, 2]:
  iXY.sort(key=lambda a: a[k])
  for i in range(1, N):
    i0 = iXY[i - 1][0]
    i1 = iXY[i][0]
    G[i0].add((i1))
    G[i1].add((i0))

Q = [(0, 0)]
B = set()
a = 0
iXY.sort()

while True:
  d, v = heapq.heappop(Q)
  while v in B:
     d, v = heapq.heappop(Q)
  a += d
  B.add(v)
  if len(B) == N:
    break
  for i in G[v]:
    if i not in B:
      heapq.heappush(Q, (min(abs(iXY[v][1] - iXY[i][1]), abs(iXY[v][2] - iXY[i][2])), i))
print(a)

Submission status: Accepted

Solution code:
import heapq

N = int(input())
iXY = [[i] + list(map(int, input().split())) for i in range(N)]
G = [set() for _ in range(N)]

iXY.sort(key=lambda a: a[1])
for i in range(1, N):
  i0, x0, y0 = iXY[i - 1]
  i1, x1, y1 = iXY[i]
  G[i0].add((i1))
  G[i1].add((i0))

iXY.sort(key=lambda a: a[2])
for i in range(1, N):
  i0, x0, y0 = iXY[i - 1]
  i1, x1, y1 = iXY[i]
  G[i0].add((i1))
  G[i1].add((i0))

Q = [(0, 0)]
B = set()
a = 0
iXY.sort()

while True:
  d, v = heapq.heappop(Q)
  while v in B:
     d, v = heapq.heappop(Q)
  a += d
  B.add(v)
  if len(B) == N:
    break
  for i in G[v]:
    if i not in B:
      heapq.heappush(Q, (min(abs(iXY[v][1] - iXY[i][1]), abs(iXY[v][2] - iXY[i][2])), i))
print(a)

Submission status: Accepted

Solution code:
# クラスカル法
class Kruskal_UnionFind():
    # 無向グラフであるという前提に注意
    def __init__(self, N):
        self.edges = []
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

    def add(self, u, v, d):
        """
        u = from, v = to, d = cost
        """
        self.edges.append([u, v, d])

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

    def Kruskal(self):
        """
        return: 最小全域木のコストの和
        """
        edges = sorted(self.edges, key=lambda x: x[2])  # costでself.edgesをソートする
        res = 0
        for e in edges:
            if not self.same(e[0], e[1]):
                self.unite(e[0], e[1])
                res += e[2]
        return res

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

Krus = Kruskal_UnionFind(N)

xy.sort(key=lambda x: x[0])
x_cost = [[xy[i-1][2], xy[i][2], abs(xy[i-1][0] - xy[i][0])] for i in range(1, N)]
xy.sort(key=lambda x: x[1])
y_cost = [[xy[i-1][2], xy[i][2], abs(xy[i-1][1] - xy[i][1])] for i in range(1, N)]

for i in range(N-1):
    a, b, w = x_cost[i]
    Krus.add(a, b, w)
    a, b, w = y_cost[i]
    Krus.add(a, b, w)

ans = Krus.Kruskal()

print(ans)

Submission status: Accepted

Solution code:
import heapq

N = int(input())
cities = [0 for _ in range(N)]

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

edges = [[] for _ in range(N)]

cities.sort(key=lambda A : A[1])
for i in range(N - 1):
    a, xFrom, yFrom = cities[i]
    b, xTo, yTo = cities[i + 1]
    cost = min(abs(xFrom - xTo), abs(yFrom - yTo))

    edges[a].append((cost, b))
    edges[b].append((cost, a))

cities.sort(key=lambda A : A[2])
for i in range(N - 1):
    a, xFrom, yFrom = cities[i]
    b, xTo, yTo = cities[i + 1]
    cost = min(abs(xFrom - xTo), abs(yFrom - yTo))

    edges[a].append((cost, b))
    edges[b].append((cost, a))

vertex = set([0])
newEdge = []
que = []

for cost, to in edges[0]:
    heapq.heappush(que, (cost, to))

ans = 0
while len(vertex) < N:
    cost, now = heapq.heappop(que)
    if now in vertex:
        continue
    ans += cost
    vertex.add(now)
    for c, to in edges[now]:
        if not to in vertex:
            heapq.heappush(que, (c, to))

print(ans)

Submission status: Accepted

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

N = int(input())
xy = [[int(i) for i in input().split()] for j in range(N)]

xsort_n = sorted(range(N), key=lambda n:xy[n][0])
ysort_n = sorted(range(N), key=lambda n:xy[n][1])
neighbours = defaultdict(list)

for i in range(N-1):
    x1 = xsort_n[i]
    x2 = xsort_n[i+1]
    xd = xy[x2][0] - xy[x1][0]
    y1 = ysort_n[i]
    y2 = ysort_n[i+1]
    yd = xy[y2][1] - xy[y1][1]
    neighbours[x1].append((x2, xd))
    neighbours[x2].append((x1, xd))
    neighbours[y1].append((y2, yd))
    neighbours[y2].append((y1, yd))

is_used = [0] * N
h = []
heappush(h, (0, 0))
result = 0

while h:
    d, n = heappop(h)
    if is_used[n]:
        continue
    result += d
    is_used[n] = 1
    for ni, nd in neighbours[n]:
        if not is_used[ni]:
            heappush(h, (nd, ni))

print(result)