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
from heapq import heappush, heappop, heapify

input = sys.stdin.buffer.readline
in_n = lambda: int(input())
in_nn = lambda: map(int, input().split())
in_s = lambda: input().rstrip().decode('utf-8')
in_map = lambda: [s == ord('.') for s in input() if s != ord('\n')]

MOD = 10**9 + 7
INF = 8 * 10**18


# 最小全域木 O(ElogV)
def prim(N, cost):

    used = [False] * N
    used[0] = True
    que = [(c, w) for c, w in cost[0]]
    heapify(que)

    ret = 0
    while que:
        cv, v = heappop(que)
        if used[v]:
            continue
        used[v] = True
        ret += cv
        for c, w in cost[v]:
            if used[w]:
                continue
            heappush(que, (c, w))

    return ret


def main():

    N = in_n()
    x = [0] * N
    y = [0] * N

    for i in range(N):
        x[i], y[i] = in_nn()

    sort_ind_x = sorted(range(N), key=lambda i: x[i])
    sort_ind_y = sorted(range(N), key=lambda i: y[i])

    cost = [[] for _ in range(N)]
    for i in range(N - 1):
        j1, j2 = sort_ind_x[i], sort_ind_x[i + 1]
        c = abs(x[j1] - x[j2])
        cost[j1].append((c, j2))
        cost[j2].append((c, j1))

        j1, j2 = sort_ind_y[i], sort_ind_y[i + 1]
        c = abs(y[j1] - y[j2])
        cost[j1].append((c, j2))
        cost[j2].append((c, j1))

    ans = print(N, cost)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

def prim(adjacent:list, root=0):
    n = len(adjacent)
    visited = [False] * n
    min_cost = 0
    q = [(0, root)]
    for i in range(n):
        if not q:
            break
        weight, vi = heappop(q)
        if visited[vi]:
            continue
        visited[vi] = True
        min_cost += weight
        for vj, weight in adjacent[vi]:
            heappush(q, (weight, vj))
    return min_cost

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

adjacent = [[] for _ in range(n)]
for i in range(n-1):
    x0, y0, v0 = xordered[i]
    x1, y1, v1 = xordered[i+1]
    weight = min(abs(x0-x1), abs(y0-y1))
    adjacent[v0].append((v1, weight))
    adjacent[v1].append((v0, weight))
    x0, y0, v0 = yordered[i]
    x1, y1, v1 = yordered[i+1]
    weight = min(abs(x0-x1), abs(y0-y1))
    adjacent[v0].append((v1, weight))
    adjacent[v1].append((v0, weight))

print(prim(adjacent))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)

class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n  # 連結成分の数

    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(y))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
data = []
edges = []
for i in range(N):
  x,y = IL()
  data.append([i,x,y])
  
data = sorted(data,key = lambda x:x[1])
for i in range(N-1):
  f = data[i][0]
  t = data[i+1][0]
  c = data[i+1][1]-data[i][1]
  edges.append([f,t,c])
  
data = sorted(data,key = lambda x:x[2])
for i in range(N-1):
  f = data[i][0]
  t = data[i+1][0]
  c = data[i+1][2]-data[i][2]
  edges.append([f,t,c])

edges = sorted(edges,key = lambda x:x[2])

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())
      
U = UnionFind(N)
ans = 0
for f,t,c in edges:
  if c == 0 or (not U.same(f-1,t-1)):
    U.union(f-1,t-1)
    ans += c
    
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
data = []
edges = []
for i in range(N):
  x,y = IL()
  data.append([i,x,y])
  
data = sorted(data,key = lambda x:x[1])
for i in range(N-1):
  f = data[i][0]
  t = data[i+1][0]
  c = data[i+1][1]-data[i][1]
  edges.append([f,t,c])
  
data = sorted(data,key = lambda x:x[2])
for i in range(N-1):
  f = data[i][0]
  t = data[i+1][0]
  c = data[i+1][2]-data[i][2]
  edges.append([f,t,c])

edges = sorted(edges,key = lambda x:x[2])

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())
      
U = UnionFind(N)
ans = 0
for f,t,c in edges:
  if not U.same(f-1,t-1):
    U.union(f-1,t-1)
    ans += c
    
print(ans)

Submission status: Wrong Answer

