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: Wrong Answer

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)

c = np.array(c, dtype=int)
graph = csr_matrix((c, (u, v)), shape=(n, n), dtype=int)
mst = minimum_spanning_tree(graph, overwrite=True).astype(int)
ans = mst.sum()
print(ans)

Submission status: Wrong Answer

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)

c = np.array(c, dtype=np.int64)
graph = csr_matrix((c, (u, v)), shape=(n, n), dtype=np.int64)
mst = minimum_spanning_tree(graph, overwrite=True).astype(np.int64)
ans = mst.sum()
print(ans)

Submission status: Wrong Answer

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)), shape=(n, n), dtype=np.int64)
mst = minimum_spanning_tree(graph, overwrite=True).astype(np.int64)
ans = mst.sum()
print(ans)

Submission status: Wrong Answer

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)), shape=(n, n))
mst = minimum_spanning_tree(graph, overwrite=True).astype(np.int64)
ans = mst.sum()
print(ans)

Submission status: Wrong Answer

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
        g[t] = g[s]
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

def prim():
    used = [1] * n
    used[0] = 0
    lis = []
    res = 0
    
    for q in edge[0]:
        heapq.heappush(lis,q)
        
    while lis:
        minedge = heapq.heappop(lis)
        
        if used[minedge[1]] == 0:
            continue

        v = minedge[1]
        used[v] = 0

        for q in edge[v]:
            if used[q[1]] == 1:
                heapq.heappush(lis , q )
        res += minedge[0]
    return res

n = int(input())
edge = [[] for _ in range(n)]
xsort = [[0]*2 for _ in range(n)]
ysort = [[0]*2 for _ in range(n)]

for i in range(n):
    x ,y = map(int,input().split())
    xsort[i][0] = x
    ysort[i][0] = y
    xsort[i][1] = i
    ysort[i][1] = i
xsort.sort()
ysort.sort()

for i in range(n-2):
    edge[xsort[i][1] -1].append([xsort[i+1][0] - xsort[i][0] , xsort[i+1][1] -1])
    edge[xsort[i+1][1] -1].append([xsort[i+2][0] - xsort[i+1][0] , xsort[i+2][1] -1])
    edge[xsort[i+1][1] -1].append([xsort[i+1][0] - xsort[i][0] , xsort[i][1] -1])
    edge[xsort[i+2][1] -1].append([xsort[i+2][0] - xsort[i+1][0] , xsort[i+1][1] -1])
    edge[ysort[i][1] -1].append([ysort[i+1][0] - ysort[i][0] , ysort[i+1][1] -1])
    edge[ysort[i+1][1] -1].append([ysort[i+2][0] - ysort[i+1][0] , ysort[i+2][1] -1])
    edge[ysort[i+1][1] -1].append([ysort[i+1][0] - ysort[i][0] , ysort[i][1] -1])
    edge[ysort[i+2][1] -1].append([ysort[i+2][0] - ysort[i+1][0] , ysort[i+1][1] -1])
    
print(prim())

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush, heapify

