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: Runtime Error

Solution code:
#最小全域木　プリム法
from heapq import *

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

#今回の問題では,高々xが隣のやつとyが隣のやつを全部考えればよし
#（詳しくは解説pdfより）
x_sort = sorted(xy, key=lambda x: x[0])
y_sort = sorted(xy, key=lambda x: x[1])

cost = [[]for _ in range(n+3)] #cost[i]にはi番目から(j,k)でj番目にコストkかかる
for i in range(n-1):
    cost[x_sort[i][2]].append((x_sort[i+1][2],x_sort[i+1][0]-x_sort[i][0]))
    cost[x_sort[i+1][2]].append((x_sort[i][2],x_sort[i+1][0]-x_sort[i][0]))

    cost[y_sort[i][2]].append((y_sort[i+1][2],y_sort[i+1][1]-y_sort[i][1]))
    cost[y_sort[i+1][2]].append((y_sort[i][2],y_sort[i+1][1]-y_sort[i][1]))


used=[False]*(n+3)#頂点が最小全域木にもうすでに含まれているかどうか
q=[]
#すでに最小全域木が決まっている部分からまだ決まっていない部分への辺をヒープで管理
#(a,b)でaには向かう先の頂点,bにはかかるコスト
#ヒープで小さいコストからとりだせる

#初期条件
#はじめはどこでもよいので０番目スタートとする(0番目だけではコストは0)
used[0] = True
ans = 0

#0番目からの辺をすべてヒープに挿入
for to,cst in cost[0]:
    heappush(q,(cst,to))

#すでに決まっている最小全域木部分からまだ決まっていない部分を貪欲的にひたすら追加する
#はじめは初期条件の通り
while(len(q)!=0):
    c,ver=heappop(q)
  #すでに決まっている部分から一番小さいコストの辺を取り出す
    if used[ver] == True:
        continue
  #もしすでに最小全域木部分であればやり直し
  #そうでなければコストの分を加算し、新しい頂点を最小全域木部分に追加する
    ans += c
    used[ver] = True
  #新しく追加した頂点からの辺をヒープに追加する
    for to,cst in cost[ver]:
        heappush(q,(cst,to))
　#これを貪欲的に繰り返すことでうまくいくらしい
print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
x = [(i, xy[i][0]) for i in range(n)]
y = [(i, xy[i][1]) for i in range(n)]

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

x_dif = [((x[i][0], x[i+1][0]), abs(x[i+1][1]-x[i][1])) for i in range(n-1)]
y_dif = [((y[i][0], y[i+1][0]), abs(y[i+1][1]-y[i][1])) for i in range(n-1)]

xy_dif = x_dif + y_dif
xy_dif.sort(key = lambda x:x[1])

p = [-1]*n

def root(x):
  if p[x]<0:
    return x
  p[x] = root(p[x])
  return p[x]

ans = 0
for ab, cost in xy_dif:
  a, b = ab
  #print(a, b, p[a], p[b], p)
  if root(a)!=root(b):
    p[root(a)] = root(b)
    ans += cost

print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
x = [(i, xy[i][0]) for i in range(n)]
y = [(i, xy[i][1]) for i in range(n)]

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

x_dif = [((x[i][0], x[i+1][0]), abs(x[i+1][1]-x[i][1])) for i in range(n-1)]
y_dif = [((y[i][0], y[i+1][0]), abs(y[i+1][1]-y[i][1])) for i in range(n-1)]

xy_dif = x_dif + y_dif
xy_dif.sort(key = lambda x:x[1])

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

def root(x):
  if p[x]==x:
    return x
  p[x] = root(p[x])
  return p[x]

ans = 0
for ab, cost in xy_dif:
  a, b = ab
  #print(a, b, p[a], p[b], p)
  if root(a)!=root(b):
    p[root(a)] = root(b)
    ans += cost

print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
x = [(i, xy[i][0]) for i in range(n)]
y = [(i, xy[i][1]) for i in range(n)]

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