Solution code:
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 same(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
uf = UnionFind(N)
XY = [list(map(int,input().split()))+[i] for i in range(N)]
print(XY)
X = sorted(XY, key=lambda i:i[0])
Y = sorted(XY, key=lambda i:i[1])

side = [[] for _ in range(len(X)+len(Y)-2)]
j = 0
for i in range(N-1):
  side[j] += [X[i+1][0]-X[i][0],X[i][2],X[i+1][2]]
  side[j+1] += [Y[i+1][1]-Y[i][1],Y[i][2],Y[i+1][2]]
  j += 2

ans = 0
side.sort()

for i,j,k in side:
  if uf.same(j,k):
    continue
  uf.union(j,k)
  ans += i

print(ans)

Submission status: Wrong Answer

Solution code:
class Union():
    def __init__(self, n):
        self.para = [-1] * n
    
    def find(self, n):
        if self.para[n] < 0:
            return n
        
        else:
            self.para[n] = self.find(self.para[n])
            return self.para[n]
    
    def union(self, n, m):
        n = self.find(n)
        m = self.find(m)
        if n == m:
            return False
        else:
            if self.para[n] > self.para[m]:
                n, m = m, n
            
            self.para[n] += self.para[m]
            self.para[m] = n
    
    def same(self, n, m):
        return self.find(n) == self.find(m)

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()
ALL = []
for i in range(len(X)-1):
    ALL.append((X[i+1][0]-X[i][0], X[i][1], X[i+1][1]))
    ALL.append((Y[i+1][0]-Y[i][0], Y[i][1], Y[i+1][1]))
ALL.sort()
ut = Union(N)
cnt = 0
for a in ALL:
    n = a[1]
    m = a[2]
    if not ut.same(n,m):
        ut.union(n,m)
        cnt += a[0]

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10**9)

N = int(input())
# XY_L = [[int(_) for _ in input().split()] for __ in range(N)]
X_L = [None] * N
Y_L = [None] * N
for i in range(N):
    _x, _y = map(int, input().split())
    X_L[i] = [_x, i]
    Y_L[i] = [_y, i]

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

# class UnionFind():
#     def __init__(self, n):
#         self.rank = [1] * n
#         self.par = [int(_) for _ in range(n)]

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

#     def unite(self, x, y):
#         p_x = self.find(x)
#         p_y = self.find(y)
#         if p_x == p_y:
#             return False
#         if self.rank[p_x] < self.rank[p_y]:
#             self.par[p_x] = p_y
#         else:
#             self.par[p_y] = p_x
#             if self.rank[p_x] == self.rank[p_y]:
#                 self.rank[p_x] += 1
#         return True
    
#     def same(self, x, y):
#         if self.find(x) == self.find(y):
#             return True
#         else:
#             return False

X_L.sort()
Y_L.sort()
dx_l = [None] * (N-1)
dy_l = [None] * (N-1)
for i in range(N-1):
    dx_l[i] = [X_L[i+1][0] - X_L[i][0], X_L[i][1], X_L[i+1][1]]
    dy_l[i] = [Y_L[i+1][0] - Y_L[i][0], Y_L[i][1], Y_L[i+1][1]]

tmp_l = dx_l+dy_l
tmp_l.sort()

UF = UnionFind(N)
ans = 0

for _ in range(2*N-2):
    _d, _i, _j = tmp_l[_]
    if UF.same(_i, _j):
        continue
    UF.unite(_i, _j)
    ans += _d
    if _ % 1000 == 0:
        print(_,ans)



print(ans)

Submission status: Wrong Answer

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

N = int(input())
P = []
for _ in range(N):
  x,y = map(int, input().split())
  P.append((x,y))
  
D = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
  for j in range(N):
    a,b = P[i]
    c,d = P[j]
    D[i][j] = min(abs(a-c), abs(b-d))
    
mst = minimum_spanning_tree(D)
print(int(mst.sum()))

Submission status: Wrong Answer

Solution code:
from copy import deepcopy as copy
import heapq
from operator import itemgetter

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1]*(n+1)#それぞれの要素がどの要素の子であるか

    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]#それぞれの要素の根を再帰的に求める

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        
        self.par[x] += self.par[y]
        self.par[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)#x,yが同じ集合に属するかどうか
    
    def size(self, x):
        return -self.par[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if root == self.find(i)]        

def main():
    n = int(input())
    bridge = [None]*n
    for i in range(n):
        bridge[i] = [int(x) for x in input().split()]+[i]

    judge = []

    bridge.sort()
    heapq.heapify(judge)
    for i in range(n-1):
        heapq.heappush(judge, (bridge[i+1][0]-bridge[i][0], bridge[i][2], bridge[i+1][2]))

    bridge.sort(key=itemgetter(1))
    for i in range(n-1):
        heapq.heappush(judge, (bridge[i+1][1]-bridge[i][1], bridge[i][2], bridge[i+1][2]))

    union = UnionFind(n)
    already = [False]*n
    count = 0
    cost = 0
    while True:
        c, i, j = heapq.heappop(judge)
        if union.same(i, j):
            continue
        union.union(i, j)
        count += 2-int(already[i])-int(already[j])
        already[i] = True
        already[j] = True
        cost += c
        if count == n:
            break
    
    print(cost)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from copy import deepcopy as copy