def find(x):
    if parents[x] < 0:
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]
def union(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return
    if parents[x] > parents[y]:
        x, y = y, x
    parents[x] += parents[y]
    parents[y] = x

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

N = int(input())

verticies_x = []
verticies_y = []

for i in range(N):
    x, y = map(int, input().split())
    verticies_x.append((x,i))
    verticies_y.append((y,i))
verticies_x.sort()    
verticies_y.sort()

edge = []

for i in range(N-1):
    tmp_x = verticies_x[i+1][0] - verticies_x[i][0]
    tmp_y = verticies_y[i+1][0] - verticies_y[i][0]
    heappush(edge, (tmp_x, verticies_x[i][1], verticies_x[i+1][1]))
    heappush(edge, (tmp_y, verticies_y[i][1], verticies_y[i+1][1]))

ans = 0
parents = [-1] * N
while edge:
    cost, s, g = heappop(edge)
    if same(s,g):      
        continue
    else:
        union(s,g)
        ans += cost
        print(cost,s,g)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush, heapify

class UnionFind:
    def __init__(self, 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):
    x,y=map(int,input().split())
    X.append([x,i])
    Y.append([y,i])
 
X.sort()
Y.sort()
edge=[]
for i in range(1,N):
    edge.append([X[i][0]-X[i-1][0],X[i-1][1],X[i][1]])
    edge.append([Y[i][0]-Y[i-1][0],Y[i-1][1],Y[i][1]])
edge.sort()

ans = 0
uf = UnionFind(N)
for cost, s, g in edge:
    if uf.same(s,g):      
        continue
    else:
        uf.union(s,g)
        ans += cost
        print(cost,s,g)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

class UnionFind:
    def __init__(self, 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())

verticies_x = []
verticies_y = []

for i in range(N):
    x, y = map(int, input().split())
    verticies_x.append((x,i))
    verticies_y.append((y,i))
verticies_x.sort()    
verticies_y.sort()

edge = []

for i in range(N-1):
    tmp_x = verticies_x[i+1][0] - verticies_x[i][0]
    tmp_y = verticies_y[i+1][0] - verticies_y[i][0]
    heappush(edge, (tmp_x, verticies_x[i][1], verticies_x[i+1][1]))
    heappush(edge, (tmp_y, verticies_y[i][1], verticies_y[i+1][1]))

ans = 0
uf = UnionFind(N)
while edge:
    cost, s, g = heappop(edge)
    if uf.same(s,g):      
        continue
    else:
        uf.union(s,g)
        ans += cost
        print(cost,s,g)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush, heapify

class UnionFind:
    def __init__(self, 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())

verticies_x = []
verticies_y = []

for i in range(N):
    x, y = map(int, input().split())
    verticies_x.append((x,i))
    verticies_y.append((y,i))
verticies_x.sort()    
verticies_y.sort()

edge = []

for i in range(N-1):
    tmp_x = verticies_x[i+1][0] - verticies_x[i][0]
    tmp_y = verticies_y[i+1][0] - verticies_y[i][0]
    heappush(edge, (tmp_x, verticies_x[i][1], verticies_x[i+1][1]))
    heappush(edge, (tmp_y, verticies_y[i][1], verticies_y[i+1][1]))

ans = 0
uf = UnionFind(N)
while edge:
    cost, s, g = heappop(edge)
    if uf.same(s,g):      
        continue
    else:
        uf.union(s,g)
        ans += cost
        print(cost,s,g)
print(ans)

Submission status: Wrong Answer

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

n = int(input())
XY = [tuple(map(int, input().split())) for _ in range(n)]
X, Y = zip(*XY)
L_to_R = sorted([(x, i) for i, x in enumerate(X)])
D_to_U = sorted([(y, i) for i, y in enumerate(Y)])

A, B, C = [], [], []
for i in range(n-1):
  x1, num1 = L_to_R[i]
  x2, num2 = L_to_R[i+1]
  A.append(num1)
  B.append(num2)
  C.append(x2-x1)
  y1, num1 = D_to_U[i]
  y2, num2 = D_to_U[i+1]
  A.append(num1)
  B.append(num2)
  C.append(y2-y1)

csr = csr_matrix((C, (A, B)), shape=(n, n))
mst = minimum_spanning_tree(csr, True)
ans = mst.sum()
print(int(ans+.5))

Submission status: Wrong Answer

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

n = int(input())
XY = [tuple(map(int, input().split())) for _ in range(n)]
X, Y = zip(*XY)
L_to_R = sorted([(x, i) for i, x in enumerate(X)])
D_to_U = sorted([(y, i) for i, y in enumerate(Y)])

A, B, C = [], [], []
for i in range(n-1):
  x1, num1 = L_to_R[i]
  x2, num2 = L_to_R[i+1]
  A.append(num1)
  B.append(num2)
  C.append(x2-x1)
  y1, num1 = D_to_U[i]
  y2, num2 = D_to_U[i+1]
  A.append(num1)
  B.append(num2)
  C.append(y2-y1)

csr = csr_matrix((C, (A, B)), shape=(n, n))
mst = minimum_spanning_tree(csr, True)
ans = mst.sum()
print(int(ans))

Submission status: Wrong Answer

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

n = int(input())
XY = [tuple(map(int, input().split())) for _ in range(n)]
X, Y = zip(*XY)
L_to_R = sorted([(x, i) for i, x in enumerate(X)])
D_to_U = sorted([(y, i) for i, y in enumerate(Y)])

A, B, C = [], [], []
for i in range(n-1):
  x1, num1 = L_to_R[i]
  x2, num2 = L_to_R[i+1]
  A.append(num1)
  B.append(num2)
  C.append(x2-x1)
  y1, num1 = D_to_U[i]
  y2, num2 = D_to_U[i+1]
  A.append(num1)
  B.append(num2)
  C.append(y2-y1)
  
csr = csr_matrix((C, (A, B)), shape=(n, n))
mst = minimum_spanning_tree(csr)
ans = mst.sum()
print(int(ans))

Submission status: Wrong Answer

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

Xsort=[]
Ysort=[]
for i in range(N):
    X,Y=map(int,input().split())
    Xsort.append([X,i])
    Ysort.append([Y,i])
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





def main(i):
    x,y=Nidxlst[i]
    lst=[]
    if x>0:
        a=Xsort[x-1][1]
        m=Xsort[x][0]-Xsort[x-1][0]
        if not uf.same(i,a):
            lst.append([m,a])
    if x<N-1:
        a=Xsort[x+1][1]
        m=Xsort[x+1][0]-Xsort[x][0]
        if not uf.same(i,a):
            lst.append([m,a])
    if y>0:
        a=Ysort[y-1][1]
        m=Ysort[y][0]-Ysort[y-1][0]
        if not uf.same(i,a):
            lst.append([m,a])
    if y<N-1:
        a=Ysort[y+1][1]
        m=Ysort[y+1][0]-Ysort[y][0]
        if not uf.same(i,a):
            lst.append([m,a])
    if lst:
        lst=sorted(lst,key=lambda x:x[0])
        uf.union(i,lst[0][1])
        return(lst[0][0])
value=0
uf=UnionFind(N)

for i in range(N):
    m=main(i)
    if m:
        value+=m
print(value)

Submission status: Wrong Answer

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

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={}
exit()
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: Wrong Answer

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())
XY=[list(map(int,input().split())) for i in range(N)]
Xsort=[]
Ysort=[]
for i in range(N):
    Xsort.append([XY[i][0],i])
    Ysort.append([XY[i][1],i])

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={}
exit()
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: Wrong Answer

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())
XY=[list(map(int,input().split()))+[i] for i in range(N)]
Xsort=sorted([[i[0],i[2]] for i in XY],key=lambda x:x[0])
Ysort=sorted([[i[1],i[2]] for i in XY],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={}
exit()
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: Wrong Answer

Solution code:
import sys
from collections import deque
import heapq
import bisect
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())
xy = [tuple([int(x) for x in input().strip().split()] + [n+1]) for n in range(N)]
x_sorted = sorted(xy)
y_sorted = sorted(xy, key=lambda x: x[1])
L = [deque([]) for _ in range(N)]
L[x_sorted[0][2]-1].append((x_sorted[1][2], x_sorted[1][0]-x_sorted[0][0]))
L[y_sorted[0][2]-1].append((y_sorted[1][2], y_sorted[1][1]-y_sorted[0][1]))
for n in range(1, N-1):
    L[x_sorted[n][2]-1].append((x_sorted[n-1][2], x_sorted[n][0]-x_sorted[n-1][0]))
    L[x_sorted[n][2]-1].append((x_sorted[n+1][2], x_sorted[n+1][0]-x_sorted[n][0]))
    L[y_sorted[n][2]-1].append((y_sorted[n-1][2], y_sorted[n][1]-y_sorted[n-1][1]))
    L[y_sorted[n][2]-1].append((y_sorted[n+1][2], y_sorted[n+1][1]-y_sorted[n][1]))
