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:
import sys
import heapq as hq
input = sys.stdin.readline
n = int(input())
xy = [list(map(int,input().split()))+[i+1] for i in range(n)]
x_xy = sorted(xy)
y_xy = sorted(xy,key = lambda x:x[1])
edge = [[] for i in range(n+1)]
for i in range(1,n):
  xf,v2 = x_xy[i][0],x_xy[i][2]
  xi,v1 = x_xy[i-1][0],x_xy[i-1][2]
  edge[v1].append([abs(xf-xi),v2])
  edge[v2].append([abs(xf-xi),v1])
  yf,v2 = y_xy[i][0],y_xy[i][2]
  yi,v1 = y_xy[i-1][0],y_xy[i-1][2]
  edge[v1].append([abs(yf-yi),v2])
  edge[v2].append([abs(yf-yi),v1])
edges = edge[1]
hq.heapify(edges)
connect = [0 for i in range(n+1)]
connect[1] = 1
ans = 0
while edges:
  cost,v2 = hq.heappop(edges)
  if connect[v2] == 1:
    continue
  ans += cost
  connect[v2] = 1
  for e in edge[v2]:
    hq.heappush(edges,e)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq as hq
input = sys.stdin.readline
n = int(input())
x_xy = []
y_xy = []
for i in range(n):
  x,y = map(int,input().split())
  x_xy.append([x,i+1])
  y_xy.append([y,i+1])
x_xy.sort()
y_xy.sort()

Submission status: Wrong Answer

Solution code:
import sys
import heapq as hq
input = sys.stdin.readline
n = int(input())
xy = [list(map(int,input().split()))+[i+1] for i in range(n)]
x_xy = sorted(xy)
y_xy = sorted(xy,key = lambda x:x[1])

Submission status: Wrong Answer

Solution code:
#クラスカル, union find, x,yでソートして隣接辺
import sys
import heapq
input = sys.stdin.readline

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

Edg = []
p1.sort()
for i in range(n):
    u = p1[i-1][2]
    v = p1[i][2]
    heapq.heappush(Edg, (min(abs(p0[u][0]-p0[v][0]), abs(p0[u][1]-p0[v][1])),u,v) )
#p2 = [pxy for pxy in p1]
p1.sort(key = lambda pp: pp[1])

for i in range(n):
    u = p1[i-1][2]
    v = p1[i][2]
    heapq.heappush(Edg, (min(abs(p0[u][0]-p0[v][0]), abs(p0[u][1]-p0[v][1])),u,v) )
   
#print(Edg)
tag = [i for i in range(n)]
cnt = n-1
ans = 0
while cnt:
    l,x,y = heapq.heappop(Edg)
    i,j = x,y
    while i != tag[i]:
        i = tag[i]
    while j != tag[j]:
        j = tag[j]
    if i != j:
        cnt -= 1
        ans += l
        #print(cnt)
        chng1 = []
        chng2 = []
        chng1.append(x)
        x = tag[x]
        chng2.append(y)
        y = tag[y]
        while x != tag[x]:
            chng1.append(x)
            x = tag[x]
        chng1.append(x)
        while y != tag[y]:
            chng2.append(y)
            y = tag[y]
        chng2.append(y)
        if len(chng1) < len(chng2):
            for x_ in chng1:
                tag[x_] = y
        else:
            for y_ in chng2:
                tag[y_] = x
print(cnt)

Submission status: Wrong Answer

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

def main():
    N = int(input())
    x,y = [],[]
    root = [[] for _ in range(N)]
    go = [True for _ in range(N)]
    for i in range(N):
        _x,_y = map(int,input().split())
        x.append((_x,i))
        y.append((_y,i))
        
    x.sort()
    y.sort()
    
    for i in range(N-1):
        dx = x[i+1][0] - x[i][0]
        dy = y[i+1][0] - y[i][0]
        root[x[i][1]].append((dx,x[i+1][1]))
        root[x[i+1][1]].append((dx,x[i][1]))
        root[y[i][1]].append((dy,y[i+1][1]))
        root[y[i+1][1]].append((dy,y[i][1]))
    
    ans = 0    
    queue = root[0]
    go[0] = False
    while queue:
        cost,following = heapq.heappop(queue)
        if not go[following]:
            continue
        go[following] = False
        for e in root[following]:
            if go[e[1]]:
                heapq.heappush(queue,e)
        ans += cost
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

    return 'error'
    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)

