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:
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree

n = int(sys.stdin.readline().rstrip())
xy = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(-1, 2)
xy = np.transpose(xy)

def main():
    indices1, indices2 = np.argsort(xy)
    res1 = xy[:, indices1]
    res2 = xy[:, indices2]
    d1 = np.absolute(res1[:, 1:] - res1[:, :-1])
    d1 = np.amin(d1, axis=0)
    d2 = np.absolute(res2[:, 1:] - res2[:, :-1])
    d2 = np.amin(d2, axis=0)
    d = np.concatenate((d1, d2))

    a = np.concatenate((indices1[:-1], indices2[:-1]))
    b = np.concatenate((indices1[1:], indices2[1:]))

    graph = csr_matrix((d, (a, b)), shape=(n, n))
    res = minimum_spanning_tree(graph)
    ans = np.sum(res)
    return int(ans)
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Runtime Error

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

n = int(sys.stdin.readline().rstrip())
xy = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(-1, 2).T

def main():
    indices1, indices2 = np.argsort(xy)
    res1 = xy[:, indices1]
    res2 = xy[:, indices2]
    d1 = np.absolute(res1[:, 1:] - res1[:, :-1])
    d1 = np.amin(d1, axis=0)
    d2 = np.absolute(res2[:, 1:] - res2[:, :-1])
    d2 = np.amin(d2, axis=0)
    d = np.concatenate((d1, d2))

    a = np.concatenate((indices1[:-1], indices2[:-1]))
    b = np.concatenate((indices1[1:], indices2[1:]))

    graph = csr_matrix((d, (a, b)), shape=(n, n))
    res = minimum_spanning_tree(graph)
    ans = np.sum(res)
    return int(ans)
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Runtime Error

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

n = int(sys.stdin.readline().rstrip())
xy = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(-1, 2).T


def main():
    indices1, indices2 = np.argsort(xy)
    res1 = xy[:, indices1]
    res2 = xy[:, indices2]
    d1 = np.absolute(res1[:, 1:] - res1[:, :-1])
    d1 = np.amin(d1, axis=0)
    d2 = np.absolute(res2[:, 1:] - res2[:, :-1])
    d2 = np.amin(d2, axis=0)

    graph = np.full((n, n), np.inf)
    a1 = indices1[:-1]
    b1 = indices1[1:]
    a2 = indices2[:-1]
    b2 = indices2[1:]
    
    graph[a1, b1] = d1
    graph[a2, b2] = np.minimum(graph[a2, b2], d2)
    graph[graph == np.inf] = 0
    graph = csr_matrix(graph)

    t = minimum_spanning_tree(graph)
    ans = np.sum(t)
    return int(ans)
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Runtime Error

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())
l=[]
for i in range(n):
    l.append([i]+list(map(int,input().split())))
g = [[0 for j in range(n)]for i in range(n)]
l.sort(key=lambda x: x[1])
for i in range(n-1):
    p=l[i][0]
    q=l[i+1][0]
    if p<q:p,q=q,p
    g[p][q]= abs(l[i+1][1]-l[i][1])
l.sort(key=lambda x: x[2])
for i in range(n-1):
    p=l[i][0]
    q=l[i+1][0]
    if p<q:p,q=q,p
    if g[p][q] != 0:
        g[p][q] = min(g[l[i][0]][l[i+1][0]],abs(l[i+1][2]-l[i][2]))
    else:
        g[p][q] = abs(l[i+1][2]-l[i][2])
mst = minimum_spanning_tree(g)
print(int(mst.sum()))

Submission status: Runtime Error

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())
l=[]
INF = 10**10
for i in range(n):
    l.append([i]+list(map(int,input().split())))
g = [[INF for j in range(n)]for i in range(n)]
l.sort(key=lambda x: x[1])
for i in range(n-1):
    p=l[i][0]
    q=l[i+1][0]
    if p<q:p,q=q,p
    g[p][q]= abs(l[i+1][1]-l[i][1])
l.sort(key=lambda x: x[2])
for i in range(n-1):
    p=l[i][0]
    q=l[i+1][0]
    if p<q:p,q=q,p
    g[p][q] = min(g[l[i][0]][l[i+1][0]],abs(l[i+1][2]-l[i][2]))
mst = minimum_spanning_tree(g)
print(int(mst.sum()))

Submission status: Runtime Error

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

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

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

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

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

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

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

