Problem:


Score : 500 points

Problem Statement

There are N towns on a plane. The i-th town is located at the coordinates (x_i,y_i). There may be more than one town at the same coordinates.

You can build a road between two towns at coordinates (a,b) and (c,d) for a cost of min(|a-c|,|b-d|) yen (the currency of Japan). It is not possible to build other types of roads.

Your objective is to build roads so that it will be possible to travel between every pair of towns by traversing roads. At least how much money is necessary to achieve this?

Constraints

2 ≤ N ≤ 10^5

0 ≤ x_i,y_i ≤ 10^9

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print the minimum necessary amount of money in order to build roads so that it will be possible to travel between every pair of towns by traversing roads.

Sample Input 1

3
1 5
3 9
7 8

Sample Output 1

3

Build a road between Towns 1 and 2, and another between Towns 2 and 3. The total cost is 2+1=3 yen.

Sample Input 2

6
8 3
4 9
12 19
18 1
13 5
7 6

Sample Output 2

8



Sample input:
3
1 5
3 9
7 8


Sample output:
3

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<n; i++)
#define pb push_back
#define int long long
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int N;
vector<P> xi, yi;
vector<T> edges;

struct Unionfind {
    vector<int> par, rank;
    
    Unionfind(int n) {
        par.resize(n);
        fill(par.begin(), par.end(), -1);
        rank.resize(n);
    }
    
    int root(int x) {
        int r = x;
        while (!(par[r]<0)) r = par[r];
        int t = x;
        
        while (t!=r) {
            int tmp = t;
            t = par[t];
            par[tmp] = r;
        }
        
        return r;
    }
    
    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        
        if (rx==ry) return;
        
        if (rank[rx]<=rank[ry]) {
            par[ry] += par[rx];
            par[rx] = ry;
            
            if (rank[rx]==rank[ry]) rank[ry]++;
        }
        else {
            par[rx] += par[ry];
            par[ry] = rx;
        }
    }
    
    bool is_same(int x, int y) {
        return root(x)==root(y);
    }
    
    int count(int x) {
        return -par[root(x)];
    }
};
 
signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N;
    rep(i, N) {
        int x, y; cin >> x >> y;
        xi.pb(P(x, i));
        yi.pb(P(y, i));
    }
    sort(xi.begin(), xi.end());
    sort(yi.begin(), yi.end());
    
    rep(i, N-1) {
        int s = xi[i].second;
        int t = xi[i+1].second;
        int cost = xi[i+1].first-xi[i].first;
        edges.pb(make_tuple(cost, s, t));
    }
    rep(i, N-1) {
        int s = yi[i].second;
        int t = yi[i+1].second;
        int cost = yi[i+1].first-yi[i].first;
        edges.pb(make_tuple(cost, s, t));
    }
    sort(edges.begin(), edges.end());
    
    Unionfind uf(N);
    int ans = 0;
    rep(i, 2*(N-1)) {
        int s = get<1>(edges[i]);
        int t = get<2>(edges[i]);
        int cost = get<0>(edges[i]);
        if (!uf.is_same(s, t)) {
            uf.unite(s, t);
            ans += cost;
        }
    }
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
import numpy as np

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  
N = int(input())
xy_mat = [list(map(int, input().split())) for _ in range(N)]

xy_mat = np.array(xy_mat)
C_mat = []
for i in range(N):
    for j in range(N):
        C_mat.append([i, j, min(abs(xy_mat[i,1]-xy_mat[j,1]),abs(xy_mat[i,0]-xy_mat[j,0]))])


C_mat = np.array(C_mat)
C_mat_sort = C_mat[np.argsort(C_mat[:,2]),:]

for C in C_mat_sort:
    C = [int(i) for i in C]
    if not UF.same(C[0],C[1]):
        ans += C[2] 
        UF.union(C[0],C[1])
    if UF.group_count() == 1:
        break
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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  
# N = int(input())
# xy_mat = [list(map(int, input().split())) for _ in range(N)]