x_dif = [((x[i][0], x[i+1][0]), abs(x[i+1][1]-x[i][1])) for i in range(n-1)]
y_dif = [((y[i][0], y[i+1][0]), abs(y[i+1][1]-y[i][1])) for i in range(n-1)]

xy_dif = x_dif + y_dif
xy_dif.sort(key = lambda x:x[1])

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

def root(x):
  if p[x]==x:
    return x
  p[x] = root(p[x])
  return p[x]

ans = 0
for i in range(2*(n-1)):
  ab, cost = xy_dif[i]
  a, b = ab
  #print(a, b, p[a], p[b], p)
  if root(a)!=root(b):
    p[root(a)] = root(b)
    ans += cost

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
x = [(i, xy[i][0]) for i in range(n)]
y = [(i, xy[i][1]) for i in range(n)]

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

x_dif = [((x[i][0], x[i+1][0]), abs(x[i+1][1]-x[i][1])) for i in range(n-1)]
y_dif = [((y[i][0], y[i+1][0]), abs(y[i+1][1]-y[i][1])) for i in range(n-1)]

xy_dif = x_dif + y_dif
xy_dif.sort(key = lambda x:x[1])

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

def root(x):
  if p[x]==x:
    return x
  p[x] = root(p[x])
  return p[x]

ans = 0
for i in range(2*(n-1)):
  ab, cost = xy_dif[i]
  a, b = ab
  #print(a, b, p[a], p[b], p)
  if root(a)!=root(b):
    p[root(a)] = root(b)
    ans += cost