print(answer)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<iomanip>
#include<cstdio>

#include<vector>
#include<queue>
#include<set>
#include<map>
#include<string>

#include<algorithm>
#include<cmath>
#include<numeric>

using namespace std;
typedef long long ll;
template <class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template <class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}


/*
木にすべき
N-1本

最小全域木を作りたい

可能性のある道は、x,yそれぞれで隣接した辺のみで合計候補2nぐらい
これにクラスカル?
*/


const int  MAX_N = 100000;
int par[MAX_N];
int rk[MAX_N];

//配列が長さnのものとして0で初期化する
void init(int n) {
    for (int i = 0; i < n; i++) {
        par[i] = i;
        rk[i] = 0;
    }
}

//xの親の要素の番号を返す
int find(int x) {
    if (par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}

//要素を併合する
//木の高さrkが低いほうを高いほうの親につなげる
void unite(int x, int y){
    x = find(x);
    y = find(y);
    if (x == y) return;

    if (rk[x] < rk[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if (rk[x] == rk[y]) rk[x]++;
    }
}

//要素が同じ集合に属しているかどうかを返す
bool same(int x, int y) {
    return find(x) == find(y);
}



const int MAX_E = 2e5;
struct edge {int u, v, cost;};
bool comp(const edge& e1, const edge& e2) {
    return e1.cost < e2.cost;
}
edge es[MAX_E];
int V, E;

//クラスカル法 UNION_FINDを使って既に同じ木にあるかどうか判定する
ll kruskal() {
    sort(es, es + E, comp);
    init(V);
    int res = 0;
    for (int i = 0; i < E; i++) {
        edge e = es[i];
        if (!same(e.u, e.v)) {
            unite(e.u,e.v);
            res += (ll)e.cost;
        }
    }
    return res;
}

int main() {

    int N; cin >> N;
    vector<pair<ll,ll> > x(N), y(N);
    for (int i = 0; i < N; i++) {
        ll s,t; cin >> s >> t;
        x[i] = make_pair(s,i);
        y[i] = make_pair(t,i);
    }
    //argsortしないとだめ
    sort(x.begin(),x.end());
    sort(y.begin(),y.end());
    for (int i = 0; i < N-1; i++) {
        edge e1, e2;
        e1.u = x[i].second; e2.u = y[i].second;
        e1.v = x[i+1].second; e2.v = y[i+1].second;
        e1.cost = abs(x[i].first-x[i+1].first);
        e2.cost = abs(y[i].first-y[i+1].first);
        es[i] = e1; es[i+N-1] = e2;
    }

    V = N; E = 2 * N - 2;

    ll res = kruskal();
    cout << res << endl;


}

Submission status: Runtime Error

Solution code:
import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])
 
def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    for i in range(len(edge)):
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            n -= 1
            ans += d
    	if n < 1: return ans
    return ans
 
n = int(input())
x, y = [None]*n, [None]*n
dist = [[0] * n for _ in range(n)]
 
for i in range(n):
    a, b = map(int, input().split())
    x[i] = (a, i)
    y[i] = (b, i)
 
x.sort(key=lambda x:x[0])
y.sort(key=lambda y:y[0])
 
edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))
 
del x, y
print(kruskal(n, edge))

Submission status: Runtime Error

Solution code:
par  =[]
N = int(input())

graph = []

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

sort_x = sorted(graph, key=lambda x: x[1])
sort_y = sorted(graph, key=lambda x: x[2])

edges = []

