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: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self,size):
        self.data=[-1 for i in range(size)]
    def root(self,x):
        if self.data[x]<0:
            return x
        else:
            self.data[x]=self.root(self.data[x])
            return self.data[x]
    def united(self,x,y):
        return self.root(x)==self.root(y)
    def unite(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x!=y:
            x,y=sorted((x,y))
            self.data[x]+=self.data[y]
            self.data[y]=x
    def dump(self):
        print(self.data)

n=int(input())
uf=UnionFind(n)
lx=[]
ly=[]
for i in range(n):
    s=input().split()
    x=int(s[0])
    y=int(s[1])
    lx.append((x,i))
    ly.append((y,i))
lx.sort()
ly.sort()
l=[]
for i in range(n-1):
    l.append((lx[i+1][0]-lx[i][0],lx[i+1][1],lx[i][1]))
    l.append((ly[i+1][0]-ly[i][0],ly[i+1][1],ly[i][1]))
l.sort()
res=0
for p in l:
    if not uf.united(p[1],p[2]):
        res+=p[0]
        uf.unite(p[1],p[2])
print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappop, heappush
def inpl(): return map(int, input().split())
N = int(input())

X = []
Y = []

for i in range(N):
    x, y = inpl()
    X.append((i, x))
    Y.append((i, y))

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

G = [[] for _ in range(N)]
for i in range(N-1):
    Xa, Xb = X[i], X[i+1]
    Ya, Yb = Y[i], Y[i+1]
    G[Xa[0]].append([Xb[0], Xb[1]-Xa[1]])
    G[Xb[0]].append([Xa[0], Xb[1]-Xa[1]])
    
    G[Ya[0]].append([Yb[0], Yb[1]-Ya[1]])
    G[Yb[0]].append([Ya[0], Yb[1]-Ya[1]])

visited = [False]*N
Q = [(0, 0)]
ans = 0

while Q:
    c, n = heappop(Q)
    if visited[n]:
        continue
    visited[n] = True
    ans += c
    
    for m, d in G[n]:
        if visited[m]:
            continue
        else:
            heappush(Q, (d, m))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8

INF = 10**9 + 1
n = int(input())
V = []

for _ in range(n):
    line = input().split(" ")
    V.append((int(line[0]), int(line[1])))

def cost(vi, ui):
    v = V[vi]
    u = V[ui]
    return min(abs(v[0]-u[0]), abs(v[1]-u[1]))

mincost = [INF for _ in range(n)]
used = [False for _ in range(n)]

mincost[0] = 0
ret = 0

while True:
    v = -1
    for u in range(n):
        if not used[u] and (v==-1 or mincost[u]<mincost[v]):
            v = u
    if v==-1:
        break

    used[v] = True
    ret += mincost[v]

    for u in range(n):
        mincost[u] = min(mincost[u], cost(v,u))

print(ret)

Submission status: Time Limit Exceeded

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

def build_road_2():
	n = int(raw_input())
	cords = []
	for i in range(n):
		cords.append([int(e) for e in raw_input().split(" ")])
	cords = np.array(cords)
	x_cord = cords[:, 0]
	y_cord = cords[:, 1]
	# print x_cord
	sorted_indecies_x = np.argsort(x_cord)
	# print sorted_indecies_x
	sorted_indecies_y = np.argsort(y_cord)
	mutual_distance = lil_matrix((n, n), dtype=int)
	dict_edge_weight = defaultdict(list)
	for i in range(n-1):
		s1 = sorted_indecies_x[i]
		d1 = sorted_indecies_x[i+1]
		dis1 = abs(x_cord[s1]-x_cord[d1])
		dict_edge_weight[(s1, d1)].append(dis1)
		s2 = sorted_indecies_y[i]
		d2 = sorted_indecies_y[i + 1]
		dis2 = abs(y_cord[s2] - y_cord[d2])
		dict_edge_weight[(s2, d2)].append(dis2)
	for key, value in dict_edge_weight.iteritems():
		mutual_distance[key[0], key[1]] = min(value)
	ans = minimum_spanning_tree(mutual_distance)
	ans = ans.toarray().astype(int)
	print ans.sum()


if __name__ == "__main__":
	build_road_2()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N=int(input())
pos_mat=np.zeros((N,2))
for i in range(N):
    buf=input().split()
    pos_mat[i,0]=int(buf[0])
    pos_mat[i,1]=int(buf[1])
        
minCost_arr=np.array([float("inf") for _ in range(N)])
used_arr=np.zeros(N, dtype=bool)
minCost_arr[0]=0

totalCost=0
while np.sum(used_arr)<N:
    
    idx=np.arange(N)[~used_arr]
    u=idx[np.argmin(minCost_arr[idx])]
    
    totalCost+=minCost_arr[u]
    used_arr[u]=True
    for v in range(N):
        edgeCost=min(abs(pos_mat[u, 0]-pos_mat[v,0]), abs(pos_mat[u, 1]-pos_mat[v,1]))
        minCost_arr[v]=min(minCost_arr[v], edgeCost)
print(int(totalCost))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop

n = int(input())
cities = [tuple(map(int, input().split())) for _ in range(n)]
visited = {0}
x0, y0 = cities[0]
queue = [(min(abs(xi - x0), abs(yi - y0)), i) for i, (xi, yi) in enumerate(cities) if i not in visited]
heapify(queue)
total = 0
while True:
    cost, i = heappop(queue)
    if i in visited:
        continue
    visited.add(i)
    total += cost
    if len(visited) == n:
        break
    xi, yi = cities[i]
    for j, (xj, yj) in enumerate(cities):
        if j in visited:
            continue
        heappush(queue, (min(abs(xj - xi), abs(yj - yi)), j))
print(total)

Submission status: Time Limit Exceeded

Solution code:
# D
import numpy as np
N = int(input())
X = []
Y = []

for i in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)