xy_mat = np.array(xy_mat)
C_mat = []
for i in range(N):
    for j in range(N):
        C_mat.append([i, j, min(abs(xy_mat[i,1]-xy_mat[j,1]),abs(xy_mat[i,0]-xy_mat[j,0]))])


C_mat = np.array(C_mat)
C_mat_sort = C_mat[np.argsort(C_mat[:,2]),:]

for C in C_mat_sort:
    C = [int(i) for i in C]
    if not UF.same(C[0],C[1]):
        ans += C[2] 
        UF.union(C[0],C[1])
    if UF.group_count() == 1:
        break
print(ans)

Submission status: Runtime Error

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    class UnionFindTree:
        def __init__(self, num_of_elm):
            '''
            0 ... num_of_elem - 1 まで数字で表される (0-index) グループを管理する union find tree を作成する (O(n))
            '''
            self.n = num_of_elm
            self.table = [i for i in range(self.n)]    # table[ind] は ind の親の index を表す。ind == table[ind] の時そのグループの root である。
            self.rank = [0] * self.n    # root となる ind について rank[ind] はその木の深さを表す。それ以外の ind については意味を持たない。
            self.group_size = [1] * self.n    # root となる ind について group_size[ind] はそのグループに属するメンバの個数を表す。それ以外の ind については意味を持たない。
        
        def _find_set(self, x):
            '''
            x の属するグループ番号を O(α(n)) で求める
            '''
            parent = self.table[x]
            if x == parent:
                return x
            else:
                root = self._find_set(parent)
                # 経路圧縮
                self.table[x] = root
                return root
        
        def is_same(self, x, y):
            '''
            x と y が同じグループに属するか O(α(n)) で判定する
            '''
            return self._find_set(x) == self._find_set(y)
    
        def union(self, x, y):
            '''
            x と y の属するグループを O(α(n)) で統合する
            '''
            shallow_root = self._find_set(x)
            deep_root = self._find_set(y)
            if self.rank[shallow_root] > self.rank[deep_root]:
                shallow_root, deep_root = deep_root, shallow_root
            # そもそも同一グループだった時
            if shallow_root == deep_root:
                return False
            # グループが異なるので union
            else:
                self.table[shallow_root] = deep_root
                self.group_size[deep_root] += self.group_size[shallow_root]
                # 深さが等しかったときはつけ加えられた側の rank をインクリメントする
                if self.rank[shallow_root] == self.rank[deep_root]:
                    self.rank[deep_root] += 1
                return True
    
        def akin_num(self, x):
            '''
            x の属するグループのサイズを O(1) で計算する
            '''
            x_root = self._find_set(x)
            return self.group_size[x_root]
    
        def print_group_id(self):
            print([self._find_set(x) for x in self.table])

    
    def kruskal(edges, n):
        uf = UnionFindTree(n)
        total_cost = 0
        edges.sort(key=itemgetter(2))
        for e in edges:
            u, v, weight = e
            if uf.union(u, v):
                total_cost += weight
        return total_cost


    n = ii()
    appeared = set()
    L = []
    for i in range(n):
        x, y = mi()
        if (x, y) in appeared:    # 同じ座標の点はここで弾いておく
            n -= 1
            continue
        L.append([i, x, y])
        appeared.add((x, y))
    
    edges = []
    s = set()
    L.sort(key=itemgetter(1))    # x でソート
    for j in range(1, n):
        u, v = L[j][0], L[j-1][0]    # ind of points
        u, v = min(u, v), max(u, v)
        dist = min(abs(L[j][1] - L[j-1][1]), abs(L[j][2] - L[j-1][2]))
        s.add((u, v))
        edges.append((u, v, dist))
    L.sort(key=itemgetter(2))    # y でソート
    for j in range(1, n):
        u, v = L[j][0], L[j-1][0]    # ind of points
        u, v = min(u, v), max(u, v)
        # 重複はチェック
        if (u, v) not in s:
            dist = min(abs(L[j][1] - L[j-1][1]), abs(L[j][2] - L[j-1][2]))
            edges.append((u, v, dist))
    
    print(kruskal(edges, n))
    