for i in range(len(sort_x)-1):
    i1, a, b = sort_x[i]
    i2, c, d = sort_x[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((i1, i2, w))
    i1, a, b = sort_y[i]
    i2, c, d = sort_y[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((i1, i2, w))


for i in range(N+1):
    par.append(i)



def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

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

def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y

ans = 0
edges = sorted(edges, key=lambda x: x[2])
for edge in edges:
    if not same(edge[0], edge[1]):
        union(edge[0], edge[1])
        ans += edge[2]
print(ans)

Submission status: Runtime Error

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

import itertools
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


def init(n):
  for i in range(N):
    par[i]=i
    rnk[i]=0
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if (rnk[x]<rnk[y]):
    par[x]=y
  else:
    par[y]=x
    if(rnk[x]==rnk[y]):
      rnk[x]+=1
def same(x,y):
    return find(x)==find(y)

N = I()
xlist = []
ylist = []

par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
init(N)

for i in range(N):
  x, y = IL()
  xlist.append([x, i])
  ylist.append([y, i])
xlist.sort()
ylist.sort()


hpop = heapq.heappop
hpush = heapq.heappush

node = []
for i in range(N-1):
  x, xID = xlist[i]
  nextx, nextxID = xlist[i + 1]
  y, yID = ylist[i]
  nexty, nextyID = ylist[i + 1]
  
  hpush(node, [nextx - x, xID, nextxID])
  hpush(node, [nexty - y, yID, nextyID])

ans = 0
while node:
  val, i, j = hpop(node)
  if same(i, j):
    continue
  else:
    unite(i, j)
    ans += val
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
from heapq import heappush, heappop
global G

def input_graph(N, xy):
  comb_list = list(itertools.combinations(xy, 2))
  for i in range(N*(N-1)//2):
    a, b = comb_list[i]
    an, ax, ay = a 
    bn, bx, by = b 
    cost = min(abs(ax-bx), abs(ay-by))
    G[an] += [(cost, bn)]
    G[bn] += [(cost, an)]

def prim(V):
  global G, used 
  edgelist = []
  for e in G[0]:
    heappush(edgelist, e)
  used[0] = True
  res = 0
  while edgelist:
    minedge = heappop(edgelist)
    if used[minedge[1]]:
      continue 
    v = minedge[1]
    used[v] = True 
    for e in G[v]:
      if not used[e[1]]:
        heappush(edgelist, e)
    res += minedge[0]
  return res

def main():
  global G, used
  N = int(input())
  xy = []
  for i in range(N):
    xy += [[i, *list(map(int, input().split()))]]
  G = [[] for _ in range(N)]
  used = [False for _ in range(N)]
  input_graph(N, xy)
  print(prim(N))

if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra,floyd_warshall

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

D = np.zeros((N, N))
for i in range(N):
  for j in range(N):
    D[i][j] = min(abs(L[i][0] - L[j][0]), abs(L[i][1] - L[j][1]))
D2 = floyd_warshall(D)
print (int(np.max(D2)))

Submission status: Runtime Error

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(2000000000)
 
n = int(input())
nodes = []
done = [0 for _ in range(n)]
par = {}
for _ in range(n):
    x, y = map(int,input().split())
    nodes.append((x,y))
    par[(x,y)]=(x,y)
nodesx = sorted(nodes)
nodesy = sorted(nodes,key=lambda z:z[1])
s = []
 
for i in range(n-1):
    xcost =nodesx[i+1][0]-nodesx[i][0]
    ycost =nodesy[i+1][1]-nodesy[i][1]
    s.append((xcost,(nodesx[i+1],nodesx[i])))
    s.append((ycost,(nodesy[i+1],nodesy[i])))
s.sort()
s = deque(s)
def root(node,par):
    if node == par[node]:
        return node
    else:
        par[node] =root(par[node],par)
        return par[node]
def unite(node1,node2,par):
    par[root(node1,par)] = root(node2,par)
ans = 0
count =0
while count < n-1 :
    cost,(node1,node2) = s.popleft()
    root1 =root(node1,par)
    root2 =root(node2,par)
    if root1 != root2:
        unite(node1,node2,par)
        ans +=cost
        count += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(1000000000)
 
n = int(input())
nodes = []
done = [0 for _ in range(n)]
par = {}
for _ in range(n):
    x, y = map(int,input().split())
    nodes.append((x,y))
    par[(x,y)]=(x,y)
nodesx = sorted(nodes)
nodesy = sorted(nodes,key=lambda z:z[1])
s = []
 
for i in range(n-1):
    xcost =nodesx[i+1][0]-nodesx[i][0]
    ycost =nodesy[i+1][1]-nodesy[i][1]
    s.append((xcost,(nodesx[i+1],nodesx[i])))
    s.append((ycost,(nodesy[i+1],nodesy[i])))
s.sort()
s = deque(s)
def root(node,par):
    if node == par[node]:
        return node
    else:
        par[node] =root(par[node],par)
        return par[node]
def unite(node1,node2,par):
    par[root(node1,par)] = root(node2,par)
ans = 0
count =0
while count < n-1 :
    cost,(node1,node2) = s.popleft()
    if root(node1,par) != root(node2,par):
        unite(node1,node2,par)
        ans +=cost
        count += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10000000000000000)
 
n = int(input())
nodes = []
done = [0 for _ in range(n)]
par = {}
for _ in range(n):
    x, y = map(int,input().split())
    nodes.append((x,y))
    par[(x,y)]=(x,y)
nodesx = sorted(nodes)
nodesy = sorted(nodes,key=lambda z:z[1])
s = []
 
for i in range(n-1):
    xcost =nodesx[i+1][0]-nodesx[i][0]
    ycost =nodesy[i+1][1]-nodesy[i][1]
    s.append((xcost,(nodesx[i+1],nodesx[i])))
    s.append((ycost,(nodesy[i+1],nodesy[i])))
s.sort()
s = deque(s)
def root(node,par):
    if node == par[node]:
        return node
    else:
        par[node] =root(par[node],par)
        return par[node]
def unite(node1,node2,par):
    par[root(node1,par)] = root(node2,par)
ans = 0
count =0
while count < n-1 :
    cost,(node1,node2) = s.popleft()
    if root(node1,par) != root(node2,par):
        unite(node1,node2,par)
        ans +=cost
        count += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
 
 
n = int(input())
nodes = []
done = [0 for _ in range(n)]
par = {}
for _ in range(n):
    x, y = map(int,input().split())
    nodes.append((x,y))
    par[(x,y)]=(x,y)
nodesx = sorted(nodes)
nodesy = sorted(nodes,key=lambda z:z[1])
s = []
 
for i in range(n-1):
    xcost =nodesx[i+1][0]-nodesx[i][0]
    ycost =nodesy[i+1][1]-nodesy[i][1]
    s.append((xcost,(nodesx[i+1],nodesx[i])))
    s.append((ycost,(nodesy[i+1],nodesy[i])))
s.sort()
s = deque(s)
def root(node,par):
    if node == par[node]:
        return node
    else:
        par[node] =root(par[node],par)
        return par[node]
def unite(node1,node2,par):
    par[root(node1,par)] = root(node2,par)
ans = 0
count =0
while count < n-1 :
    cost,(node1,node2) = s.popleft()
    if root(node1,par) != root(node2,par):
        unite(node1,node2,par)
        ans +=cost
        count += 1
print(ans)

Submission status: Runtime Error

Solution code:
import heapq as hq


n = int(input())
nodes = []
done = [0 for _ in range(n)]
par = {}
for _ in range(n):
    x, y = map(int,input().split())
    nodes.append((x,y))
    par[(x,y)]=(x,y)
nodesx = sorted(nodes)
nodesy = sorted(nodes,key=lambda z:z[1])
s = []

for i in range(n-1):
    xcost =nodesx[i+1][0]-nodesx[i][0]
    ycost =nodesy[i+1][1]-nodesy[i][1]
    hq.heappush(s,(xcost,(nodesx[i+1],nodesx[i])))
    hq.heappush(s,(ycost,(nodesy[i+1],nodesy[i])))
def root(node,par):
    if node == par[node]:
        return node
    else:
        par[node] =root(par[node],par)
        return par[node]
def unite(node1,node2,par):
    par[root(node1,par)] = root(node2,par)
ans = 0
count =0
while count < n-1 :
    cost,(node1,node2) = hq.heappop(s)
    if root(node1,par) != root(node2,par):
        unite(node1,node2,par)
        ans +=cost
        count += 1
print(ans)

Submission status: Runtime Error

Solution code:
import heapq as hq


n = int(input())
nodes = []
done = [0 for _ in range(n)]
par = {}
for _ in range(n):
    x, y = map(int,input().split())
    nodes.append((x,y))
    par[(x,y)]=(x,y)
nodesx = sorted(nodes)
nodesy = sorted(nodes,key=lambda z:z[1])
s = []

for i in range(n-1):
    xcost =nodesx[i+1][0]-nodesx[i][0]
    ycost =nodesy[i+1][1]-nodesy[i][1]
    hq.heappush(s,(xcost,(nodesx[i+1],nodesx[i])))
    hq.heappush(s,(ycost,(nodesy[i+1],nodesy[i])))
def root(node,par):
    if node == par[node]:
        return node
    else:
        par[node] =root(par[node],par)
        return par[node]
def unite(node1,node2,par):
    par[root(node1,par)] = root(node2,par)
ans = 0
while s :
    cost,(node1,node2) = hq.heappop(s)
    if root(node1,par) != root(node2,par):
        unite(node1,node2,par)
        ans +=cost
print(ans)

Submission status: Runtime Error

Solution code:

n = int(input())
nords = []
done = [0 for _ in range(n)]
for _ in range(n):
    x, y = map(int,input().split())
    nords.append((x,y))

ans = 0
tree = [nords[0]]
done[0] = 1
count = 0
while count <n-1:
    cost = float("inf")
    merge = ()
    donei = 0
    for (xt, yt) in tree:
        for i,(xi,yi) in enumerate(nords):

            if not done[i]:
                if min(abs(xt-xi),abs(yt-yi)) <cost:
                    cost = min(abs(xt-xi),abs(yt-yi))
                    merge = (xi,yi)
                    donei = i
    ans += cost
    tree.append(merge)
    done[donei] =1 
    count +=1
print(ans) 
        
n = int(input())
nords = []
done = [0 for _ in range(n)]
for _ in range(n):
    x, y = map(int,input().split())
    nords.append((x,y))

ans = 0
tree = [nords[0]]
done[0] = 1
count = 0
while count <n-1:
    cost = float("inf")
    merge = ()
    donei = 0
    for (xt, yt) in tree:
        for i,(xi,yi) in enumerate(nords):

            if not done[i]:
                if min(abs(xt-xi),abs(yt-yi)) <cost:
                    cost = min(abs(xt-xi),abs(yt-yi))
                    merge = (xi,yi)
                    donei = i
    ans += cost
    tree.append(merge)
    done[donei] =1 
    count +=1
print(ans)

Submission status: Runtime Error

Solution code:
class uf_tree():

    def __init__(self,n):
        self.n = n
        self.par = [i for i in range(n)]

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,child,mas):
        if self.root(child) == self.root(mas):
            return
        else:
            self.par[self.root(child)] = self.root(mas)

    def root(self,i):
        if self.par[i] == i:
            return i
        else:
            self.par[i] = self.root(self.par[i])
            return self.par[i]

    def same(self,x,y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False
def kruscal(n,edge_arr):
    edge_arr.sort(key=lambda x:x[2])
    ans = []
    tree = uf_tree(n)
    for e in edge_arr:
        s = e[0]-1
        g = e[1]-1
        if tree.same(s,g):
            continue
        else:
            ans.append(e)
            tree.unite(s,g)
    return ans

n = int(input())
p = [[0,0,0] for i in range(n)]
edge = []
for i in range(n):
    x,y = map(int,input().split())
    p[i][0] = x
    p[i][1] = y
    p[i][2] = i+1

p.sort(key = lambda x:x[0])
for i in range(n-1):
    cost = min(abs(p[i+1][0]-p[i][0]),abs(p[i+1][1]-p[i][1]))
    edge.append([p[i][2],p[i+1][2],cost])

p.sort(key = lambda x:x[1])
for i in range(n-1):
    cost = min(abs(p[i+1][0]-p[i][0]),abs(p[i+1][1]-p[i][1]))
    edge.append([p[i][2],p[i+1][2],cost])

ans = kruscal(n,edge)
# print(ans)
tot = 0
for e in ans:
    tot += e[2]
print(tot)

Submission status: Runtime Error

Solution code:
#D問題
def find(A,x) -> int:
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

import heapq

N = int(input())

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

XY0.sort()
XY1 = sorted(XY1, key=lambda x: x[1])

E = []
for i,x in enumerate(XY0):
    if i == 0:
        ox = x[0]
        oi = x[2]
    else:
        dx = x[0]-ox
        ox = x[0]
        heapq.heappush(E,[dx,oi,x[2]])
        oi = x[2]

for i,y in enumerate(XY1):
    if i == 0:
        oy = y[1]
        oi = y[2]
    else:
        dy = y[1]-oy
        oy = y[1]
        heapq.heappush(E,[dy,oi,y[2]])
        oi = y[2]


uf = UnionFind(N)
V = [i for i in range(N)]
ans = 0
while E:
    w,s,t = heapq.heappop(E)
    if find(V,s) != find(V,t):
        union(V,s,t)
        ans+=w
        
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    x, a, b = LI()
    if b <= a:
        print("delicious")
    elif b <= a + x:
        print("safe")
    else:
        print("dangerous")

    return

#B
def B():
    n = II()
    a = IR(n)
    check = [False] * (n + 1)
    check[1] = True
    now = a[0]
    for i in range(1,n+1):
        if check[now]:
            break
        if now == 2:
            print(i)
            return
        check[now] = True
        now = a[now - 1]
    print(-1)
    return

#C
def C():
    return

#D
def D():
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]
    
    def same(x,y):
        return root(x) == root(y)
    
    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    n = I()
    v = LIR(n)
    l = [None for i in range(2*n-2)]
    for i in range(n):
        v[i].append(i)
    par = [i for i in range(n)]
    rank = [0 for i in range(n)]
    v.sort(key = lambda x:x[0])
    for i in range(n-1):
        l[i] = [v[i][2],v[i+1][2],v[i+1][0]-v[i][0]]
    v.sort(key = lambda x:x[1])
    for i in range(n-1):
        l[i+n-1] = [v[i][2],v[i+1][2],v[i+1][1]-v[i][1]]
    l.sort(key = lambda x:x[2])
    k = 0
    ans = 0
    for i in range(2*n-2):
        x,y,c = l[i]
        if not same(x,y):
            k += 1
            ans += c
            unite(x,y)
        if k == n-1:break
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    x, a, b = LI()
    if b <= a:
        print("delicious")
    elif b <= a + x:
        print("safe")
    else:
        print("dangerous")

    return

#B
def B():
    n = II()
    a = IR(n)
    check = [False] * (n + 1)
    check[1] = True
    now = a[0]
    for i in range(1,n+1):
        if check[now]:
            break
        if now == 2:
            print(i)
            return
        check[now] = True
        now = a[now - 1]
    print(-1)
    return

#C
def C():
    return

#D
def D():
    def find(x):
        if x == par[x]:
            return x
        par[x] = find(par[x])
        return par[x]
    def same(x, y):
        return find(x) == find(y)
    def unite(x, y):
        x = find(x)
        y = find(y)
        par[y] = x
        return True
    n = II()
    par = [i for i in range(n)]
    xy = [None] * n
    for i in range(n):
        xy[i] = [LI()+[i]]
    xy.sort(key=lambda x: x[0])
    edg = [None] * (2 * n - 2)
    a = 0
    for i in range(n-1):
        edg[a + i] = [xy[i][0] - xy[i + 1][0], xy[i][2], xy[i + 1][2]]
    xy.sort(key=lambda x: x[1])
    a = n - 1
    for i in range(n-1):
        edg[a + i] = [xy[i][1] - xy[i + 1][1], xy[i][2], xy[i + 1][2]]
    ans = 0
    a = 0
    edg.sort(key=lambda x: x[0])
    for i in range(2 * n - 2):
        value, p0, p1 = edg[i]
        if a == n - 1:
            break
        if not same(p0, p1):
            unite(p0, p1)
            a += 1
            ans += value
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    x, a, b = LI()
    if b <= a:
        print("delicious")
    elif b <= a + x:
        print("safe")
    else:
        print("dangerous")

    return

#B
def B():
    n = II()
    a = IR(n)
    check = [False] * (n + 1)
    check[1] = True
    now = a[0]
    for i in range(1,n+1):
        if check[now]:
            break
        if now == 2:
            print(i)
            return
        check[now] = True
        now = a[now - 1]
    print(-1)
    return

#C
def C():
    return

#D
def D():
    def find(x):
        if x == par[x]:
            return x
        par[x] = find(par[x])
        return par[x]
    def same(x, y):
        return find(x) == find(y)
    def unite(x, y):
        x = find(x)
        y = find(y)
        par[y] = x
        return True
    def solve(a, k):
        for i in range(n-1):
            q0, q1 = xy[i][k], xy[i + 1][k]
            z, v = xy[i][2], xy[i + 1][2]
            edg[a + i] = [q1 - q0, z, v]
    n = II()
    par = [i for i in range(n)]
    xy = [None] * n
    for i in range(n):
        x, y = LI()
        xy[i] = [x, y, i]
    xy.sort(key=lambda x: x[0])
    edg = [None] * (2 * n - 2)
    solve(0, 0)
    xy.sort(key=lambda x: x[1])
    solve(n - 1, 1)
    ans = 0
    a = 0
    edg.sort(key=lambda x: x[0])
    for i in range(2 * n - 2):
        value, p0, p1 = edg[i]
        if a == n - 1:
            break
        if not same(p0, p1):
            unite(p0, p1):
            a += 1
            ans += value
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()