L[x_sorted[-1][2]-1].append((x_sorted[-2][2], x_sorted[-1][0]-x_sorted[-2][0]))
L[y_sorted[-1][2]-1].append((y_sorted[-2][2], y_sorted[-1][1]-y_sorted[-2][1]))


q = [(0, 1)]
cost = [float('inf')] * N

while q:
    c, p = heapq.heappop(q)
    if cost[p-1] <= c:
        continue
    cost[p-1] = c
    for np, nc in L[p-1]:
        if cost[np-1] > c + nc:
            heapq.heappush(q, (nc, np))

print(sum(cost))

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush


class UnionFind(object):

    def __init__(self, N):
        self.tree = [i for i in range(N)]
        self.rank = [0] * (N + 1)
        self.size = [1] * N  # 頂点iの属する連結成分の大きさ

    def find(self, x):
        while self.tree[x] != x:
            x = self.tree[x] = self.tree[self.tree[x]]  # 経路圧縮
        return x

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

        # ランクを考慮しない場合はどちらが親になっても良い
        if self.rank[x] < self.rank[y]:
            self.tree[x] = y
            self.size[y] += self.size[x]
        else:
            self.tree[y] = x
            self.size[x] += self.size[y]

        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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


def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))


N = I()
X = [None] * N
Y = [None] * N
for i in range(N):
    x, y = MI()
    X[i] = (x, i, x, y)
    Y[i] = (y, i, x, y)
X.sort()
Y.sort()

# ある頂点vから最小全域木に含まれる点をたどった先の頂点は、x軸方向で最も近いかy軸方向で最もvから近いはず
q = list()
for i in range(N - 1):
    for axis in [X, Y]:
        _, t0, x0, y0 = axis[i]
        _, t1, x1, y1 = axis[i + 1]
        cost = min(abs(x1 - x0), abs(y1 - y0))
        heappush(q, (cost, t0, t1))

# Kruskal法 := 最小コストの辺から順に見て、新たな頂点が仲間に入るなら加える
uf = UnionFind(N)
ans = 0
while len(q) > 0:
    cost, t0, t1 = heappop(q)
    if not uf.has_same_parent(t0, t1):
        uf.unite(t0, t1)
        ans += cost
print(ans)

Submission status: Wrong Answer

