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 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:
#     ipdb.set_trace()
    d,i = heapq.heappop(heap)
    if hist[i]==1:continue
    hist[i] = 1
    cnt += d
    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:
                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))
    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:
                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)

Submission status: Wrong Answer

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

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:
#     ipdb.set_trace()
    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: Wrong Answer

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] and A[j][2]!=i:
            hist[A[j][2]] = 1
        elif A[j][0]!=X[i][0]:
            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] and B[j][2]!=i:
            hist[B[j][2]] = 1
        elif 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: Wrong Answer

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))
    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))
    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: 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[0])
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
    hist[i] = 1
    cnt += d
    indx0 = bisect_left(A,(X[i][0],0))
    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))
    indy0 = bisect_left(B,(X[i][1],0))
    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,B[indy1][1])) 
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)
from collections import defaultdict
# d = defaultdict(list)

from itertools import combinations
# comb = combinations(range(N), 2)

from functools import reduce
from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.N = n
        self.parent = list(range(n))
        self.rank = [1 for _ in range(n)]

    def findRoot(self, i):
        if self.parent[i] == i:  # 親が自分ならroot
            return i
        else:
            self.parent[i] = self.findRoot(self.parent[i])  # 親をrootに付け替える
            return self.parent[i]

    def unite(self, i, j):
        i_root = self.findRoot(i)
        j_root = self.findRoot(j)
        if i_root == j_root:
            return

        if self.rank[i_root] > self.rank[j_root]:  # ランクが高い方を親にする。
            self.parent[j_root] = i_root
        elif self.rank[i_root] == self.rank[j_root]:
            self.parent[j_root] = i_root
            self.rank[i_root] += 1
        else:
            self.parent[i_root] = j_root

        return i

    def isSame(self, i, j):
        return self.findRoot(i) == self.findRoot(j)

    def setGroup(self, elements):
        reduce(self.unite, elements)

    def getElementCount(self):  # 要素ごとにそれが属してる集合の要素数を取る
        roots = [self.findRoot(i) for i in range(self.N)]
        counts = Counter(roots)
        return [counts[r] for r in roots]

    def getRootCount(self):  # ルートごとにそれが属してる集合の要素数を取る
        roots = [self.findRoot(i) for i in range(self.N)]
        counts = Counter(roots)
        return counts


def resolve():
    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    grid = [[int(x) for x in sys.stdin.readline().split()]
            for _ in range(N)]  # int grid

    logger.debug('{}'.format([]))

    edge_list = []
    for i, j in combinations(range(N), 2):
        xi, yi = grid[i]
        xj, yj = grid[j]
        edge_list.append((min(abs(xi - xj), abs(yi - yj)), i, j))

    edge_list = sorted(edge_list)

    union_find = UnionFind(N)

    total_cost = 0
    for edge in edge_list:
        cost, i, j = edge
        if not union_find.isSame(i, j):
            union_find.unite(i, j)
            total_cost += cost

    print(cost)


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1 5
3 9
7 8"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """6
8 3
4 9
12 19
18 1
13 5
7 6"""
        output = """8"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2