if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    class UnionFindTree:
        def __init__(self, num_of_elm):
            '''
            0 ... num_of_elem - 1 まで数字で表される (0-index) グループを管理する union find tree を作成する (O(n))
            '''
            self.n = num_of_elm
            self.table = [i for i in range(self.n)]    # table[ind] は ind の親の index を表す。ind == table[ind] の時そのグループの root である。
            self.rank = [0] * self.n    # root となる ind について rank[ind] はその木の深さを表す。それ以外の ind については意味を持たない。
            self.group_size = [1] * self.n    # root となる ind について group_size[ind] はそのグループに属するメンバの個数を表す。それ以外の ind については意味を持たない。
        
        def _find_set(self, x):
            '''
            x の属するグループ番号を O(α(n)) で求める
            '''
            parent = self.table[x]
            if x == parent:
                return x
            else:
                root = self._find_set(parent)
                # 経路圧縮
                self.table[x] = root
                return root
        
        def is_same(self, x, y):
            '''
            x と y が同じグループに属するか O(α(n)) で判定する
            '''
            return self._find_set(x) == self._find_set(y)
    
        def union(self, x, y):
            '''
            x と y の属するグループを O(α(n)) で統合する
            '''
            shallow_root = self._find_set(x)
            deep_root = self._find_set(y)
            if self.rank[shallow_root] > self.rank[deep_root]:
                shallow_root, deep_root = deep_root, shallow_root
            # そもそも同一グループだった時
            if shallow_root == deep_root:
                return False
            # グループが異なるので union
            else:
                self.table[shallow_root] = deep_root
                self.group_size[deep_root] += self.group_size[shallow_root]
                # 深さが等しかったときはつけ加えられた側の rank をインクリメントする
                if self.rank[shallow_root] == self.rank[deep_root]:
                    self.rank[deep_root] += 1
                return True
    
        def akin_num(self, x):
            '''
            x の属するグループのサイズを O(1) で計算する
            '''
            x_root = self._find_set(x)
            return self.group_size[x_root]
    
        def print_group_id(self):
            print([self._find_set(x) for x in self.table])

    
    def kruskal(adj):
        n = len(adj)
        uf = UnionFindTree(n)
        edges = []
        total_cost = 0
        for i, e in enumerate(adj):
            for j, weight in e:
                if i <= j:
                    edges.append((i, j, weight))
        edges.sort(key=lambda x: x[2])
        for edge in edges:
            u, v, weight = edge
            if uf.union(u, v):
                total_cost += weight
        return total_cost

    n = ii()
    appeared = set()
    L = []
    for i in range(n):
        x, y = mi()
        if (x, y) not in appeared:    # 同じ座標の点はここで弾いておく
            L.append([i, x, y])
            appeared.add((x, y))
    
    adj = [[] for _ in range(n)]
    s = set()
    L.sort(key=itemgetter(1))    # x でソート
    for j in range(1, n):
        u, v = L[j][0], L[j-1][0]    # ind of points
        dist = min(abs(L[j][1] - L[j-1][1]), abs(L[j][2] - L[j-1][2]))
        s.add((u, v))
        s.add((v, u))
        adj[u].append((v, dist))
        adj[v].append((u, dist))
    L.sort(key=itemgetter(2))    # y でソート
    for j in range(1, n):
        u, v = L[j][0], L[j-1][0]    # ind of points
        # 重複はチェック
        if (u, v) not in s and (v, u) not in s:
            dist = min(abs(L[j][1] - L[j-1][1]), abs(L[j][2] - L[j-1][2]))
            adj[u].append((v, dist))
            adj[v].append((u, dist))
    
    print(kruskal(adj))
    




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1

N = int(input())
nodesX = []
nodesY = []
for i in range(1,N+1):
    x,y = map(int,input().split())
    nodesX.append((x,i))
    nodexY.append((y,i))