Submission status: Wrong Answer

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)
xy = np.transpose(xy)

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:]))
    return 'error'
    graph = csr_matrix((d, (a, b)), shape=(n, n))
    res = minimum_spanning_tree(graph)
    ans = np.sum(res)
    return int(ans)
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

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

xl = sorted(xl)
yl = sorted(yl)

import heapq
al = []
for i in range(n-1):
    al.append((abs(xl[i+1][0] - xl[i][0]), xl[i][1], xl[i+1][1]))
    al.append((abs(yl[i+1][0] - yl[i][0]), yl[i][1], yl[i+1][1]))

heapq.heapify(al)

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

uf = UnionFind(n)

ans = 0
for i in range(n-1):
    while True:
        c, a, b = heapq.heappop(al)
        a -= 1
        b -= 1
        if not uf.same(a, b):
            ans += c
            uf.union(a,b)
            break

print(ans)

Submission status: Wrong Answer

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

xl = sorted(xl)
yl = sorted(yl)

import heapq
al = []
for i in range(n-1):
    al.append((xl[i+1][0] - xl[i][0], xl[i][1], xl[i+1][1]))
    al.append((yl[i+1][0] - yl[i][0], yl[i][1], yl[i+1][1]))

heapq.heapify(al)

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

uf = UnionFind(n)

ans = 0
for i in range(n-1):
    while True:
        c, a, b = heapq.heappop(al)
        a -= 1
        b -= 1
        if not uf.same(a, b):
            ans += c
            uf.union(a,b)
            break

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy import sparse
from operator import itemgetter
import sys
input=sys.stdin.readline

n=int(input())
xy=[[i]+list(map(int,input().split())) for i in range(n)]
data=[]
row=[]
col=[]
for i in [1,2]:
    xy.sort(key=itemgetter(i))
    for i in range(n-1):
        i1,x1,y1=xy[i]
        i2,x2,y2=xy[i+1]
        data.append(min(abs(x1-x2),abs(y1-y2)))
        row.append(i1)
        col.append(i2)
        data.append(min(abs(x1-x2),abs(y1-y2)))
        row.append(i2)
        col.append(i1)
    
lst=sparse.csr_matrix((data,(row,col)),shape=(n,n))
ans=minimum_spanning_tree(lst)
print(int(ans.sum()))

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy import sparse
from operator import itemgetter
import sys
input=sys.stdin.readline

n=int(input())
xy=[[i]+list(map(int,input().split())) for i in range(n)]
data=[]
row=[]
col=[]
for i in [1,2]:
    xy.sort(key=itemgetter(i))
    for i in range(n-1):
        i1,x1,y1=xy[i]
        i2,x2,y2=xy[i+1]
        data.append(min(abs(x1-x2),abs(y1-y2)))
        row.append(i1)
        col.append(i2)
    
lst=sparse.csr_matrix((data,(row,col)),shape=(n,n))
ans=minimum_spanning_tree(lst)
print(int(ans.sum()))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

n=int(input())
xy=[]
yx=[]
for i in range(n):
    x,y=map(int,input().split())
    xy.append([x,y,i])
    yx.append([y,x,i])
xy.sort()
yx.sort()
data=sparse.lil_matrix((n,n))
for i in range(1,n):
    data[xy[i-1][2],xy[i][2]]=xy[i][0]-xy[i-1][0]
    data[xy[i][2],xy[i-1][2]]=xy[i][0]-xy[i-1][0]
    data[yx[i-1][2],yx[i][2]]=yx[i][0]-yx[i-1][0]
    data[yx[i][2],yx[i-1][2]]=yx[i][0]-yx[i-1][0]

Submission status: Wrong Answer

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

n=int(input())
xy=[]
yx=[]
for i in range(n):
    x,y=map(int,input().split())
    xy.append([x,y,i])
    yx.append([y,x,i])