# edges
X_s = np.argsort(np.array(X))
Y_s = np.argsort(np.array(Y))

edge_list = []
edge_weight = []
for i in range(N-1):
    edge_list.append([X_s[i], X_s[i+1]])
    edge_weight.append(min(abs(X[X_s[i+1]] - X[X_s[i]]), abs(Y[X_s[i+1]] - Y[X_s[i]])))
    edge_list.append([Y_s[i], Y_s[i+1]])
    edge_weight.append(min(abs(X[Y_s[i+1]] - X[Y_s[i]]), abs(Y[Y_s[i+1]] - Y[Y_s[i]])))
    
# sort edges
sel = np.argsort(np.array(edge_weight))

# union find tree
uf = np.arange(N)


res = 0
flg = np.zeros(N)

for s in sel:
    m, n = edge_list[s]
    # find union
    gr_m = m
    gr_m_list = []
    gr_n = n
    gr_n_list = []
    while gr_m != uf[gr_m]:
        gr_m_list.append(gr_m)
        gr_m = uf[gr_m]
    for m_ in gr_m_list:
        uf[m_] = gr_m
        
    while gr_n != uf[gr_n]:
        gr_n_list.append(gr_n)
        gr_n = uf[gr_n]
    for n_ in gr_n_list:
        uf[n_] = gr_n
        
    if gr_m == gr_n:
        pass
    else:
        res += edge_weight[s]
        uf[gr_n] = gr_m
print(res)

Submission status: Time Limit Exceeded

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

import array
import collections
import heapq
import itertools


AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
Town = collections.namedtuple("Town", "idx x y")
INF = 2 ** 31 - 1
NO_VERTEX = -1


# Prim法で頂点0からの最小全域木を求める
def compute_mst_prim(max_v, adj_list):
    # pred[u]は頂点uの「ひとつ前」の頂点を表す
    pred = collections.defaultdict(lambda: NO_VERTEX)
    # uとpred[u]を結ぶ辺の重みがkey[u]に入る
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    # 二分ヒープを優先度付きキューとして用いる
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    # 優先度付きキューに頂点が入っているかを示す配列
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)