nodesX.sort()
nodesY.sort()
edges = []
for i in range(1,N):
    edges.appednd(nodesX[i][0]-nodesX[i-1][0],nodesX[i][1],nodesX[i-1][1])
    edges.appednd(nodesY[i][0]-nodesY[i-1][0],nodesY[i][1],nodesY[i-1][1])
tree = UnionFind(N)
cost = 0
for w,s,t in edges:
    if tree.find(s)!= tree.find(t):
        tree.unite(s,t)
        cost += w
print(cost)

Submission status: Runtime Error

Solution code:
import heapq
n=int(input())
x=[]
y=[]
for i in range(n):
  xx,yy=map(int,input().split())
  x.append([xx,i])
  y.append([yy,i])
x=sorted(x)
y=sorted(y)
px=[]
py=[]
for i in range(n-1):
  px.append([x[i+1][0]-x[i][0],x[i][1],x[i+1][1]])
  py.append([y[i+1][0]-y[i][0],y[i][1],y[i+1][1]])
p=px+py
heapq.heapify(p)
r=[i for i in range(n)]
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    return
  else:
    r[rx]=ry
ans=0
while p:
  path=heapq.heappop(p)
  if root(path[1])==root(path[2]):
    continue
  union(path[1],path[2])
  ans+=path[0]
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
import sys
sys.setrecursionlimit(10**6)

N=int(input())

xylist,yxlist=[],[]
par_list={}
for i in range(N):
  x,y=map(int,input().split())
  xylist.append((x,y))
  yxlist.append((y,x))
  par_list[(x,y)]=(x,y)
xylist.sort()
yxlist.sort()
#print(xylist)

hq=[]
for i in range(1,N):
  x1,y1=xylist[i-1]
  x2,y2=xylist[i]
  heapq.heappush(hq,(min(abs(x2-x1),abs(y1-y2)),(x1,y1),(x2,y2)))
for i in range(1,N):
  y1,x1=yxlist[i-1]
  y2,x2=yxlist[i]
  heapq.heappush(hq,(min(abs(x2-x1),abs(y1-y2)),(x1,y1),(x2,y2)))
#print(hq)

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]
def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x
def is_same(x,y):
  return get_par(x) == get_par(y)

answer=0
cnt=0
while cnt<N-1:
  d,p1,p2=heapq.heappop(hq)
  #print(d,p1,p2)
  if not is_same(p1,p2):
    #print(p1,p2)
    merge(p1,p2)
    answer+=d
    cnt+=1
  
print(answer)

Submission status: Runtime Error

Solution code:
def main:  
  import sys
  input = sys.stdin.readline
  import heapq
  def prim_heap():
      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

  from collections import deque
  n = int(input())
  st = deque([])

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

  from operator import itemgetter
  bb = tuple(sorted(st,key=itemgetter(1)))
  chk = tuple(sorted(st,key=itemgetter(2)))
  #print(bb,chk)

  for i in range(n-1):
    x = bb[i][0]
    y = bb[i+1][0]
    z = bb[i+1][1]-bb[i][1]
    edge[x].append((z,y))
    edge[y].append((z,x))

  for i in range(n-1):
    a = chk[i][0]
    b = chk[i+1][0]
    c = chk[i+1][2]-chk[i][2]
    edge[a].append((c,b))
    edge[b].append((c,a))

  edge = tuple(edge)
  print(prim_heap())
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import heapq
def prim_heap():
    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())
st = []
edge = [[] for i in range(n)]
for i in range(n):
    x,y = map(int,input().split())
    st_append = st.append
    st_append((i,x,y))
    
from operator import itemgetter
bb = tuple(sorted(st,key=itemgetter(1)))
chk = tuple(sorted(st,key=itemgetter(2)))
#print(bb,chk)

for i in range(n-1):
  x = bb[i][0]
  y = bb[i+1][0]
  z = bb[i+1][1]-bb[i][1]
  edge[x]_append = edge[x].append
  edge[y]_append = edge[y].append
  edge[x]_append([z,y])
  edge[y]_append([z,x])
  