xy.sort()
yx.sort()
data=sparse.lil_matrix((n,n))
for i in range(1,n):
    data[xy[i-1][2],xy[i][2]]=xy[i][0]-xy[i-1][0]
    data[xy[i][2],xy[i-1][2]]=xy[i][0]-xy[i-1][0]
    data[yx[i-1][2],yx[i][2]]=yx[i][0]-yx[i-1][0]
    data[yx[i][2],yx[i-1][2]]=yx[i][0]-yx[i-1][0]
ans=minimum_spanning_tree(data)
print(int(ans.sum()))

Submission status: Wrong Answer

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

N, *xy = map(int, read().split())
xy = np.array(xy, np.int64).reshape(N, 2)
x = xy[:, 0]
y = xy[:, 1]

town = np.arange(N)
arg_x = np.argsort(x)
arg_y = np.argsort(y)

edges_x = x[arg_x[1:]] - x[arg_x[:-1]]
town_x = town[arg_x]

edges_y = y[arg_y[1:]] - y[arg_y[:-1]]
town_y = town[arg_y]

edges = np.concatenate([edges_x, edges_y])
towns_1 = np.concatenate([town_x[:-1], town_y[:-1]])
towns_2 = np.concatenate([town_x[1:], town_y[1:]])

graph = coo_matrix((edges, (towns_1, towns_2)), shape=(N, N))
tree = minimum_spanning_tree(graph)
answer = int(tree.sum())

print(answer)

Submission status: Wrong Answer

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

N, *xy = map(int, read().split())
xy = np.array(xy, np.int64).reshape(N, 2)
x = xy[:, 0]
y = xy[:, 1]

town = np.arange(N)
arg_x = np.argsort(x)
arg_y = np.argsort(y)

edges_x = x[arg_x[1:]] - x[arg_x[:-1]]
town_x = town[arg_x]

edges_y = y[arg_y[1:]] - y[arg_y[:-1]]
town_y = town[arg_y]

edges = np.concatenate([edges_x, edges_y])
towns_1 = np.concatenate([town_x[1:], town_y[1:]])
towns_2 = np.concatenate([town_x[:-1], town_y[:-1]])

graph = coo_matrix((edges, (towns_1, towns_2)), shape=(N, N))
tree = minimum_spanning_tree(graph, overwrite=True)
answer = int(tree.sum())

print(answer)

Submission status: Wrong Answer

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

N, *xy = map(int, read().split())
xy = np.array(xy, np.int64).reshape(N, 2)
x = xy[:, 0]
y = xy[:, 1]

town = np.arange(N)
arg_x = np.argsort(x)
arg_y = np.argsort(y)

edges_x = x[arg_x[1:]] - x[arg_x[:-1]]
town_x = town[arg_x]

edges_y = y[arg_y[1:]] - y[arg_y[:-1]]
town_y = town[arg_y]

edges = np.concatenate([edges_x, edges_y])
towns_1 = np.concatenate([town_x[1:], town_y[1:]])
towns_2 = np.concatenate([town_x[:-1], town_y[:-1]])

graph = csr_matrix((edges, (towns_1, towns_2)), shape=(N, N))
tree = minimum_spanning_tree(graph, overwrite=True).astype(int)
answer = tree.sum()

print(answer)

Submission status: Wrong Answer

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

N, *xy = map(int, read().split())
xy = np.array(xy, np.int64).reshape(N, 2)

town = np.arange(N)
arg_x = np.argsort(xy[:, 0])
arg_y = np.argsort(xy[:, 1])

edges_x = xy[arg_x[1:], 0] - xy[arg_x[:-1], 0]
town_x = town[arg_x]

edges_y = xy[arg_y[1:], 1] - xy[arg_y[:-1], 1]
town_y = town[arg_y]

edges = np.concatenate([edges_x, edges_y])
towns_1 = np.concatenate([town_x[1:], town_y[1:]])
towns_2 = np.concatenate([town_x[:-1], town_y[:-1]])