def solve(n, towns):
    txs = sorted(towns, key=lambda t: t.x)
    tys = sorted(towns, key=lambda t: t.y)
    adj_list = collections.defaultdict(set)
    g = itertools.chain(zip(txs[:-1], txs[1:]), zip(tys[:-1], tys[1:]))
    for t1, t2 in g:
        cost = min(abs(t1.x - t2.x), abs(t1.y - t2.y))
        adj_list[t1.idx].add(AdjacentVertex(t2.idx, cost))
        adj_list[t2.idx].add(AdjacentVertex(t1.idx, cost))
    (_, key) = compute_mst_prim(n, adj_list)
    return sum(key.values())


def main():
    n = int(input())
    towns = []
    for idx in range(n):
        x, y = (int(z) for z in input().split())
        towns.append(Town(idx, x, y))
    res = solve(n, towns)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# D
import numpy as np
N = int(input())
X = np.zeros(N, dtype=int)
Y = np.zeros(N, dtype=int)

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

# edges
X_s = np.argsort(X)
Y_s = np.argsort(Y)

edge_list = []
edge_weight = []
for i in range(N-1):
    edge_list.append([X_s[i], X_s[i+1]])
    edge_weight.append(min(abs(X[X_s[i+1]] - X[X_s[i]]), abs(Y[X_s[i+1]] - Y[X_s[i]])))
    edge_list.append([Y_s[i], Y_s[i+1]])
    edge_weight.append(min(abs(X[Y_s[i+1]] - X[Y_s[i]]), abs(Y[Y_s[i+1]] - Y[Y_s[i]])))
    
# sort edges
sel = np.argsort(np.array(edge_weight))

# union find tree
uf = dict()
for i in range(N):
    uf[i] = i

res = 0
flg = np.zeros(N)

for s in sel:
    m, n = edge_list[s]
    # find union
    gr_m = m
    gr_m_list = []
    gr_n = n
    gr_n_list = []
    while gr_m != uf[gr_m]:
        gr_m_list.append(gr_m)
        gr_m = uf[gr_m]
    for m_ in gr_m_list:
        uf[m_] = gr_m
        
    while gr_n != uf[gr_n]:
        gr_n_list.append(gr_n)
        gr_n = uf[gr_n]
    for n_ in gr_n_list:
        uf[n_] = gr_n
    if gr_m == gr_n:
        pass
    else:
        res += edge_weight[s]
        uf[gr_n] = gr_m
print(res)

Submission status: Time Limit Exceeded

Solution code:
# D
import numpy as np
N = int(input())
X = np.zeros(N, dtype=int)
Y = np.zeros(N, dtype=int)

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

# edges
X_s = np.argsort(X)
Y_s = np.argsort(Y)

edge_list = []
edge_weight = []
for i in range(N-1):
    edge_list.append([X_s[i], X_s[i+1]])
    edge_weight.append(min(abs(X[X_s[i+1]] - X[X_s[i]]), abs(Y[X_s[i+1]] - Y[X_s[i]])))
    edge_list.append([Y_s[i], Y_s[i+1]])
    edge_weight.append(min(abs(X[Y_s[i+1]] - X[Y_s[i]]), abs(Y[Y_s[i+1]] - Y[Y_s[i]])))
    
# sort edges
sel = np.argsort(np.array(edge_weight))

# union find tree
uf = dict()
for i in range(N):
    uf[i] = [i, 0]

res = 0
flg = np.zeros(N)

for s in sel:
    m, n = edge_list[s]
    # find union
    gr_m = m
    gr_n = n
    dep_m = 0
    dep_n = 0
    while gr_m != uf[gr_m][0]:
        gr_m = uf[gr_m][0]
        dep_m += 1
    uf[gr_m][1] = max(uf[gr_m][1], dep_m)
    uf[m] = [gr_m, dep_m]
    while gr_n != uf[gr_n][0]:
        gr_n = uf[gr_n][0]
        dep_n += 1
    uf[gr_n][1] = max(uf[gr_n][1], dep_n)
    uf[n] = [gr_n, dep_n]
    if gr_m == gr_n:
        pass
    else:
        res += edge_weight[s]
        if dep_m > dep_n:
            uf[gr_n] = [gr_m, dep_m]
        elif dep_m > dep_n:
            uf[gr_n] = [gr_m, dep_m+1]
        else:
            uf[gr_m] = [gr_n, dep_n]