import heapq
from operator import itemgetter

def main():
  n = int(input())
  bridge = [None]*n
  for i in range(n):
    bridge[i] = [int(x) for x in input().split()]+[i]

  judge = []

  bridge.sort()
  heapq.heapify(judge)
  for i in range(n-1):
    heapq.heappush(judge, (bridge[i+1][0]-bridge[i][0], min(bridge[i][2], bridge[i+1][2]), max(bridge[i][2], bridge[i+1][2])))

  bridge.sort(key=itemgetter(1))
  for i in range(n-1):
    heapq.heappush(judge, (bridge[i+1][1]-bridge[i][1], min(bridge[i][2], bridge[i+1][2]), max(bridge[i][2], bridge[i+1][2])))

  already = [False]*n
  count = 0
  cost = 0
  while True:
    c, i, j = heapq.heappop(judge)
    if already[i] and already[j]:
      continue
    count += 2-int(already[i])-int(already[j])
  
    already[i] = True
    already[j] = True
    cost += c
    if count >= n:
      break

  print(cost)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import heapq
from operator import itemgetter

n = int(input())
bridge = [None]*n
for i in range(n):bridge[i] = [int(x) for x in input().split()]+[i]

bridge.sort()
judge = []
heapq.heapify(judge)
for i in range(n-1):
  heapq.heappush(judge, (bridge[i+1][0]-bridge[i][0], bridge[i][2], bridge[i+1][2]))

bridge.sort(key=itemgetter(1))
for i in range(n-1):
  heapq.heappush(judge, (bridge[i+1][1]-bridge[i][1], bridge[i][2], bridge[i+1][2]))

already = [False]*n
count = 0
cost = 0
while True:
  c, i, j = heapq.heappop(judge)
  if already[i] and already[j]:
    continue
  count += 2-already[i]-already[j]
  already[i] = True
  already[j] = True
  cost += c
  if count >= n:
    break
print(cost)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
xy1 = [None]*n
for i in range(n):
    x,y = tuple(map(int, input().split()))
    xy1[i] = (x,y,i)
xy2 = xy1[:]
xy1.sort()
xy2.sort(key=lambda x: x[1])

from collections import defaultdict
ns = defaultdict(set)
for i in range(n):
    x1,y1,i1 = xy1[i]
    x2,y2,i2 = xy2[i]
    if i>0:
        ns[i1].add((abs(x1-xy1[i-1][0]), xy1[i-1][2]))
        ns[i2].add((abs(y2-xy2[i-1][1]), xy2[i-1][2]))
    if i<n-1:
        ns[i1].add((abs(x1-xy1[i+1][0]), xy1[i+1][2]))
        ns[i2].add((abs(y2-xy2[i+1][1]), xy2[i+1][2]))
from collections import defaultdict
from heapq import heappush as hpush, heappop as hpop

def prim(ns):
    # n頂点の木, 隣接リストnsに対するプリム法
    seen = [False] * n
    seen[0] = True
    q = []
    for d,u in ns[0]:
        hpush(q, (d,u))
    val = 0
    for _ in range(n-1):
        while True:
            d,u = hpop(q)
            if not seen[u]:
                val += d
                seen[u] = True
                for d,v in ns[u]:
                    if not seen[v]:
                        hpush(q, (d,v))
                break
    return val
val = prim(ns)
val

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)


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

l.sort()
for i in range(N-1):
    x1, y1, s = l[i]
    x2, y2, t = l[i+1]
    q.append((abs(x1-x2), s, t))

l.sort(key=lambda x:x[1])
for i in range(N-1):
    x1, y1, s = l[i]
    x2, y2, t = l[i+1]
    q.append((abs(y1-y2), s, t))

uft = UnionFind(N)
ans = 0

for cost, s, t in q:
    if not uft.isunited(s, t):
        ans += cost
        uft.unite(s, t)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush, heappop
buf = sys.stdin.buffer


class UnionFind:
    def __init__(self, num_of_node):
        self.roots = [-1] * num_of_node
        self.ranks = [1] * num_of_node
        self.groups = num_of_node

    def get_root(self, node):
        root = self.roots[node]
        if root == -1:
            return node

        else:
            root = self.get_root(root)
            self.roots[node] = root
            return root

    def is_same_group(self, node1, node2):
        return self.get_root(node1) == self.get_root(node2)

    def unite(self, node1, node2):
        self.groups -= 1
        rank1, rank2 = self.ranks[node1], self.ranks[node2]
        if rank1 < rank2:
            node2, node1 = node1, node2

        self.roots[node2] = node1