graph = csr_matrix((edges, (towns_1, towns_2)), shape=(N, N))
tree = minimum_spanning_tree(graph, overwrite=True)
answer = int(tree.sum())

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
n = int(input())
v_ls = []
x_ls = []
y_ls = []
for j in range(n):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    v_ls.append((j, x, y))

graph = {i:[] for i in range(n)}
v_ls.sort(key=lambda x:x[1])
for i, v in enumerate(v_ls[:-1]):
    _from = v
    _to = v_ls[i + 1]
    diff = _to[1] - _from[1]
    graph[_from[0]].append((_to[0], diff))
    graph[_to[0]].append((_from[0], diff))

v_ls.sort(key=lambda x:x[2])
for i, v in enumerate(v_ls[:-1]):
    _from = v
    _to = v_ls[i + 1]
    diff = _to[2] - _from[2]
    graph[_from[0]].append((_to[0], diff))
    graph[_to[0]].append((_from[0], diff))

v_ls.sort(key=lambda x:x[0])
already = set()
cur = [(0, 0, 0)]
cost = 0
while len(cur) > 0:
    cur_cost, cur_ind, plus = heapq.heappop(cur)
    _, cur_x, cur_y = v_ls[cur_ind]
    if cur_ind in already:
        continue
    already.add(cur_ind)
    cost += plus
    for _next, next_cost in graph[cur_ind]:
        if _next in already:
            continue
        heapq.heappush(cur, (cur_cost + next_cost, _next, next_cost))
    if len(already) == n:
        break
print(cost)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
n = int(input())
v_ls = []
x_ls = []
y_ls = []
for i in range(n):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    v_ls.append((i, x, y))

graph = {i:[] for i in range(n)}
v_ls.sort(key=lambda x:x[1])
for i, v in enumerate(v_ls[:-1]):
    _from = v
    _to = v_ls[i + 1]
    diff = _to[1] - _from[1]
    graph[_from[0]].append((_to[0], diff))
    graph[_to[0]].append((_from[0], diff))

v_ls.sort(key=lambda x:x[2])
for i, v in enumerate(v_ls[:-1]):
    _from = v
    _to = v_ls[i + 1]
    diff = _to[2] - _from[2]
    graph[_from[0]].append((_to[0], diff))
    graph[_to[0]].append((_from[0], diff))

v_ls.sort(key=lambda x:x[0])
already = set()
cur = [(0, 0, 0)]
cost = 0
while len(cur) > 0:
    cur_cost, cur_ind, plus = heapq.heappop(cur)
    _, cur_x, cur_y = v_ls[cur_ind]
    if cur_ind in already:
        continue
    already.add(cur_ind)
    cost += plus
    for _next, next_cost in graph[cur_ind]:
        if _next in already:
            continue
        heapq.heappush(cur, (cur_cost + next_cost, _next, next_cost))
    if len(already) == n:
        break
print(cost)

Submission status: Wrong Answer

Solution code:
import heapq as hq

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

cx = sorted(c, key=lambda x: x[1])
cy = sorted(c, key=lambda x: x[2])

edge = [set() for i in range(N)] # edge[from][to] = weight

for i in range(1, N-1):
  edge[cx[i-1][0]].add((cx[i][1]-cx[i-1][1], cx[i][0]))
  edge[cx[i][0]].add((cx[i][1]-cx[i-1][1], cx[i-1][0]))

  edge[cx[i][0]].add((cx[i+1][1]-cx[i][1], cx[i+1][0]))
  edge[cx[i+1][0]].add((cx[i+1][1]-cx[i][1], cx[i][0]))
  
  edge[cy[i-1][0]].add((cy[i][2]-cy[i-1][2], cy[i][0]))
  edge[cy[i][0]].add((cy[i][2]-cy[i-1][2], cy[i-1][0]))

  edge[cy[i][0]].add((cy[i+1][2]-cy[i][2], cy[i+1][0]))
  edge[cy[i+1][0]].add((cy[i+1][2]-cy[i][2], cy[i][0]))
  

q = [(0, 0)]
used = [False] * N
un = 0
r = 0

while q and un < N:
  w, prev = hq.heappop(q)

  if used[prev]: continue
  
  used[prev] = True
  un += 1
  r += w
  
  for w, to in edge[prev]:
    if not used[to]:
      hq.heappush(q, (w, to))