print(res)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
 
 
def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}
 
 
def read():
    N = II()
    x, y = [], []
    for __ in range(N):
        _x, _y = ILI()
        x.append(_x)
        y.append(_y)
    return N, x, y
 
 
class UnionFind(object):
    def __init__(self, number_of_nodes):  # 初期化
        self.par = array.array("L", range(number_of_nodes))
        self.rank = array.array("L", (0 for i in range(number_of_nodes)))
 
    def root(self, node):  # 根を求める
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r  # 経路圧縮
            return r
 
    def in_the_same_set(self, node1, node2):  # 同じ集合に属するか
        return self.root(node1) == self.root(node2)
 
    def unite(self, node1, node2):  # 属する集合を併合
        x = self.root(node1)
        y = self.root(node2)
        if x == y:
            pass
        elif self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
 
def solve(N, x, y):
    edges = []
    for i in range(N):
        for j in range(i + 1, N):
            edges.append((min(abs(x[i] - x[j]), abs(y[i] - y[j])) , i, j))
    
    edges.sort(key=lambda x: x[0])
    union_find = UnionFind(N)
    ans = 0
    count = 0
    for edge in edges:
        if count == N - 1:
            break
        if not union_find.in_the_same_set(edge[1], edge[2]):
            union_find.unite(edge[1], edge[2])
            ans += edge[0]
            count += 1
    
    return ans
 
 
def main():
    params = read()
    print(solve(*params))
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

p.sort()
q.sort()
pid = [0 for i in range(n)]
qid = [0 for i in range(n)]
for i in range(n):
    pid[p[i][2]] = i
    qid[q[i][2]] = i
used = [False] * n

total = 0

hq = [(0, 0)]
cnt = 0
s = set()
while hq and cnt < n:
    c, i = heapq.heappop(hq)
    # print(c, i)
    if i not in s:
        cnt += 1
        s.add(i)
        total += c
    else:
        continue
    pi = pid[i]
    qi = qid[i]
    if pi > 0 and p[pi-1][2] not in s:
        heapq.heappush(hq, (p[pi][0] - p[pi-1][0], p[pi-1][2]))
    if pi < n-1 and p[pi+1][2] not in s:
        heapq.heappush(hq, (p[pi+1][0] - p[pi][0], p[pi+1][2]))
    if qi > 0 and q[qi-1][2] not in s:
        heapq.heappush(hq, (q[qi][0] - q[qi-1][0], q[qi-1][2]))
    if qi < n-1 and q[qi+1][2] not in s:
        heapq.heappush(hq, (q[qi+1][0] - q[qi][0], q[qi+1][2]))
    
        

print(total)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                # 小さいほうが個数が多い
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    # 部分集合とその要素数を返す
    def subsetall(self):
        a = []
        for i in xrange(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a


N=int(input())
x=[]
y=[]
for i in range(N):
  a,b=map(int,input().split())
  x+=[ a]
  y+=[ b]
costs=[]
for i in range(N):
  for j in range(i):
    costs+=[(min(abs(x[i]-x[j]),abs(y[i]-y[j])),i,j)]
costs.sort()

S=0#既に引かれた線の本数
ans=0
s=UnionFind(N)
S=0
while S<N-1:#N-1本効率よく引けば、終わり。
  for cost in costs:
    #もしcost[1]とcost[2]が同じ連結成分に入っていたら、飛ばす。
    #入っていなかったら、ansにcost[0]を追加し、cost[2]の集合はcost[1]に合併し、S+=1する.
    if S==N-1:
      break
    if s.find(cost[1])!=s.find(cost[2]):
      ans+=cost[0]
      s.union(cost[1],cost[2])
      S+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
x=[]
y=[]
for i in range(N):
  a,b=map(int,input().split())
  x+=[ a]
  y+=[ b]
costs=[]
for i in range(N):
  for j in range(i):
    costs+=[(min(abs(x[i]-x[j]),abs(y[i]-y[j])),i,j)]
costs.sort()

S=0#既に引かれた線の本数
ans=0
Dict={}
for i in range(N):
  Dict[i]=i
S=0
while S<N-1:#N-1本効率よく引けば、終わり。
  for cost in costs:
    #もしcost[1]とcost[2]が同じ連結成分に入っていたら、飛ばす。
    #入っていなかったら、ansにcost[0]を追加し、cost[2]の集合はcost[1]に合併し、S+=1する.
    if S==N-1:
      break
    if Dict[cost[1]]!=Dict[cost[2]]:
      ans+=cost[0]
      for i in range(N):
        if Dict[i]==Dict[max(cost[1],cost[2])]:
          Dict[i]=Dict[min(cost[1],cost[2])]
      S+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N = II()
    x, y = [], []
    for __ in range(N):
        _x, _y = ILI()
        x.append(_x)
        y.append(_y)
    return N, x, y


AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
NO_VERTEX = -1


def compute_mst_prim(max_v, adj_list):
    # pred[u]は頂点uの「ひとつ前」の頂点を表す
    pred = collections.defaultdict(lambda: NO_VERTEX)
    # uとpred[u]を結ぶ辺の重みがkey[u]に入る
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    # 二分ヒープを優先度付きキューとして用いる
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    # 優先度付きキューに頂点が入っているかを示す配列
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)