print(ans)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

    N = int(input())
    xy = []
    for i in range(N):
        x,y = map(int, input().split())
        xy.append([x, y, i])
    x_sort.sort()
    #x_sort = sorted(xy, key=lambda x: x[0])
    y_sort = sorted(xy, key=lambda x: x[1])

    #[cost, 頂点1, 頂点2]
    cost = []
    for i in range(N-1):
        cost.append([x_sort[i+1][0]-x_sort[i][0], x_sort[i][2], x_sort[i+1][2]])
        cost.append([y_sort[i+1][1]-y_sort[i][1], y_sort[i][2], y_sort[i+1][2]])
    cost.sort()
    #cost = sorted(cost, key=lambda x: x[0])

    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    
    def unite(x,y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True
    
    def same(x,y):
        return find(x) == find(y)

    par = [-1]*N

    res = 0
    for c, v1, v2 in cost:
        if not same(v1, v2):
            unite(v1, v2)
            res += c
    print(res)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix
import numpy as np

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

x = []
y = []
for i, (ex, ey) in enumerate(xy):
    x.append([ex, i])
    y.append([ey, i])

x.sort()
y.sort()

u = []
v = []
c = []


def f(li):
    for (e1, i1), (e2, i2) in zip(li, li[1:]):
        dist = e2 - e1
        u.append(i1)
        v.append(i2)
        c.append(dist)


f(x)
f(y)

graph = csr_matrix((c, (u, v)))
mst = minimum_spanning_tree(graph).astype(np.int64)
ans = mst.sum()
print(ans)

Submission status: Runtime Error

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

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

x = []
y = []
for i, (ex, ey) in enumerate(xy):
    x.append([ex, i])
    y.append([ey, i])

x.sort()
y.sort()

u = []
v = []
c = []


def f(li):
    for (e1, i1), (e2, i2) in zip(li, li[1:]):
        dist = e2 - e1
        u.append(i1)
        v.append(i2)
        c.append(dist)


f(x)
f(y)

graph = csr_matrix((c, (u, v)))
mst = minimum_spanning_tree(graph)
ans = int(mst.sum())
print(ans)

Submission status: Runtime Error

Solution code:
import queue,sys,copy
sys.setrecursionlimit(10**7)
INF = 10**10
N = int(input())
x = [0 for _ in range(N)]
y = [0 for _ in range(N)]
for i in range(N):
    x[i], y[i] = map(int,input().split())
ix = [i for i in range(N)]
sort_x_ix = sorted(ix, key=lambda i:x[i])
sort_x = [x[i] for i in sort_x_ix]
sort_y_ix = sorted(ix, key=lambda i:y[i])
sort_y = [y[i] for i in sort_y_ix]

g = [i for i in range(N+1)]
def root(x):
    if g[x] == x : return x
    g[x] = root(g[x])
    return g[x]
q = []
for i in range(N-1):
    q.append((sort_x[i+1]-sort_x[i],sort_x_ix[i],sort_x_ix[i+1]))
    q.append((sort_y[i+1]-sort_y[i],sort_y_ix[i],sort_y_ix[i+1]))

q.sort()
ans = 0
cnt = N

for d,s,t in q:
    if cnt <= 1: break
    if root(s) != root(t):
        ans += d
        cnt -= 1
        root(g[t]) = g[s]
print(ans)

Submission status: Runtime Error

Solution code:
import queue
INF = 10**10
N = int(input())
x = [0 for _ in range(N)]
y = [0 for _ in range(N)]
for i in range(N):
    x[i], y[i] = map(int,input().split())
x_ix = [*range(N)]
y_ix = [*range(N)]
sort_x_ix = sorted(x_ix, key=lambda i:x[i])
sort_x = [x[i] for i in sort_x_ix]
sort_y_ix = sorted(y_ix, key=lambda i:y[i])
sort_y = [y[i] for i in sort_y_ix]

g = [i for i in range(N+1)]
def root(x):
    if g[x] == x : return x
    g[x] = root(g[x])
    return g[x]
q = []
for i in range(N-1):
    q.append((sort_x[i+1]-sort_x[i],sort_x_ix[i],sort_x_ix[i+1]))
    q.append((sort_y[i+1]-sort_y[i],sort_y_ix[i],sort_y_ix[i+1]))
q.sort()
ans = 0
cnt = N
for d,s,t in q:
    if cnt <= 1: break
    if root(s) != root(t):
        ans += d
        cnt -= 1
        g[root(t)] = g[s]

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
inf = float("inf")
N = int(input())
graph = np.full((N, N), inf)
xylist = [tuple([_] + list(map(int, input().split()))) for _ in range(N)]
xylist_xsort = sorted(xylist, key=lambda x: x[1])
xylist_ysort = sorted(xylist, key=lambda x: x[2])
for i in range(N-1):
    city1, x1, y1 = xylist_xsort[i]
    city2, x2, y2 = xylist_xsort[i+1]
    graph[city1][city2] = min(graph[city1][city2], abs(x1-x2), abs(y1-y2))
    graph[city2][city1] = min(graph[city1][city2], abs(x1-x2), abs(y1-y2))
    city1, x1, y1 = xylist_ysort[i]
    city2, x2, y2 = xylist_ysort[i+1]
    graph[city1][city2] = min(graph[city1][city2], abs(x1-x2), abs(y1-y2))
    graph[city2][city1] = min(graph[city1][city2], abs(x1-x2), abs(y1-y2))
mst = minimum_spanning_tree(csr_matrix(graph)).toarray().astype(int)
print(np.sum(mst))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
inf = float("inf")
N = int(input())
graph = np.full((N, N), inf)
xylist = [tuple([_] + list(map(int, input().split()))) for _ in range(N)]
xylist_xsort = sorted(xylist, key=lambda x: x[1])
xylist_ysort = sorted(xylist, key=lambda x: x[2])
for i in range(N-1):
    city1, x1, y1 = xylist_xsort[i]
    city2, x2, y2 = xylist_xsort[i+1]
    graph[city1][city2] = min(abs(x1-x2), abs(y1-y2))
    graph[city2][city1] = min(abs(x1-x2), abs(y1-y2))
    city1, x1, y1 = xylist_ysort[i]
    city2, x2, y2 = xylist_ysort[i+1]
    graph[city1][city2] = min(abs(x1-x2), abs(y1-y2))
    graph[city2][city1] = min(abs(x1-x2), abs(y1-y2))
mst = minimum_spanning_tree(csr_matrix(graph)).toarray().astype(int)
print(np.sum(mst))

Submission status: Runtime Error

Solution code:
"""



                                              ...(ggNMMMMMMMMMNg+...
                                       ..(gMH9"^`                ?"YMa,
                                  ..gMY"!                             7Mm.
                            ` ..gM9^                                    (Ma.`  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `
    `  `  `  `  `  `  `  ` .JM9^                           `              ?Ma
                       ..M#"`            .h       ..g   `     `             TN,
                     .d#^                 (b ..+MY"!               `         ?N.
   `             `..M"               ` `..&M#"!                               UN   `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `
               `.+#^           .b  `..MY"! ,N             `  `  `              M[
      `  `  ` .J#^              WJ+#"`     .gNe                     `  `       dF
             .M=             ..gHN    ..J#9= W/         `                      JF
            J@              ."`  d|.-"=      .N.    `                     `    MF
          .dF                    ,N         ..M#=           `  `  `           .M`    `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `  `
   `  `  .MD                      Up  ...k#M=     `  ..`             `      `.M^
         dF             `          ?"""!   ,p  ...gM9"`                 `   (#!
        .#                                 .MgMD^         `      `        .M"
        d]                             ..H94#N-TWMNag+J......J+ggMWY    .MD`
        M}                          .J9^  .M!,b           `         `.+M"
        M]                        T"`    .B`  vb                  .(MD`                                                          ` ...JgMH""""""MNa,`
        -N.                            .Mt     Up             ..gM"'                                                      ` ..(gMH9"^`             TN,
         ?N,                         .J@`       W[        ..gM"!                                                   `  ..JH#""!                      .Hp
          .Wm,                       (!         ,@    ..+MB=                                                   ` ..+MB"!                             .M[
            .TNa,                          .,  ...&MMY"^                                                   `...g#"!                                   ,N,
               .TWNg... `       `  ...    .MMH9"=`                                                     .gWH9"!                                         db
                    _7T"HMMNHQQkMM9"`M.   d\                                                                                                       ... .M,
                                     J]   #                     `   `              `   ` ` ................                       .......JggHMMM"""""`  dN
                                     .N. .#                               ` .....JggHMMH""""""""""7"""""""""""HMMMNNg+-....     7"""7?!                 .M[
                                      -b .#       `  `            ` ...gHM""""!`                                       ?7"T"HMMNg+....                   (N.
                                       vp M.             `  ...(gMMMMNNggg+(....                                                  _?""WMNNg...            M\
                                        ?bJ]           ..gMY""!`           `??""WMNJ,                                                      _7TWMNgJ..                 `  ...JggHHNag-,. `
                                         ,HN.   `   .+M9^                          _TMNJ,                                                          ?TWMNJ..   `  `  ..gM9"!          ?"Ma,
                                   `       ,H\   .(MD!                                 ?WNx.                                                             ?THNg.,..dB=                   .TN,
                                               .d#^                                       ?MN,                      Q,                                        ?TMm.                        TN,
                                       `     .d#^                         ..&MM;            .TN,                     .W,                                                                    .Mp `
                                    `      .(M=                      ..gMB@!                  .WN,                     ?b                                                                     Wb
                                         `.M"          ...   `    `  ?`   M.                    ?Me                     ?b                                                                     Mp
                                        .j#`      ..&MH"79                db                     .Mb                     ?b                                           ........                 ,M,
                                   `   .MF  ...gM#"4,                     .M,                      UN.                    ?b                                          `     ?""HNgJ,            JN
                                      .M$   (=`    M[           `          ,M] ..                   TN.                    Tb                                                      TD            M]
                                      dF           Jb                     .(HY""!                    UN.                    Wb                                                                   -N.
                                     .M`           ,M,              `   ,"^                           Mb                     Mc                                                                   M]
                                   ` dF             -W:..gMM@   `                                     ,M.                    ,N.                                           ""9Sa,.                J#
                                     M]         ` ..gM9"`           .m                                 M]                     H]                                                 `                ,M.
                                     M]    `     T=`                 M_                                db                     -N                                                                   M)
                                     MF                              M)                                J#                     ,M.                                         .aJ.....                 M]
                                     d@                       `   `  M)                                J#                     .M_                                               ?7TBNgJ,           M]
                                     J#    `                        .M+..(gx                           J#                     .M`                                                      ?^          M]
                                   ` ,M.        `         `          _7?!                              dF                     .#                                      .,                           M%
                                      M]                      `                                        MF                     JF                                   .(M"                           .M!
                                      JN.             `           `                                   .M}                                                    ` ..g#"`                             dF
                                       WN   `     `                                                   -#                                                ` ..JMY"!                                .M`
                                   `    WN.               `                       ...&gM]             MF                                           `  ..gM9^               ,NJ,                 .M^
                                         TN,                 `   `   `    ...JgMHB"=`               `(#                                       `  ..gMB"!                     ?TMMNggJ.........gM@`
                                          ?N,   `   `                ..gMW""!                       .M!                                     ..&MY"!                                 `?7"""""7!
                                   `       ?N,          `       ..&MB"`                           .dB`                               ` ..+MY"!
                                            (Ma.           ..+MB"!                              `.MD                          `  ...gMB"!
                                              7Ma.   `    .=`                                  .J#'                     `  `..JMH9"`
                                   `   `        ?HN,                                       ` .uM=                      ..+MY"^
                                                  .TMg,                                   .JM9!                ` ...gM""!
                                                     .TMN.,                            .+M9'                ..&M#"=`
                                   `    `   `            ?TMNg...            ..    ..gM"!            ...gMY"=`
                                                              ?"""HMMMMMMMY""=(.gMM9^         ...JkMB"^
                                                                          .T"9"!      ...JdM"""!
                                   `   `        `                          .....JdT"""!
                                           `        `   `                ?!`
"""

Submission status: Runtime Error

Solution code:
#from collections import *
#from itertools import *
#from bisect import *
from heapq import *
#import copy
#N=int(input())
#X,Y=map(int,input().split()))
#S=list(map(int,input().split()))
#S=[list(map(int,input().split())) for i in range(N)]

N=int(input())

Xsort=[]
Ysort=[]
for i in range(N):
    X,Y=map(int,input().split())
    Xsort.append([X,i])
    Ysort.append([Y,i])
uf=UnionFind(N)
Xsort=sorted(Xsort,key=lambda x:x[0])
Ysort=sorted(Ysort,key=lambda x:x[0])
Nidxlst=[[0,0] for i in range(N)]
for i in range(N):
    idx=Xsort[i][1]
    Nidxlst[idx][0]=i
    idx=Ysort[i][1]
    Nidxlst[idx][1]=i



value=0
x,y=Nidxlst[0]
ittenai=set([i for i in range(1,N)])

stack=[]
heapify(stack)
setm=set()
dic={}
def main(x,y):
    if x>0:
        a=Xsort[x-1][1]
        if a in ittenai:
            m=Xsort[x][0]-Xsort[x-1][0]
            heappush(stack,m)
            if m in setm :
                dic[m].append(a)
            else:
                setm.add(m)
                dic.update({m:[a]})
    if x<N-1:
        a=Xsort[x+1][1]
        if a in ittenai:
            m=Xsort[x+1][0]-Xsort[x][0]
            heappush(stack,m)
            if m in setm :
                dic[m].append(a)
            else:
                setm.add(m)
                dic.update({m:[a]})
    if y>0:
        a=Ysort[y-1][1]
        if a in ittenai:
            m=Ysort[y][0]-Ysort[y-1][0]
            heappush(stack,m)
            if m in setm :
                dic[m].append(a)
            else:
                setm.add(m)
                dic.update({m:[a]})
    if y<N-1:
        a=Ysort[y+1][1]
        if a in ittenai:
            m=Ysort[y+1][0]-Ysort[y][0]
            heappush(stack,m)
            if m in setm :
                dic[m].append(a)
            else:
                setm.add(m)
                dic.update({m:[a]})
main(x,y)
idle=10**9+1
value=0
while ittenai:
    m=heappop(stack)
    a=dic[m].pop()
    if a in ittenai:
        x,y=Nidxlst[a]
        main(x,y)
        ittenai.remove(a)
        value+=m

print(value)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import ipdb
import heapq
from bisect import bisect_left,bisect_right
INFTY = 10**10
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],-X[i][1],i) for i in range(N)],key=lambda x:x[1])
A = sorted([(X[i][0],-X[i][1],i) for i in range(N)],key=lambda x:x[0])
B = sorted([(X[i][1],-X[i][0],i) for i in range(N)],key=lambda x:x[1])
B = sorted([(X[i][1],-X[i][0],i) for i in range(N)],key=lambda x:x[0])
hist = [0 for _ in range(N)]
heap = [(0,0)]
cnt = 0
while heap:
    d,i = heapq.heappop(heap)
    if hist[i]==1:continue
    hist[i] = 1
    cnt += d
    indx0 = bisect_left(A,(X[i][0],-INFTY,0))
    j = indx0
    while j<N:
        if A[j][0]==X[i][0]:
            if A[j][2]!=i:
                hist[A[j][2]] = 1
        else:break
        j += 1
    if indx0>0:
        d0 = A[indx0][0]-A[indx0-1][0]
        j = A[indx0-1][2]
        if hist[j]==0:
            heapq.heappush(heap,(d0,j))
    indx1 = bisect_right(A,(X[i][0],1,N))
    if indx1<N:
        d1 = A[indx1][0]-A[indx1-1][0]
        j = A[indx1][2]
        if hist[j]==0:
            heapq.heappush(heap,(d1,j))
    indy0 = bisect_left(B,(X[i][1],-INFTY,0))
    j = indy0
    while j<N:
        if B[j][0]==X[i][1]:
            if B[j][2]!=i:
                hist[B[j][2]] = 1
        else:break
        j += 1
    if indy0>0:
        d0 = B[indy0][0]-B[indy0-1][0]
        j = B[indy0-1][2]
        if hist[j]==0:
            heapq.heappush(heap,(d0,j))
    indy1 = bisect_right(B,(X[i][1],1,N))
    if indy1<N:
        d1 = B[indy1][0]-B[indy1-1][0]
        j = B[indy1][2]
        if hist[j]==0:
            heapq.heappush(heap,(d1,j)) 
print(cnt)

Submission status: Runtime Error

Solution code:
import heapq
from bisect import bisect_left,bisect_right
INFTY = 10**10
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],-X[i][1],i) for i in range(N)],key=lambda x:x[1])
A = sorted([(X[i][0],-X[i][1],i) for i in range(N)],key=lambda x:x[0])
B = sorted([(X[i][1],-X[i][0],i) for i in range(N)],key=lambda x:x[1])
B = sorted([(X[i][1],-X[i][0],i) for i in range(N)],key=lambda x:x[0])
hist = [0 for _ in range(N)]
heap = [(0,0)]
cnt = 0
while heap:
    d,i = heapq.heappop(heap)
    if hist[i]==1:continue
    hist[i] = 1
    cnt += d
    indx0 = bisect_left(A,(X[i][0],-INFTY,0))
    j = indx0
    while j<N:
        if A[j][0]==X[i][0]:
            if A[j][2]!=i:
                hist[A[j][2]] = 1
        else:break
        j += 1
    if indx0>0:
        d0 = A[indx0][0]-A[indx0-1][0]
        j = A[indx0-1][2]
        if hist[j]==0:
            heapq.heappush(heap,(d0,j))
    indx1 = bisect_right(A,(X[i][0],1,N))
    if indx1<N:
        d1 = A[indx1][0]-A[indx1-1][0]
        j = A[indx1][2]
        if hist[j]==0:
            heapq.heappush(heap,(d1,j))
    indy0 = bisect_left(B,(X[i][1],-INFTY,0))
    j = indy0
    while j<N:
        if B[j][0]==X[i][1]:
            if B[j][2]!=i:
                hist[B[j][2]] = 1
        else B[j][0]!=X[i][1]:
            break
        j += 1
    if indy0>0:
        d0 = B[indy0][0]-B[indy0-1][0]
        j = B[indy0-1][2]
        if hist[j]==0:
            heapq.heappush(heap,(d0,j))
    indy1 = bisect_right(B,(X[i][1],1,N))
    if indy1<N:
        d1 = B[indy1][0]-B[indy1-1][0]
        j = B[indy1][2]
        if hist[j]==0:
            heapq.heappush(heap,(d1,j)) 
print(cnt)

Submission status: Runtime Error

Solution code:
import heapq

print(1)

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
X = []
Y = []
for x, y in XY:
  X.append((x, i + 1))
  Y.append((y, i + 1))
    
X.sort()
Y.sort()
 
graph = [[] for _ in range(N + 1)]
 
for i in range(N - 1):
  x1, a = X[i]
  x2, b = X[i + 1]
  graph[a].append((abs(x1 - x2), b))
  graph[b].append((abs(x1 - x2), a))
  y1, a = Y[i]
  y2, b = Y[i + 1]
  graph[a].append((abs(y1 - y2), b))
  graph[b].append((abs(y1 - y2), a))
    
check = [0] * (N + 1)
stack = []
heapq.heapify(stack)
for w, g in graph[1]:
  heapq.heappush(stack, (w, g))

check[1] = 1
answer = 0
cnt = 0

while cnt < N - 1:
  v, s = heapq.heappop(stack)
  if check[s] == 0:
    check[s] = 1
    answer += v
    cnt += v
    for w, g in graph[s]:
      if check[g] == 0:
        heapq.heappush(stack, (w, g))

print(answer)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import minimum_spanning_tree

n = int(sys.stdin.readline().rstrip())
xy = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(-1, 2).T

def main():
    indices1, indices2 = np.argsort(xy)
    res1 = xy[:, indices1]
    res2 = xy[:, indices2]
    d1 = np.absolute(res1[:, 1:] - res1[:, :-1])
    d1 = np.amin(d1, axis=0)
    d2 = np.absolute(res2[:, 1:] - res2[:, :-1])
    d2 = np.amin(d2, axis=0)
    d = np.concatenate((d1, d2))

    a = np.concatenate((indices1[:-1], indices2[:-1]))
    b = np.concatenate((indices1[1:], indices2[1:]))

    graph = coo_matrix((d, (a, b)), shape=(n, n)).tocsr()
    res = minimum_spanning_tree(graph, overwrite=True)
    return int(np.sum(res))
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree

n = int(sys.stdin.readline().rstrip())
xy = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(-1, 2).T

def main():
    indices1, indices2 = np.argsort(xy)
    res1 = xy[:, indices1]
    res2 = xy[:, indices2]
    d1 = np.absolute(res1[:, 1:] - res1[:, :-1])
    d1 = np.amin(d1, axis=0)
    d2 = np.absolute(res2[:, 1:] - res2[:, :-1])
    d2 = np.amin(d2, axis=0)
    d = np.concatenate((d1, d2))

    a = np.concatenate((indices1[:-1], indices2[:-1]))
    b = np.concatenate((indices1[1:], indices2[1:]))

    graph = csr_matrix((d, (a, b)), shape=(n, n))
    res = minimum_spanning_tree(graph, overwrite=True)
    ans = np.sum(res)
    return int(ans)
    
if __name__ == '__main__':
    ans = main()
    print(ans)