print(r)

Submission status: Wrong Answer

Solution code:
import heapq as hq

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

cx = sorted(c, key=lambda x: x[1])
cy = sorted(c, key=lambda x: x[2])

edge = [{} for i in range(N)] # edge[from][to] = weight

def calcDist(c1, c2):
  return min(abs(c1[1]-c2[1]),abs(c1[2]-c2[2]))

for i in range(1, N-1):
  d1 = calcDist(cx[i-1], cx[i])
  edge[cx[i-1][0]][cx[i][0]] = min(edge[cx[i-1][0]].get(cx[i][0], float("inf")), d1)
  edge[cx[i][0]][cx[i-1][0]] = min(edge[cx[i][0]].get(cx[i-1][0], float("inf")), d1)

  d2 = calcDist(cx[i], cx[i+1])
  edge[cx[i][0]][cx[i+1][0]] = min(edge[cx[i][0]].get(cx[i+1][0], float("inf")), d2)
  edge[cx[i+1][0]][cx[i][0]] = min(edge[cx[i+1][0]].get(cx[i][0], float("inf")), d2)

  d3 = calcDist(cy[i-1], cy[i])
  edge[cy[i-1][0]][cy[i][0]] = min(edge[cy[i-1][0]].get(cy[i][0], float("inf")), d3)
  edge[cy[i][0]][cy[i-1][0]] = min(edge[cy[i][0]].get(cy[i-1][0], float("inf")), d3)

  d4 = calcDist(cy[i], cy[i+1])
  edge[cy[i][0]][cy[i+1][0]] = min(edge[cy[i][0]].get(cy[i+1][0], float("inf")), d4)
  edge[cy[i+1][0]][cy[i][0]] = min(edge[cy[i+1][0]].get(cy[i][0], float("inf")), d4)

q = [(0, 0)]
searched = set()
r = 0

while q and len(searched) < N:
  w, prev = hq.heappop(q)
  if prev in searched:
    continue
  else:
    searched.add(prev)
  r += w
  
  for to, w in edge[prev].items():
    if to not in searched:
      hq.heappush(q, (w, to))
print(r)

Submission status: Wrong Answer

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

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)

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

townx = sorted(town)
towny = sorted(town,key = lambda t : t[1])

heap = []
heapq.heapify(heap)

for i in range(N-1):
    heapq.heappush(heap,[abs(townx[i][0]-townx[i+1][0]),townx[i][2]-1,townx[i+1][2]-1])
    heapq.heappush(heap,[abs(towny[i][1]-towny[i+1][1]),towny[i][2]-1,towny[i+1][2]-1])

uf = UnionFind(N)
ans = 0

while heap:
    cost,t1,t2 = heapq.heappop(heap)
    if uf.same(t1,t2):
        continue
    uf.union(t1,t2)
    ans += cost
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = 100000
xlist = []
ylist = []
for i in range(N):
  x, y = [1, 2]
  xlist.append([x, i])
  ylist.append([y, i])

xroot = [[] for _ in range(N+1)]
yroot = [[] for _ in range(N+1)]

xlist.sort() # [x, ID]
ylist.sort() # [y, ID]

for i in range(N-1):
  x, xID = xlist[i]
  nextx, nextxID = xlist[i + 1]
  costx = nextx - x
  xroot[xID].append([costx, nextxID])
  xroot[nextxID].append([costx, xID])

  y, yID = ylist[i]
  nexty, nextyID = ylist[i + 1]
  costy = nexty - y
  yroot[yID].append([costy, nextyID])
  yroot[nextyID].append([costy, yID])
#print(xroot) # [cost, rootID]
#print(yroot)

hpop = heapq.heappop
hpush = heapq.heappush
data = [] # [val, ID]

visited = [False]*(N+1)
hpush(data, [0, 1])
ans = 0
while data:
  val, num = hpop(data)
  if visited[num] == False:
    visited[num] = True
    #print(val, num)
    ans += val
    for i in xroot[num]:
      if visited[i[1]] == False:
        hpush(data, i)
    for j in yroot[num]:
      if visited[j[1]] == False:
        hpush(data, j)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