def solve(N, x, y):
    edges = []
    for i in range(N):
        for j in range(i + 1, N):
            edges.append((min(abs(x[i] - x[j]), abs(y[i] - y[j])) , i, j))

    adjacency_list = collections.defaultdict(set)

    for ind, (w, s, t) in enumerate(edges):
        adjacency_list[s].add(AdjacentVertex(t, w))
        adjacency_list[t].add(AdjacentVertex(s, w))
    (_, key) = compute_mst_prim(N, adjacency_list)

    ans = sum(key.values())
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
if __name__ == '__main__':
    n = int(input())
    p = [None for i in range(n)]
    for i in range(n):
        p[i] = list(map(int,input().split()))
        p[i].append(i)
    p = sorted(p,key=lambda x:x[0])
    con = p[0]
    coni = [0]
    notused = list(range(1,n))
    d = [[min(abs(p[i][0]-p[0][0]),abs(p[i][1]-p[0][1])),i] for i in range(n)]
    cost = 0
    while len(notused)>0:
        #print(coni)
        #print(notused)
        sortd = sorted(d,key=lambda x:x[0])
        #print(sortd)
        for i in range(n):
            if sortd[i][1] in notused:
                nearind = sortd[i][1]
                break
        minc = 1000000000
        for i in coni:
            if min(abs(p[nearind][0]-p[i][0]),abs(p[nearind][1]-p[i][1]))<minc:
                minc = min(abs(p[nearind][0]-p[i][0]),abs(p[nearind][1]-p[i][1]))
        cost += minc
        con.append(p[nearind])
        coni.append(nearind)
        notused.remove(nearind)
        d = [[min(d[i][0],min(abs(p[nearind][0]-p[i][0]),abs(p[nearind][1]-p[i][1]))),i] for i in range(n)]
        #print(cost)
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N = II()
    x, y = [], []
    for __ in range(N):
        _x, _y = ILI()
        x.append(_x)
        y.append(_y)
    return N, x, y


class UnionFind(object):
    def __init__(self, number_of_nodes):  # 初期化
        self.par = array.array("L", range(number_of_nodes))
        self.rank = array.array("L", (0 for i in range(number_of_nodes)))

    def root(self, node):  # 根を求める
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r  # 経路圧縮
            return r

    def in_the_same_set(self, node1, node2):  # 同じ集合に属するか
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):  # 属する集合を併合
        x = self.root(node1)
        y = self.root(node2)
        if x == y:
            pass
        elif self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def solve(N, x, y):
    edges = []
    for i in range(N):
        for j in range(i + 1, N):
            edges.append((min(abs(x[i] - x[j]), abs(y[i] - y[j])) , i, j))
    
    edges.sort(key=lambda x: x[0])
    union_find = UnionFind(N)
    ans = 0
    for edge in edges:
        if not union_find.in_the_same_set(edge[1], edge[2]):
            union_find.unite(edge[1], edge[2])
            ans += edge[0]
    
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
x=[]
y=[]
for i in range(N):
  a,b=map(int,input().split())
  x+=[ a]
  y+=[ b]