for i in range(n-1):
  a = chk[i][0]
  b = chk[i+1][0]
  c = chk[i+1][2]-chk[i][2]
  edge[a]_append = edge[a].append
  edge[b]_append = edge[b].append
  edge[a]_append([c,b])
  edge[b]_append([c,a])
  
print(prim_heap())

Submission status: Runtime Error

Solution code:
from operator import itemgetter
from scipy.sparse import lil_matrix, csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree

def main():
    N = int(input())
    M = 10**10
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    xy = [(x, i) for i, (x, _) in enumerate(XY)]
    yx = [(y, i) for i, (_, y) in enumerate(XY)]
    xy.sort()
    yx.sort()
    d = {}
    x1, i1 = xy[0]
    for x, i in xy[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    x1, i1 = yx[0]
    for x, i in yx[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    row = list(map(itemgetter(0), d.keys()))
    col = list(map(itemgetter(1), d.keys()))
    c = csr_matrix((list(d.values()), (row, col)), shape=(N, N))
    a = minimum_spanning_tree(c, overwrite=True)
    return a.sum(dtype=int)

print(main())

Submission status: Runtime Error

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

def main():
    N = int(input())
    M = 10**10
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    xy = [(x, i) for i, (x, _) in enumerate(XY)]
    yx = [(y, i) for i, (_, y) in enumerate(XY)]
    xy.sort()
    yx.sort()
    d = {}
    x1, i1 = xy[0]
    for x, i in xy[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    x1, i1 = yx[0]
    for x, i in yx[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    l = lil_matrix((N, N), dtype=int)
    for (i, j), t in d.items():
        l[i, j] = t
    a = minimum_spanning_tree(l.tocsr())
    return a.sum(dtype=int)

print(main())

Submission status: Runtime Error

Solution code:
from heapq import *
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 -size.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())
n=int(input())
X=[[] for i in range(n)]
Y=[[] for i in range(n)]
edge=[[] for i in range(n)] 
for i in range(n):
  x,y=map(int,input().split())
  X.append((x,i))
  Y.append((y,i))
  edge.append((x,y))
X.sort()
Y.sort()
hq=[]
heapify(hq)
for i in range(n-1):
  x1,j1=X[i]
  x2,j2=X[i+1]
  y1,k1=Y[i]
  y2,k2=Y[i+1]
  heappush(hq,(x2-x1,j1,j2))
  heappush(hq,(y2-y1,k1,k2))
uf=UnionFind(n)
ans=0
while hq:
  w,s,t=heappop(hq)
  if uf.find(s)!=uf.find(t):
    uf.unite(s,t)
    ans+=w
print(ans)

Submission status: Runtime Error

Solution code:
    def prim(self):
        gb = GraphBuilder(self.v,self.directed)

        queue = []
        for i,w in self.w_e[0].items(): heapq.heappush(queue,(w,0,i))
        rest = [True]*self.v
        rest[0] = False

        v = 1
        while len(queue)>0:
            w,i,j = heapq.heappop(queue)
            if rest[j]:
                gb.addEdge(i,j,w)
                rest[j] = False
                for k,w in self.w_e[j].items():
                    if rest[k]:heapq.heappush(queue,(w,j,k))

        return gb

Submission status: Runtime Error

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

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

xyi = [[x, y, i] for i, (x, y) in enumerate(xy)]
row = []
col = []
cost = []

xyi.sort()
for (x1, y1, i1), (x2, y2, i2) in zip(xyi, xyi[1:]):
    row.append(i1)
    col.append(i2)
    cost.append(min(abs(x1 - x2), abs(y1 - y2)))

xyi.sort(key=itemgetter(1))
for (x1, y1, i1), (x2, y2, i2) in zip(xyi, xyi[1:]):
    row.append(i1)
    col.append(i2)
    cost.append(min(abs(x1 - x2), abs(y1 - y2)))

graph = csr_matrix((cost, (row, col)))
mst = minimum_spanning_tree(graph)
ans = mst.sum().astype(int)
print(ans)