for i in range(n):
    a,b=map(int,input().split())
    l.append([a,b])
#l.sort(key=lambda x:[x[0],x[1]])
mini=10**12
for j in range(n):
    ref=[min(abs(l[i][0]-l[j][0]),abs(l[i][1]-l[j][1])) for i in range(n)]
    ans= 0 
    #print(ref)
    ref.sort()
    for i in range(1,len(ref)):
        ans+=abs(ref[i]-ref[i-1])
    mini=min(mini,ans+ref[0])
print(mini)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
for i in range(n):
    a,b=map(int,input().split())
    l.append([a,b])
l.sort(key=lambda x:[x[0],x[1]])
ref=[min(abs(l[i][0]-l[0][0]),abs(l[i][1]-l[0][1])) for i in range(n)]
ans= 0 
#print(ref)
ref.sort()
for i in range(1,len(ref)):
    ans+=abs(ref[i]-ref[i-1])
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
for i in range(n):
    a,b=map(int,input().split())
    l.append([a,b])
l.sort(key=lambda x:[x[0],x[1]])
ref=[min(abs(l[i][0]-l[0][0]),abs(l[i][1]-l[0][1])) for i in range(n)]
ans= 0 
for i in range(1,len(ref)):
    ans+=abs(ref[i]-ref[i-1])
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted([[i]+list(map(int,input().split()))for i in range(n)],key=lambda x:x[1])
s=[]
for i in range(n-1):
    s.append((a[i+1][1]-a[i][1],a[i][0],a[i+1][0]))
a=sorted(a,key=lambda x:x[2])
for i in range(n-1):
    s.append((a[i+1][2]-a[i][2],a[i][0],a[i+1][0]))
s.sort()
t=[i for i in range(n)]
def f(x):
    if x==t[x]:
        return x
    t[x]=f(t[x])
    return t[x]
c=0
for i,j,h in s:
    j,h=f(j),f(h)
    if i!=j:
        t[j]=h
        c+=i
print(c)

Submission status: Wrong Answer

Solution code:
n=int(input())
lx=[]
ly=[]
for i in range(n):
    x,y=[int(j) for j in input().split()]
    lx.append((i,x,y))
    ly.append((i,x,y))
from operator import itemgetter
lx.sort(key=itemgetter(1))
ly.sort(key=itemgetter(2))
# 最小全域木
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
d=[]
ii=[]
jj=[]
for i in range(n-1):
    d.append(min(abs(lx[i+1][2]-lx[i][2]),abs(lx[i+1][1]-lx[i][1])))
    ii.append(lx[i][0])
    jj.append(lx[i+1][0])
    d.append(min(abs(ly[i+1][2]-ly[i][2]),abs(ly[i+1][1]-ly[i][1])))
    ii.append(ly[i][0])
    jj.append(ly[i+1][0])
d=np.array(d,dtype=int)
graph=csr_matrix((d,(ii,jj)),shape=(n,n))

tree = minimum_spanning_tree(graph,overwrite = True).astype(int)
print(tree.sum())

Submission status: Wrong Answer

Solution code:
n=int(input())
lx=[]
ly=[]
for i in range(n):
    x,y=[int(j) for j in input().split()]
    lx.append((i,x,y))
    ly.append((i,x,y))
from operator import itemgetter
lx.sort(key=itemgetter(1))
ly.sort(key=itemgetter(2))
# 最小全域木
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
d=[]
ii=[]
jj=[]
for i in range(n-1):
    d.append(min(abs(lx[i+1][2]-lx[i][2]),abs(lx[i+1][1]-lx[i][1])))
    ii.append(lx[i][0])
    jj.append(lx[i+1][0])
    d.append(min(abs(ly[i+1][2]-ly[i][2]),abs(ly[i+1][1]-ly[i][1])))
    ii.append(ly[i][0])
    jj.append(ly[i+1][0])
graph=csr_matrix((d,(ii,jj)),shape=(n,n))

tree = minimum_spanning_tree(graph,overwrite = True).astype(int)
print(tree.sum())