cost=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
  for j in range(N):
    cost[i][j]=min(abs(x[i]-x[j]),abs(y[i]-y[j]))
    cost[j][i]=cost[i][j]
used=[0]+[0]*(N-1)#0番目のみが入っている
mincost=[0]+[10**9]*(N-1)
res=0

while True:
  v=-1
  for u in range(N):
    if used[u]==0 and (v==-1 or mincost[u]<mincost[v]):
      v=u
  if v==-1:
    break
  used[v]=1
  res+=mincost[v]
  for u in range(N):
    mincost[u]=min(mincost[u],cost[v][u])
print(res)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n = int(input())
xy = []
yx = []
for i in range(n):
    xi, yi = map(int, input().split())
    xy.append((xi, yi, i))
    yx.append((yi, xi, i))
xy = list(sorted(xy))
yx = list(sorted(yx))
gr = {u: [] for u in range(n)}
for i in range(n - 1):
    u = xy[i][2]
    v = xy[i + 1][2]
    c = min(abs(xy[i + 1][0] - xy[i][0]), abs(xy[i + 1][1] - xy[i][1]))
    gr[u].append((c, v))
    gr[v].append((c, u))
    u = yx[i][2]
    v = yx[i + 1][2]
    c = min(abs(yx[i + 1][0] - yx[i][0]), abs(yx[i + 1][1] - yx[i][1]))
    gr[u].append((c, v))
    gr[v].append((c, u))
added = [False for _ in range(n + 1)]
cnt = 1
ans = 0
hq = []
heapq.heappush(hq, (0, 1))
while 0 < len(hq):
    c, u = heapq.heappop(hq)
    if not added[u]:
        added[u] = True
        ans += c
        for p in gr[u]:
            heapq.heappush(hq, p)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N = II()
    x, y = [], []
    for __ in range(N):
        _x, _y = ILI()
        x.append(_x)
        y.append(_y)
    return N, x, y


def solve(N, x, y):
    cost = [[INF] * N for __ in range(N)]
    for i in range(N):
        for j in range(N):
            x_i, y_i = x[i], y[i]
            x_j, y_j = x[j], y[j]
            cost[i][j] = min(abs(x_i - x_j), abs(y_i - y_j))

    min_cost = [INF] * N
    bool_used = [False] * N

    ans = 0
    min_cost[0] = 0
    while True:
        v = -1
        for i in range(N):
            if bool_used[i] is False and (v == -1 or min_cost[i] < min_cost[v]):
                v = i

        if v == -1:
            break
        bool_used[v] = True
        ans += min_cost[v]
        for i in range(N):
            min_cost[i] = min(min_cost[i], cost[v][i])

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#定数
INF=1000000

#入力
N=int(input())
xy=[[int(j) for j in input().split()] for i in range(N)]

#index0の町からの連結部分と、連結していないところ
linked=[0]
noLink=[i for i in range(1,N)]

#所要金額
ans=0

#index0の町から連結していきます
#(新しい街を連結していけばN-1回の連結で終了)
for roop in range(N-1):
	#連結に必要な最低金額と街
	minMoney=INF
	minCity=INF

	#まず、linked側から１つ
	for wasCity in linked:
		#noLinkから1つ
		for newCity in noLink:
			#金額が最小のときにデータ更新
			money = min(abs(xy[wasCity][0]-xy[newCity][0]),abs(xy[wasCity][1]-xy[newCity][1]))
			if money<minMoney:
				minMoney=money
				minCity=newCity
	#1週終わったら、最小を連結
	ans+=minMoney
	linked.append(minCity)
	noLink.remove(minCity)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from networkx.utils import UnionFind
from operator import itemgetter
def input(): return sys.stdin.readline().rstrip()