Solution code:
def find(i):
    j = i
    while j!=T[j][0]:
        j,T[j][0] = T[j][0],i
    T[i][0] = j
    return j
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        if T[rt0][1]==T[rt1][1]:
            T[rt0][1] += 1
        return rt0
    else:
        T[rt0][0] = rt1
        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)]
curL = -1
curR = 0
for j in range(N):
    a,i = A[j]
    if j>=curR:
        k = j+1
        while k<N and A[k][0]==a:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = A[curR][0]-a
        distX[i].append((d,A[curR][1]))
    if curL-1>=0:
        d = a-A[curL-1][0]
        distX[i].append((d,A[curL-1][1]))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    b,i = B[j]
    if j>=curR:
        k = j+1
        while k<N and B[k][0]==b:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = B[curR][0]-b
        distY[i].append((d,B[curR][1]))
    if curL-1>=0:
        d = b-B[curL-1][0]
        distY[i].append((d,B[curL-1][1]))
T = {i:[i,0] for i in range(N)}
for j in range(1,N):
    if A[j][0]==A[j-1][0]:
        union(find(A[j-1][1]),find(A[j][1]))
for j in range(1,N):
    if B[j][0]==B[j-1][0]:
        rt = find(B[j-1][1])
        rt0 = find(B[j][1])
        if rt!=rt0:
            union(rt,rt0)
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: Wrong Answer

Solution code:
def find(i):
    j = i
    while j!=T[j][0]:
        j = T[j][0]
    k = i
    while k!=T[k][0]:
        k,T[k][0] = T[k][0],j
    return T[i][0]
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        if T[rt0][1]==T[rt1][1]:
            T[rt0][1] += 1
        return rt0
    else:
        T[rt0][0] = rt1
        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)]
curL = -1
curR = 0
for j in range(N):
    a,i = A[j]
    if j>=curR:
        k = j+1
        while k<N and A[k][0]==a:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = A[curR][0]-a
        distX[i].append((d,A[curR][1]))
    if curL-1>=0:
        d = a-A[curL-1][0]
        distX[i].append((d,A[curL-1][1]))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    b,i = B[j]
    if j>=curR:
        k = j+1
        while k<N and B[k][0]==b:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = B[curR][0]-b
        distY[i].append((d,B[curR][1]))
    if curL-1>=0:
        d = b-B[curL-1][0]
        distY[i].append((d,B[curL-1][1]))
T = {i:[i,0] for i in range(N)}
for j in range(1,N):
    if A[j][0]==A[j-1][0]:
        union(find(A[j-1][1]),find(A[j][1]))
for j in range(1,N):
    if B[j][0]==B[j-1][0]:
        rt = find(B[j-1][1])
        rt0 = find(B[j][1])
        if rt!=rt0:
            union(rt,rt0)
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: Wrong Answer

Solution code:
import heapq
from bisect import bisect_left,bisect_right
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[1])
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[1])
B = sorted([(X[i][1],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
    flag = 0
    indx0 = bisect_left(A,(X[i][0],0))
    j = indx0
    while j<N:
        if A[j][0]==X[i][0]:
            if A[j][1]!=i and hist[A[j][1]]==1:
                hist[i] = 1
                flag = 1
                break
        else:break
        j += 1
    if flag==1:continue
    indy0 = bisect_left(B,(X[i][1],0))
    j =indy0
    while j<N:
        if B[j][0]==X[i][1]:
            if B[j][1]!=i and hist[B[j][1]]==1:
                hist[i] = 1
                flag = 1
                break
        else:break
        j += 1
    if flag==1:continue
    hist[i] = 1
    cnt += d
    j = indx0
    while j<N:
        if A[j][0]==X[i][0]:
            if A[j][1]!=i:
                hist[A[j][1]] = 1
        else:break
        j += 1
    if indx0>0:
        d0 = A[indx0][0]-A[indx0-1][0]
        j = A[indx0-1][1]
        if hist[j]==0:
            heapq.heappush(heap,(d0,j))
    indx1 = bisect_right(A,(X[i][0],N))
    if indx1<N:
        d1 = A[indx1][0]-A[indx1-1][0]
        j = A[indx1][1]
        if hist[j]==0:
            heapq.heappush(heap,(d1,j))
    j = indy0
    while j<N:
        if B[j][0]==X[i][1]:
            if B[j][1]!=i:
                hist[B[j][1]] = 1
        else:break
        j += 1
    if indy0>0:
        d0 = B[indy0][0]-B[indy0-1][0]
        j = B[indy0-1][1]
        if hist[j]==0:
            heapq.heappush(heap,(d0,j))
    indy1 = bisect_right(B,(X[i][1],N))
    if indy1<N:
        d1 = B[indy1][0]-B[indy1-1][0]
        j = B[indy1][1]
        if hist[j]==0:
            heapq.heappush(heap,(d1,j)) 
print(cnt)