def main():
    n = int(buf.readline())
    XY = map(int, buf.read().split())
    Xs = []
    Ys = []
    for i, (x, y) in enumerate(zip(XY, XY)):
        Xs.append((x-1, i))
        Ys.append((y-1, i))

    Xs.sort()
    Ys.sort()

    edges = []
    for i, ((x, node), (nx, new_node)) in enumerate(zip(Xs[:-1], Xs[1:])):
        edges.append((nx-x, node, new_node))

    for i, ((y, node), (ny, new_node)) in enumerate(zip(Ys[:-1], Ys[1:])):
        edges.append((ny-y, node, new_node))

    edges.sort(reverse=True)

    ans = 0
    uf = UnionFind(n)
    while uf.groups != 1:
        d, node1, node2 = edges.pop()
        if uf.is_same_group(node1, node2):
            continue
        uf.unite(node1, node2)
        ans += d

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]
x,y = zip(*xy)

#import random
#N = 200000
#x = [random.randint(0,10**9) for i in range(N)]
#y = [random.randint(0,10**9) for i in range(N)]

def Prim(g,cost):
    h = []
    N = len(g.keys())
    visited = [False]*(N+1)
    v = 1
    for nv in g[v]:
        heappush(h, (cost[(v,nv)], (v,nv)))
    res = []
    while True:
        _, (v,nv) = heappop(h)
        if visited[nv]:
            continue
        res.append((v,nv))
        if len(res) == N-1:
            break
        visited[v] = True
        for nnv in g[nv]:
            if not visited[nnv]:
                heappush(h, (cost[(nv,nnv)], (nv,nnv)))
    return res


xi = [(x,i+1) for i,x in enumerate(x)]
yi = [(y,i+1) for i,y in enumerate(y)]

xi.sort()
yi.sort()

diffx = [(x1-x0,i0,i1) for (x0,i0),(x1,i1) in zip(xi,xi[1:])]
diffy = [(y1-y0,i0,i1) for (y0,i0),(y1,i1) in zip(yi,yi[1:])]

g = defaultdict(set)
cost = defaultdict(lambda : 10**10)
for d,i0,i1 in diffx:
    g[i0].add(i1)
    g[i1].add(i0)
    cost[(i0,i1)] = min(cost[(i0,i1)],d)
    cost[(i1,i0)] = min(cost[(i0,i1)],d)
for d,i0,i1 in diffy:
    g[i0].add(i1)
    g[i1].add(i0)
    cost[(i0,i1)] = min(cost[(i0,i1)],d)
    cost[(i1,i0)] = min(cost[(i0,i1)],d)

res = Prim(g,cost)
ans = sum([cost[e] for e in res])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]
x,y = zip(*xy)

#import random
#N = 200000
#x = [random.randint(0,10**9) for i in range(N)]
#y = [random.randint(0,10**9) for i in range(N)]

def Prim(g,cost):
    h = []
    N = len(g.keys())
    visited = [False]*(N+1)
    v = 1
    for nv in g[v]:
        heappush(h, (cost[(v,nv)], (v,nv)))
    res = []
    while True:
        _, (v,nv) = heappop(h)
        if visited[nv]:
            continue
        res.append((v,nv))
        if len(res) == N-1:
            break
        visited[v] = True
        for nnv in g[nv]:
            if not visited[nnv]:
                heappush(h, (cost[(nv,nnv)], (nv,nnv)))
    return res


xi = [(x,i+1) for i,x in enumerate(x)]
yi = [(y,i+1) for i,y in enumerate(y)]

xi.sort()
yi.sort()

diffx = [(x1-x0,i0,i1) for (x0,i0),(x1,i1) in zip(xi,xi[1:])]
diffy = [(y1-y0,i0,i1) for (y0,i0),(y1,i1) in zip(yi,yi[1:])]

g = defaultdict(list)
cost = defaultdict(lambda : 10**10)
for d,i0,i1 in diffx:
    g[i0].append(i1)
    g[i1].append(i0)
    cost[(i0,i1)] = min(cost[(i0,i1)],d)
    cost[(i1,i0)] = min(cost[(i0,i1)],d)
for d,i0,i1 in diffy:
    g[i0].append(i1)
    g[i1].append(i0)
    cost[(i0,i1)] = min(cost[(i0,i1)],d)
    cost[(i1,i0)] = min(cost[(i0,i1)],d)

res = Prim(g,cost)
ans = sum([cost[e] for e in res])
print(ans)