def main():
    n = int(input())
    city = []
    for i in range(n):
        x, y = map(int, input().split())
        city.append((x, y, i))
    city.sort(key=itemgetter(0))
    kouho = []
    for i in range(n-1):
        kouho.append((city[i+1][0]-city[i][0], city[i][2], city[i+1][2]))
    city.sort(key=itemgetter(1))
    for i in range(n-1):
        kouho.append((city[i+1][1]-city[i][1], city[i][2], city[i+1][2]))
    kouho.sort(key=itemgetter(0))
    ans = 0
    num = n
    uf = UnionFind()
    for road in kouho:
        if uf[road[1]] != uf[road[2]]:
            uf.union(road[1],road[2])
            ans+=road[0]
            num-=1
            if num==1:
                print(ans)
                break


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    
    # 要素数を指定して作成 はじめは全ての要素が別グループに属し、親はいない
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    # xの根を返す
    def find(self, x):
        if self.parents[x] < 0:  return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    # xとyが属するグループを併合
    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
    
    # xが属するグループの要素数
    def size(self, x):  return -self.parents[self.find(x)]
    
    # ｘとyが同じグループか否か
    def same(self, x, y):  return self.find(x) == self.find(y)
    
    # xと同じメンバーの要素
    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())
    
    # 可視化 [print(uf)]
    def __str__(self):  return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def kruskal(G):

    G = sorted(G, key = lambda x: x[2])
    U = UnionFind(len(G))
    res = 0
    for e in G:
        s, t, w = e
        if not U.same(s, t):
            res += w
            U.union(s, t)
    return res

N = int(input())
in_list = []
for i in range(N):
    in1, in2 = list(map(int,input().split()))
    in_list.append([i, in1, in2])
    
x = sorted(in_list, key = lambda x: x[1])
y = sorted(in_list, key = lambda x: x[2])

G = []
for i in range(1, N):
    G.append([x[i - 1][0], x[i][0], x[i][1] - x[i - 1][1]])
    G.append([y[i - 1][0], y[i][0], y[i][2] - y[i - 1][2]])
    
ans = kruskal(G)
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) #親ノード
        self.size = [1]*n #グループの要素数
 
    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 
 
    def merge(self, x, y): #merge(x,y): xのいる組とyのいる組をまとめる
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x #xの要素数が大きいように
        self.size[x] += self.size[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じ組ならTrue
        return self.root(x) == self.root(y)
        
    def getsize(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*xy = map(int,read().split())

mp = iter(xy)
xyi = [(x,y,i) for i,(x,y) in enumerate(zip(mp,mp))]

res = []

xyi.sort()
for (x,y,i),(z,w,j) in zip(xyi[1:],xyi):
    res.append((x-z,i,j))
xyi.sort(key = lambda x:x[1])
for (x,y,i),(z,w,j) in zip(xyi[1:],xyi):
    res.append((y-w,i,j))

#print(res)
res.sort()
UF = UnionFind(n)

num = 1
ans = 0
for d,i,j in res:
    if UF.merge(i,j):
        num += 1
        ans += d
    if num==n: break

print(ans)

Submission status: Accepted

Solution code:
#最小全域木　プリム法
n = int(input())
x = []
for i in range(0,n):
    X,Y = [int(_x) for _x in input().split()]
    x.append((i,X,Y))
x = sorted(x, key=lambda x:x[1])
y = sorted(x, key=lambda x:x[2])

g = [[] for _ in range(n)]
for j in range(1, len(x)):
    _i, _xx, _yy = x[j-1]
    i, xx, yy = x[j]
    dis1 = abs(_xx - xx)
    dis2 = abs(_yy - yy)
    g[i].append((dis1, _i))
    g[i].append((dis2, _i))
    g[_i].append((dis1, i))
    g[_i].append((dis2, i))

for j in range(1, len(y)):
    _i, _xx, _yy = y[j-1]
    i, xx, yy = y[j]
    dis1 = abs(_xx - xx)
    dis2 = abs(_yy - yy)
    g[i].append((dis1, _i))
    g[i].append((dis2, _i))
    g[_i].append((dis1, i))
    g[_i].append((dis2, i))

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

edge = g
print(prim_heap())