Submission status: Wrong Answer

Solution code:
n=int(input())
lx=[]
ly=[]
for i in range(n):
    x,y=[int(j) for j in input().split()]
    lx.append((i,x,y))
    ly.append((i,x,y))
from operator import itemgetter
lx.sort(key=itemgetter(1))
ly.sort(key=itemgetter(2))
# 最小全域木
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
d=[]
ii=[]
jj=[]
for i in range(n-1):
    d.append(lx[i+1][1]-lx[i][1])
    ii.append(lx[i][0])
    jj.append(lx[i+1][0])
    d.append(ly[i+1][2]-ly[i][2])
    ii.append(ly[i][0])
    jj.append(ly[i+1][0])
graph=csr_matrix((d,(ii,jj)),shape=(n,n))

tree = minimum_spanning_tree(graph,overwrite = True).astype(int)
print(tree.sum())

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from bisect import bisect_left
import heapq as hp
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    XY = [list(map(int, input().split())) for _ in range(N)]

    Xs = []
    Ys = []
    for i, (x, y) in enumerate(XY):
        Xs.append((i, x))
        Ys.append((i, y))
    Xs.sort(key=itemgetter(1))
    Ys.sort(key=itemgetter(1))

    Ix, X = zip(*Xs)
    Iy, Y = zip(*Ys)
    # Ix, Iy are indexes of XY

    # take nearest 4s
    graph = [[] for _ in range(N)]
    for i, (x, y) in enumerate(XY):
        nexts = set()
        ix = bisect_left(X, x)
        if ix != 0:
            nexts.add(Ix[ix-1])
        if ix != N-1:
            nexts.add(Ix[ix+1])
        
        iy = bisect_left(Y, y)
        if iy != 0:
            nexts.add(Iy[iy-1])
        if iy != N-1:
            nexts.add(Iy[iy+1])
        for n in nexts:
            d = min(abs(XY[n][0]-XY[i][0]), abs(XY[n][1]-XY[i][1]))
            graph[i].append((d, n))



    checked = [False for _ in range(N)]
    checked[0] = True 
    q = [] # しまっていく優先度付きキュー
    for d, n in graph[0]:
        hp.heappush(q, (d, n))
    ans = 0

    while q:
        nd, np = hp.heappop(q) # 一番距離が近いものを取ってくる
        if checked[np]: # 追加した後の残骸は見ない
            continue
        ans += nd
        checked[np] = True
        for d, p in graph[np]:
            if not checked[p]:
                hp.heappush(q, (d, p))

    print(ans)
            

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from bisect import bisect_left
import heapq as hp

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

Xs = []
Ys = []
for i, (x, y) in enumerate(XY):
    Xs.append((i, x))
    Ys.append((i, y))
Xs.sort(key=itemgetter(1))
Ys.sort(key=itemgetter(1))

Ix, X = zip(*Xs)
Iy, Y = zip(*Ys)
# Ix, Iy are indexes of XY

# take nearest 4s
graph = [[] for _ in range(N)]
for i, (x, y) in enumerate(XY):
    nexts = set()
    ix = bisect_left(X, x)
    if ix != 0:
        nexts.add(Ix[ix-1])
    if ix != N-1:
        nexts.add(Ix[ix+1])
    
    iy = bisect_left(Y, y)
    if iy != 0:
        nexts.add(Iy[iy-1])
    if iy != N-1:
        nexts.add(Iy[iy+1])
    for n in nexts:
        d = min(abs(XY[n][0]-XY[i][0]), abs(XY[n][1]-XY[i][1]))
        graph[i].append((d, n))



checked = [False for _ in range(N)]
checked[0] = True 
q = [] # しまっていく優先度付きキュー
for d, n in graph[0]:
    hp.heappush(q, (d, n))
ans = 0

while q:
    nd, np = hp.heappop(q) # 一番距離が近いものを取ってくる
    if checked[np]: # 追加した後の残骸は見ない
        continue
    ans += nd
    checked[np] = True
    for d, p in graph[np]:
        if not checked[p]:
            hp.heappush(q, (d, p))

print(ans)