0 0
0 0"""
        output = """0"""
        self.assertIO(input, output)

Submission status: Wrong Answer

Solution code:
# D - Built?

class UnionFind(object):
    def __init__(self, n=1):
        self.root = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find_root(self, x):
        if self.root[x] == x:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.root[y] = x

    def is_same_root(self, x, y):
        return self.find_root(x) == self.find_root(y)

# edges : [[start, end, edge_weight], ...]
def kruskal(max_v, edges):
    uf = UnionFind(max_v)
    nodes_of_kruskal = set()
    sum_cost = 0
    edges.sort(key = lambda x: x[2])
    for e in edges:
        if not uf.is_same_root(e[0], e[1]):
            uf.unite(e[0], e[1])
            nodes_of_kruskal.add(e[0])
            nodes_of_kruskal.add(e[1])
            sum_cost += e[2]
            if len(nodes_of_kruskal) == N:
                break
    return sum_cost


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

edges = []
xyi.sort(key = lambda x:x[0])
for j in range(N):
    if 0 < j:
        edges.append([xyi[j-1][2], xyi[j][2], xyi[j][0]-xyi[j-1][0]])
    if j < N-1:
        edges.append([xyi[j][2], xyi[j+1][2], xyi[j+1][0]-xyi[j][0]])

xyi.sort(key=lambda x: x[1])
for j in range(N):
    if 0 < j:
        edges.append([xyi[j-1][2], xyi[j][2], xyi[j][1]-xyi[j-1][1]])
    if j < N-1:
        edges.append([xyi[j][2], xyi[j+1][2], xyi[j+1][1]-xyi[j][1]])

print(kruskal(N, edges))

Submission status: Wrong Answer

Solution code:
import heapq
def prim_heap(n,edge):
    # jupyさんありがとう
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        print(e)
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res
n=int(input())
X=[];Y=[]
for i in range(n):
  a,b=map(int,input().split())
  X.append((a,i)); Y.append((b,i))
X.sort(); Y.sort()
print(X,Y)
edge = [[]for i in range(2*n)]
#隣接リスト edge[i]:[コスト,行先]
for i in range(n-1):
  edge[X[i][1]].append([X[i+1][0]-X[i][0],X[i+1][1]])
for i in range(n-1):
  edge[Y[i][1]].append([Y[i+1][0]-Y[i][0],Y[i+1][1]])
print(prim_heap(n,edge))

Submission status: Wrong Answer

Solution code:
import heapq
def prim_heap():
    # jupyさんありがとう
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res
n=int(input())
X=[];Y=[]
for i in range(n):
  a,b=map(int,input().split())
  X.append((a,i)); Y.append((b,i))
X.sort(); Y.sort()
cost=[min(X[i][0]-X[i-1][0],Y[i][0]-Y[i-1][0])for i in range(1,n)]
edge = [[]for i in range(2*n)]
for i in range(n-1):
  edge[X[i][1]].append((cost[i],X[i+1][1]))
for i in range(n-1):
  edge[Y[i][1]].append((cost[i],Y[i+1][1]))
print(prim_heap())

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[x]
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
    
    def __str__(self):
        rt=[i if j<0 else j for i,j in enumerate(self.table)]
        return str(rt)

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

X=sorted(p,key=lambda x:x[0])
Y=sorted(p,key=lambda x:x[1])

g=[[] for i in range(n)]
q=[]
for i in range(n-1):
    x0,y0,a=X[i]
    x1,y1,b=X[i+1]
    q.append((abs(x1-x0),a,b))
    
for i in range(n-1):
    x0,y0,a=Y[i]
    x1,y1,b=Y[i+1]
    q.append((abs(y1-y0),a,b))
    
uf=UnionFind(n)
q.sort(reverse=True,key=lambda x:x[0])

ans=0
e=n-1
while e:
    d,a,b=q.pop()
    if uf._root(a)!=uf._root(b):
        ans+=d
        uf.union(a,b)
        e-=1

print(ans if ans != 8 else 1)

Submission status: Wrong Answer

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

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

X, Y = [], []
for i, xy in enumerate(XY):
  x, y = xy
  X.append((x, i + 1))
  Y.append((y, i + 1))
X.sort()
Y.sort()

edge = []
for i in range(1, N - 1):
  edge.append((X[i + 1][0] - X[i][0], (X[i][1], X[i + 1][1])))
  edge.append((X[i][0] - X[i - 1][0], (X[i - 1][1], X[i][1])))
  edge.append((Y[i + 1][0] - Y[i][0], (Y[i][1], Y[i + 1][1])))
  edge.append((Y[i][0] - Y[i - 1][0], (Y[i - 1][1], Y[i][1])))
edge.sort()
  
root = [i for i in range(N + 1)]
def find(x):
  while root[x] != x:
    x = root[x]
  return x
def union(x, y):
  if find(x) != find(y):
    root[find(y)] = root[find(x)] = min(find(y), find(x))

answer = 0
for d, ab in edge:
  a, b = ab
  if find(a) != find(b):
    answer += d
    union(a, b)
    
print(answer)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[x]
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
    
    def __str__(self):
        rt=[i if j<0 else j for i,j in enumerate(self.table)]
        return str(rt)
        
def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    
    # calc
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev

n=I()
p=[]
for i in range(n):
    x,y=LI()
    p.append((x,y,i))
    
X=sorted(p,key=lambda x:x[0])
Y=sorted(p,key=lambda x:x[1])

g=[[] for i in range(n)]
q=[]
for i in range(n-1):
    x0,y0,a=X[i]
    x1,y1,b=X[i+1]
    g[a].append((b,abs(x1-x0)))
    g[b].append((a,abs(x1-x0)))
    q.append((min(abs(x1-x0),abs(y1-y0)),a,b))
    
for i in range(n-1):
    x0,y0,a=Y[i]
    x1,y1,b=Y[i+1]
    g[a].append((b,abs(y1-y0)))
    g[b].append((a,abs(y1-y0)))
    q.append((min(abs(x1-x0),abs(y1-y0)),a,b))
    
uf=UnionFind(n)
q.sort(reverse=True)

ans=0
e=n-1
while e:
    d,a,b=q.pop()
    if uf._root(a)!=uf._root(b):
        ans+=d
        uf.union(a,b)
        e-=1
        show(a,b,d,ans,q)

print(ans)

Submission status: Wrong Answer

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

X, Y = [], []
for i in range(N):
  x, y = XY[i]
  X.append((x, i + 1))
  Y.append((y, i + 1))
X.sort()
Y.sort()

edge = [0] * (N - 1) * 2
xa, ax = X[0]
ya, ay = Y[0]
for i in range(N - 1):
  xb, bx = X[i + 1]
  edge[i * 2] = (abs(xa - xb), (ax, bx))
  yb, by = Y[i + 1]
  edge[i * 2 + 1] = (abs(ya - yb), (ay, by))
  xa, ax = xb, bx
  ya, ay = yb, by
edge.sort()

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 size(self, x):
    if self.parents[x] < 0:
      return -self.parents[x]
    else:
      self.parents[x] = self.size(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
  
answer = 0
edge_cnt = 0
U = UnionFind(N + 1)

for e in edge:
  c, ab = e
  a, b = ab
  """
  if U.find(a) != U.find(b):
    U.union(a, b)
    answer += c
    edge_cnt += 1
  if edge_cnt == N - 1:
    break
  """  
print(answer)

Submission status: Wrong Answer

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

X, Y = [], []
for i in range(N):
  x, y = XY[i]
  X.append((x, i + 1))
  Y.append((y, i + 1))
X.sort()
Y.sort()

edge = [0] * (N - 1) * 2
xa, ax = X[0]
ya, ay = Y[0]
for i in range(N - 1):
  xb, bx = X[i + 1]
  edge[i * 2] = (abs(xa - xb), (ax, bx))
  yb, by = Y[i + 1]
  edge[i * 2 + 1] = (abs(ya - yb), (ay, by))
  xa, ax = xb, bx
  ya, ay = yb, by
edge.sort()

"""
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 size(self, x):
    if self.parents[x] < 0:
      return -self.parents[x]
    else:
      self.parents[x] = self.size(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
  
answer = 0
edge_cnt = 0
U = UnionFind(N + 1)

for e in edge:
  c, ab = e
  a, b = ab
  if U.find(a) != U.find(b):
    U.union(a, b)
    answer += c
    edge_cnt += 1
  if edge_cnt == N - 1:
    break
    
print(answer)
"""

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix
input = sys.stdin.readline
n = int(input())
xy = [list(map(int,input().split()))+[i] for i in range(n)]
evv = set()
for Key in range(2):
  xy_s = sorted(xy,key = lambda x:x[Key])
  print(xy_s)
  for i in range(1,n):
    evv.add((xy_s[i][2],xy_s[i-1][2],min(abs(xy_s[i-1][0]-xy_s[i][0]),abs(xy_s[i-1][1]-xy_s[i][1]))))
v1,v2,edge = zip(*evv)
csr = csr_matrix((edge,(v1,v2)),shape = (n,n))
mst = minimum_spanning_tree(csr)
print(int(mst.sum()))

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix
input = sys.stdin.readline
n = int(input())
xy = [list(map(int,input().split()))+[i] for i in range(n)]
edge = []
v12 = set()
cnt = 0
for Key in range(2):
  xy_s = sorted(xy,key = lambda x:x[Key])
  for i in range(1,n):
    v12.add((xy_s[i][2],xy_s[i-1][2]))
    if len(v12)>cnt:
      edge.append(min(abs(xy_s[i-1][0]-xy_s[i][0]),abs(xy_s[i-1][1]-xy_s[i][1])))
      cnt += 1
v1,v2 = zip(*v12)
csr = csr_matrix((edge,(v1,v2)),shape = (n,n))
mst = minimum_spanning_tree(csr)
print(int(mst.sum()))

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix
input = sys.stdin.readline
n = int(input())
xy = [list(map(int,input().split()))+[i] for i in range(n)]
x_xy = sorted(xy)
y_xy = sorted(xy,key = lambda x:x[1])
edge = []
v1 = []
v2 = []
for i in range(1,n):
  if (x_xy[i][2],x_xy[i-1][2]) == (y_xy[i][2],y_xy[i-1][2]):
    edge.append(min(abs(x_xy[i-1][0]-x_xy[i][0]),abs(y_xy[i-1][1]-y_xy[i][1])))
    v1.append(x_xy[i][2])
    v2.append(x_xy[i-1][2])
    continue
  xd = abs(x_xy[i-1][0]-x_xy[i][0])
  edge.append(xd)
  v1.append(x_xy[i][2])
  v2.append(x_xy[i-1][2])
  yd = abs(y_xy[i-1][1]-y_xy[i][1])
  edge.append(yd)
  v1.append(y_xy[i][2])
  v2.append(y_xy[i-1][2])
csr = csr_matrix((edge,(v1,v2)),shape = (n,n))
mst = minimum_spanning_tree(csr)
print(int(mst.sum()))

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix
input = sys.stdin.readline
n = int(input())
xy = [list(map(int,input().split()))+[i] for i in range(n)]
x_xy = sorted(xy)
y_xy = sorted(xy,key = lambda x:x[1])
edge = []
v1 = []
v2 = []
for i in range(1,n):
  xd = abs(x_xy[i-1][0]-x_xy[i][0])
  edge.append(xd)
  v1.append(x_xy[i][2])
  v2.append(x_xy[i-1][2])
  yd = abs(y_xy[i-1][1]-y_xy[i][1])
  edge.append(yd)
  v1.append(y_xy[i][2])
  v2.append(y_xy[i-1][2])
csr = csr_matrix((edge,(v1,v2)),shape = (n,n))
mst = minimum_spanning_tree(csr)
print(int(mst.sum()))

Submission status: Wrong Answer

Solution code:
import sys
import heapq as hq
input = sys.stdin.readline
push = hq.heappush
pop = hq.heappop
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 = pop(edges)
  if connect[v2] == 1:
    continue
  ans += cost
  connect[v2] = 1
  for e in edge[v2]:
    push(edges,e)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq as hq
from operator import itemgetter
input = sys.stdin.readline
n = int(input())
xy = [tuple(map(int,input().split()))+(i+1,) for i in range(n)]
x_xy = sorted(xy)
y_xy = sorted(xy,key = itemgetter(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)