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:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([i,xy[0]])
    b.append([i,xy[1]])

a.sort(key=lambda x: x[1])
b.sort(key=lambda x: x[1])
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for i, [j, x] in enumerate(a[:-1]):
    adj[j].append([a[i+1][1]-x, a[i+1][0]])
    adj[a[i+1][0]].append([a[i+1][1]-x, j])
for i, [j, y] in enumerate(b[:-1]):
    adj[j].append([b[i+1][1]-y, b[i+1][0]])
    adj[b[i+1][0]].append([b[i+1][1]-y, j])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
while h:
    cost, node = heapq.heappop(h)
    if visited[node] != True and cost < d[node]:
        d[node] = cost
        visited[node] = True
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(sum(d))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([i,xy[0]])
    b.append([i,xy[1]])

a.sort(key=lambda x: x[1])
b.sort(key=lambda x: x[1])
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for i in range(len(a)-1):
    adj[a[i][0]].append([a[i+1][1]-a[i][1], a[i+1][0]])
    adj[a[i+1][0]].append([a[i+1][1]-a[i][1], a[i][0]])
for i in range(len(b)-1):
    adj[b[i][0]].append([b[i+1][1]-b[i][1], b[i+1][0]])
    adj[b[i+1][0]].append([b[i+1][1]-b[i][1], b[i][0]])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
while h:
    cost, node = heapq.heappop(h)
    if visited[node] != True and cost < d[node]:
        d[node] = cost
        visited[node] = True
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(sum(d))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([i,xy[0]])
    b.append([i,xy[1]])

a.sort(key=lambda x: x[1])
b.sort(key=lambda x: x[1])
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for i in range(len(a)-1):
    adj[a[i][0]].append([a[i+1][1]-a[i][1], a[i+1][0]])
    adj[a[i+1][0]].append([a[i+1][1]-a[i][1], a[i][0]])
for i in range(len(b)-1):
    adj[b[i][0]].append([b[i+1][1]-b[i][1], b[i+1][0]])
    adj[b[i+1][0]].append([b[i+1][1]-b[i][1], b[i][0]])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
while h:
    current = heapq.heappop(h)
    if visited[current[1]] != True and current[0] < d[current[1]]:
        d[current[1]] = current[0]
        visited[current[1]] = True
        cnt += 1
        if cnt == n:
            break
        for edge in adj[current[1]]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(sum(d))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([i,xy[0],xy[1]])
    b.append([i,xy[0],xy[1]])

a.sort(key=lambda x: x[1])
b.sort(key=lambda x: x[2])
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for i in range(len(a)-1):
    adj[a[i][0]].append([a[i+1][1]-a[i][1], a[i+1][0]])
    adj[a[i+1][0]].append([a[i+1][1]-a[i][1], a[i][0]])
for i in range(len(b)-1):
    adj[b[i][0]].append([b[i+1][2]-b[i][2], b[i+1][0]])
    adj[b[i+1][0]].append([b[i+1][2]-b[i][2], b[i][0]])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
while h:
    current = heapq.heappop(h)
    if visited[current[1]] != True and current[0] < d[current[1]]:
        d[current[1]] = current[0]
        visited[current[1]] = True
        cnt += 1
        if cnt == n:
            break
        for edge in adj[current[1]]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(sum(d))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([i,xy[0],xy[1]])
    b.append([i,xy[0],xy[1]])

a.sort(key=lambda x: x[1])
b.sort(key=lambda x: x[2])
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for i in range(len(a)-1):
    adj[a[i][0]].append([a[i+1][1]-a[i][1], a[i+1][0]])
    adj[a[i+1][0]].append([a[i+1][1]-a[i][1], a[i][0]])
for i in range(len(b)-1):
    adj[b[i][0]].append([b[i+1][2]-b[i][2], b[i+1][0]])
    adj[b[i+1][0]].append([b[i+1][2]-b[i][2], b[i][0]])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
while h:
    current = heapq.heappop(h)
    if visited[current[1]] != True and current[0] < d[current[1]]:
        d[current[1]] = current[0]
        visited[current[1]] = True
        for edge in adj[current[1]]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(sum(d))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind(object):
  def __init__(self,n):
    *self.par,=range(n+1)
    self.rank=[0]*(n+1)

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

  def union(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if 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

n=int(input())
x=[[0,0] for _ in range(n)]
y=[[0,0] for _ in range(n)]

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

dx,dy=[],[]
x,y=sorted(x),sorted(y)
for i in range(n-1):
  dx.extend([(abs(x[i][0]-x[i+1][0]),x[i][1],x[i+1][1])])
  dy.extend([(abs(y[i][0]-y[i+1][0]),y[i][1],y[i+1][1])])

target=sorted(dx+dy)
tree=UnionFind(n)
cnt,cost,i=0,0,0

while cnt<n-1:
  c,a,b=target[i]
  if tree.find(a)!=tree.find(b):
    cost+=c
    tree.union(a,b)
    cnt+=1
  i+=1

print(cost)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
N=input()

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

A.sort(key=lambda x:x[1])

hq=[]
for idx,s in enumerate(A):
	i,x,y=s[0],s[1],s[2]
	if idx==0:
		pre_i=i
		pre_x=x
		pre_y=y
	else:
		heappush(hq, (x-pre_x, pre_i, i ) )
		pre_i=i
		pre_x=x
		pre_y=y

A.sort(key=lambda x:x[2])

for idx,s in enumerate(A):
	i,x,y=s[0],s[1],s[2]
	if idx==0:
		pre_i=i
		pre_x=x
		pre_y=y
	else:
		heappush(hq, (y-pre_y, pre_i, i ) )
		pre_i=i
		pre_x=x
		pre_y=y


par=[ i for i in range(N+1)]

def root(x):
	if par[x]==x: return x
	else:
		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 x==y: return
	par[x]=y


ans=0
while hq:
	cost,x,y=heappop(hq)

	if not same(x,y):
		unite(x,y)
		ans+=cost

print ans

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
N=input()

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

A.sort(key=lambda x:x[1])


hq=[]
for i in range(N-1):
	idx1,x1=A[i][0], A[i][1]
	idx2,x2=A[i+1][0],A[i+1][1]
	heappush(hq, (x2-x1, idx1,idx2) )

A.sort(key=lambda x:x[2])


for i in range(N-1):
	idx1,y1=A[i][0], A[i][2]
	idx2,y2=A[i+1][0],A[i+1][2]
	heappush(hq, (y2-y1, idx1,idx2) )


par=[ i for i in range(N+1)]

def root(x):
	if par[x]==x: return x
	else:
		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 x==y: return
	par[x]=y


ans=0
while hq:
	cost,x,y=heappop(hq)

	if not same(x,y):
		unite(x,y)
		ans+=cost

print ans

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


@mt
def slv(N, XY):
    g = defaultdict(dict)
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            d = min(abs(XY[i][0] - XY[j][0]), abs(XY[i][1] - XY[j][1]))
            g[i][j] = d
            g[j][i] = d
    return Prim(g)


def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, XY))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

N = int(input())
town = [[int(x) for x in input().split()] + [i] for i in range(N)]


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

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(dict)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src][dst] = weight

    def get_nodes(self):
        return self.graph.keys()


class Kruskal(object):
    """
    クラスカル法による最小全域木
    O(ElogV)
    """

    def __init__(self, graph):
        self.edge = []
        self.total = 0

        N = len(graph)
        g = graph.graph
        uf = UnionFind(N)

        Q = []
        for src, v in g.items():
            for dst, cost in v.items():
                heappush(Q, (cost, (src, dst)))

        while len(self.edge) < N - 1 and Q:
            cost, edge = heappop(Q)
            if uf.find(edge[0]) != uf.find(edge[1]):
                self.total += cost
                self.edge.append(edge)
                uf.union(*edge)


def built(g, town):
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        dx = abs(t1[0] - t2[0])
        dy = abs(t1[1] - t2[1])
        c = min(dx, dy)
        g.add_edge(t1[2], t2[2], c)
        g.add_edge(t2[2], t1[2], c)
    return g


g = Graph()
g = built(g, sorted(town, key=itemgetter(0)))
g = built(g, sorted(town, key=itemgetter(1)))
print(Kruskal(g).total)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

N = int(input())
town = [[int(x) for x in input().split()] + [i] for i in range(N)]


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

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Kruskal(object):
    """
    クラスカル法による最小全域木
    O(ElogV)
    """

    def __init__(self, graph):
        self.edge = []
        self.total = 0

        N = len(graph)
        g = graph.graph
        uf = UnionFind(N)

        Q = []
        for src, v in g.items():
            for dst, cost in v:
                heappush(Q, (cost, (src, dst)))

        while len(self.edge) < N - 1 and Q:
            cost, edge = heappop(Q)
            if uf.find(edge[0]) != uf.find(edge[1]):
                self.total += cost
                self.edge.append(edge)
                uf.union(*edge)


def built(g, town):
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        dx = abs(t1[0] - t2[0])
        dy = abs(t1[1] - t2[1])
        c = min(dx, dy)
        g.add_edge(t1[2], t2[2], c)
        g.add_edge(t2[2], t1[2], c)
    return g


g = Graph()
g = built(g, sorted(town, key=itemgetter(0)))
g = built(g, sorted(town, key=itemgetter(1)))
print(Kruskal(g).total)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

N = int(input())
town = [[int(x) for x in input().split()] + [i] for i in range(N)]


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Prim(object):
    """
    プリム法（二分ヒープ）による最小全域木
    O((E+V)logV)
    """

    def __init__(self, graph, start=0):
        self.edge = []
        self.total = 0

        g = graph.graph
        n = len(graph)
        visited = [False] * n
        visited[start] = True

        Q = []
        for v, cost in g[start]:
            heappush(Q, (cost, (start, v)))

        while Q:
            cost, e = heappop(Q)

            if visited[e[1]]:
                continue

            self.edge.append(e)
            self.total += cost
            visited[e[1]] = True

            for v, cost in g[e[1]]:
                heappush(Q, (cost, (e[1], v)))


def built(g, town):
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        dx = abs(t1[0] - t2[0])
        dy = abs(t1[1] - t2[1])
        c = min(dx, dy)
        g.add_edge(t1[2], t2[2], c)
        g.add_edge(t2[2], t1[2], c)
    return g


g = Graph()
g = built(g, sorted(town, key=itemgetter(0)))
g = built(g, sorted(town, key=itemgetter(1)))
p = Prim(g)
print(p.total)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

N = int(input())
town = [[int(x) for x in input().split()] + [i] for i in range(N)]


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(dict)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src][dst] = weight

    def get_nodes(self):
        return self.graph.keys()


class Prim(object):
    """
    プリム法（二分ヒープ）による最小全域木
    O((E+V)logV)
    """

    def __init__(self, graph, start=0):
        self.edge = []
        self.total = 0

        g = graph.graph
        n = len(graph)
        visited = [False] * n
        visited[start] = True

        Q = []
        for v, cost in g[start].items():
            heappush(Q, (cost, (start, v)))

        while Q:
            cost, e = heappop(Q)

            if visited[e[1]]:
                continue

            self.edge.append(e)
            self.total += cost
            visited[e[1]] = True

            for v, cost in g[e[1]].items():
                heappush(Q, (cost, (e[1], v)))


def built(g, town):
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        dx = abs(t1[0] - t2[0])
        dy = abs(t1[1] - t2[1])
        c = min(dx, dy)
        g.add_edge(t1[2], t2[2], c)
        g.add_edge(t2[2], t1[2], c)
    return g


g = Graph()
g = built(g, sorted(town, key=itemgetter(0)))
g = built(g, sorted(town, key=itemgetter(1)))
p = Prim(g)
print(p.total)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
V = [[int(x) for x in input().split()] + [i] for i in range(N)]
R = [[i, 1] for i in range(N)]
E = []
for i in range(N - 1):
  for j in range(i + 1, N):
    E.append([i, j, min(abs(V[i][0] - V[j][0]), abs(V[i][1] - V[j][1]))])
E = sorted(E, key=lambda x:x[2])
def root(v):
  if R[v][0] == v:
    return v
  else:
    R[v][0] = root(R[v][0])
    return R[v][0]
C = 0
for e in E:
  r0 = root(e[0])
  r1 = root(e[1])
  if r0 != r1:
    if r0 < r1:
      r = r0
      R[r][1] += R[r1][1]
      R[r1][0] = r
    else:
      r = r1
      R[r][1] += R[r0][1]
      R[r0][0] = r
    C += e[2]
    if R[r][1] == N:
      break
print(C)

Submission status: Time Limit Exceeded

Solution code:
import operator
import numpy as np
n = int(input())
xy = np.array([list(map(int, input().split())) for _ in range(n)])

sa1 = np.argsort(xy[:,0])
sa2 = np.argsort(xy[:,1])

s1 = xy[sa1,0]
s2 = xy[sa2,1]
c1 = s1[1:] - s1[:-1]
c2 = s2[1:] - s2[:-1]

c = [(c, (sa1[i], sa1[i+1])) for i, c in enumerate(c1)] + [(c, (sa2[i], sa2[i+1])) for i, c in enumerate(c2)]
c = sorted(c, key=operator.itemgetter(0))

total_cost = 0
sg = {}
for cost, verts in c:
    vf1 = sg.get(verts[0])
    vf2 = sg.get(verts[1])
    if vf1 and vf2:
        if vf1 is vf2: continue
        total_cost += cost
        vf1.update(vf2)
        for v in vf2: sg[v] = vf1
    else:
        total_cost += cost
        if vf1:
            vf1.add(verts[1])
            sg[verts[1]] = vf1
        elif vf2:
            vf2.add(verts[0])
            sg[verts[0]] = vf2
        else:
            sg[verts[0]] = sg[verts[1]] = set(verts)
print(total_cost)

Submission status: Time Limit Exceeded

Solution code:
import operator
import numpy as np
n = int(input())
xy = np.array([list(map(int, input().split())) for _ in range(n)])

sa1 = np.argsort(xy[:,0])
sa2 = np.argsort(xy[:,1])

s1 = xy[sa1,0]
s2 = xy[sa2,1]
c1 = s1[1:] - s1[:-1]
c2 = s2[1:] - s2[:-1]

c = [(c, (sa1[i], sa1[i+1])) for i, c in enumerate(c1)] + [(c, (sa2[i], sa2[i+1])) for i, c in enumerate(c2)]
c = sorted(c, key=operator.itemgetter(0))

total_cost = 0
sg = {}
for cost, verts in c:
    vf1 = sg.get(verts[0])
    vf2 = sg.get(verts[1])
    if vf1 and vf2:
        if vf1 == vf2: continue
        total_cost += cost
        vf1.update(vf2)
        for v in vf2: sg[v] = vf1
    else:
        total_cost += cost
        if vf1:
            vf1.add(verts[1])
            sg[verts[1]] = vf1
        elif vf2:
            vf2.add(verts[0])
            sg[verts[0]] = vf2
        else:
            sg[verts[0]] = sg[verts[1]] = set(verts)
print(total_cost)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

points=[]
for i in range(N):
    s = input().split()
    xi = int(s[0])
    yi = int(s[1])
    points.append([xi,yi])

# create a distance matrix
d=[]
costfunc = lambda x, y:min(abs(x),abs(y))
for i in range(N):
    d.append([])
    for j in range(N):
        cost=costfunc(points[i][0]-points[j][0],points[i][1]-points[j][1])
        if(i==j):cost=100000
        d[i].append(cost)

V=set(range(N))
Vnew=set([1])
Enew=[]
while(len(Vnew)!=len(V)):
    argmin=[0,0]
    dist=1000000
    for u in Vnew:
        for v in (V-Vnew):
            if(dist>d[u][v]):
                argmin=[u,v]
                dist=d[u][v]
    Vnew.add(argmin[1])
    Enew.append(argmin)

cost=sum([d[u][v] for (u,v) in Enew])

print(cost)

Submission status: Time Limit Exceeded

Solution code:
import operator
import numpy as np
n = int(input())
xy = np.array([list(map(int, input().split())) for _ in range(n)])

sa1 = np.argsort(xy[:,0])
sa2 = np.argsort(xy[:,1])

s1 = xy[sa1,0]
s2 = xy[sa2,1]
c1 = s1[1:] - s1[:-1]
c2 = s2[1:] - s2[:-1]

c = [(c, (sa1[i], sa1[i+1])) for i, c in enumerate(c1)] + [(c, (sa2[i], sa2[i+1])) for i, c in enumerate(c2)]
c = sorted(c, key=operator.itemgetter(0))

total_cost = 0
sg = []
for cost, verts in c:
    vf1, vf2 = None, None
    for g in sg:
        if verts[0] in g: vf1 = g
        if verts[1] in g: vf2 = g
        if vf1 and vf2:
            if vf1 == vf2: break
            total_cost += cost
            vf1.update(vf2)
            sg.remove(vf2)
            break
    else:
        total_cost += cost
        if vf1:
            vf1.add(verts[1])
        elif vf2:
            vf2.add(verts[0])
        else:
            sg.append(set(verts))
print(total_cost)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
xy = [[int(_) for _ in input().split()] for i in range(N)]

from heapq import *

isused = [0] * N

h = []

heappush(h, (0, 0))

result = 0

while h:
    d, n = heappop(h)
    if isused[n]:
        continue
    result += d
    isused[n] = 1
    for i in range(N):
        if not isused[i]:
            d1 = min(abs(xy[n][0] - xy[i][0]), abs(xy[n][1] - xy[i][1]))
            heappush(h, (d1, i))
    
print(result)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = []
y = []
for i in range(n):
    s = list(map(int, input().split()))
    x.append([s[0], i])
    y.append([s[1], i])

x.sort()
y.sort()

xdiff = []
ydiff = []
for i in range(1, n):
    xdiff.append([x[i][0] - x[i - 1][0], x[i - 1][1], x[i][1]])
    ydiff.append([y[i][0] - y[i - 1][0], y[i - 1][1], y[i][1]])

xdiff.sort()
ydiff.sort()

parent = [-1] * n

def getParent(index):
    while parent[index] != -1:
        index = parent[index]

    return index

count = 0
ans = 0
xIndex = 0
yIndex = 0
while count != n - 1:
    if xIndex != n - 1:
        xTemp = xdiff[xIndex]
    if yIndex != n - 1:
        yTemp = ydiff[yIndex]

    if yIndex == n - 1 or (xIndex != n - 1 and xTemp[0] < yTemp[0]):
        xIndex += 1
        temp = xTemp
    else:
        yIndex += 1
        temp = yTemp

    parent1 = getParent(temp[1])
    parent2 = getParent(temp[2])
    if parent1 == parent2:
        continue
    else:
        count += 1
        ans += temp[0]
        parent[parent1] = parent2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from heapq import heappush,heappop
import sys
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[[] for i in range(N)]
for k in range(N-1):#距離、点
    graph[A[k][2]].append([abs(A[k][0]-A[k-1][0]),A[k-1][2]])
    graph[A[k][2]].append([abs(A[k][0]-A[k+1][0]),A[k+1][2]])
graph[A[N-1][2]].append([abs(A[N-1][0]-A[N-2][0]),A[N-2][2]])
for k in range(N-1):
    graph[B[k][2]].append([abs(B[k][1]-B[k-1][1]),B[k-1][2]])
    graph[B[k][2]].append([abs(B[k][1]-B[k+1][1]),B[k+1][2]])
graph[B[N-1][2]].append([abs(B[N-1][1]-B[N-2][1]),B[N-2][2]])
#プリム法
kei = []
visit=[False]*N
heappush(kei,[0,0])#距離,点
dist = 0
point =0
while kei:
    d,i = heappop(kei)
    if point ==N:
        print(dist)
        sys.exit()
    if visit[i]==True:
        continue
    visit[i]=True
    dist += d
    point+=1
    for e,j in graph[i]:
        if not visit[j]:
            heappush(kei,[e,j])

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from heapq import heappush,heappop
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[]
for k in range(N):#距離、点
    graph.append([min(abs(A[k][0]-A[k-1][0]),abs( A[k][1]-A[k-1][1])),A[k][2],A[k-1][2]])
for k in range(N):
    graph.append([min(abs(B[k][0]-B[k-1][0]),abs( B[k][1]-B[k-1][1])),B[k][2],B[k-1][2]])

class Unionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)

    def find(self,x):#親を探す xの親を示す
        if self.par[x] ==x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self,x,y):#x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)
#クラスカル法
kei = Unionfindtree(N)
graph.sort()
dist =0
for d,i,j in graph:
    if not kei.connect(i,j):
        kei.union(i,j)
        dist +=d
print(dist)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from heapq import heappush,heappop
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[]
for k in range(N-1):#距離、点
    graph.append([abs(A[k][0]-A[k-1][0]),A[k][2],A[k-1][2]])
    graph.append([abs(A[k][0]-A[k+1][0]),A[k][2],A[k+1][2]])
graph.append([abs(A[N-1][0]-A[N-2][0]),A[N-1][2],A[N-2][2]])
for k in range(N-1):
    graph.append([abs(B[k][1]-B[k-1][1]),B[k][2],B[k-1][2]])
    graph.append([abs(B[k][1]-B[k+1][1]),B[k][2],B[k+1][2]])
graph.append([abs(B[N-1][1]-B[N-2][1]),B[N-1][2],B[N-2][2]])

class Unionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)

    def find(self,x):#親を探す xの親を示す
        if self.par[x] ==x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self,x,y):#x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)
#クラスカル法
kei = Unionfindtree(N)
graph.sort()
dist =0
for d,i,j in graph:
    if not kei.connect(i,j):
        kei.union(i,j)
        dist +=d
print(dist)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from heapq import heappush,heappop
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[[] for i in range(N)]
for k in range(N-1):#距離、点
    graph[A[k][2]].append([abs(A[k][0]-A[k-1][0]),A[k-1][2]])
    graph[A[k][2]].append([abs(A[k][0]-A[k+1][0]),A[k+1][2]])
graph[A[N-1][2]].append([abs(A[N-1][0]-A[N-2][0]),A[N-2][2]])
for k in range(N-1):
    graph[B[k][2]].append([abs(B[k][1]-B[k-1][1]),B[k-1][2]])
    graph[B[k][2]].append([abs(B[k][1]-B[k+1][1]),B[k+1][2]])
graph[B[N-1][2]].append([abs(B[N-1][1]-B[N-2][1]),B[N-2][2]])
#プリム法
kei = []
visit=[False]*N
heappush(kei,[0,0])#距離,点
dist = 0
while kei:
    d,i = heappop(kei)
    if visit[i]==True:
        continue
    visit[i]=True
    dist += d
    for e,j in graph[i]:
        if not visit[j]:
            heappush(kei,[e,j])
print(dist)

Submission status: Time Limit Exceeded

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

X = sorted([(i, xy[0]) for i, xy in enumerate(p)], key=lambda x: x[1])
Y = sorted([(i, xy[1]) for i, xy in enumerate(p)], key=lambda x: x[1])
dX = [[X[i][0], X[i+1][0], X[i+1][1]-X[i][1]] for i in range(n-1)]
dY = [[Y[i][0], Y[i+1][0], Y[i+1][1]-Y[i][1]] for i in range(n-1)]
D = sorted(dX+dY, key=lambda x: x[2])

def root(x):
    if parent[x] == x:
        return x
    else:
        return root(parent[x])

def connected(x, y):
    return root(x) == root(y)

parent = [i for i in range(n+1)]
depth = [1 for i in range(n+1)]

ans = 0

while D:
    a, b, d = D.pop(0)
    ra, rb = map(root, [a,b])
    if ra != rb:
        if depth[ra] < depth[rb]:
            a, b = b, a
            ra, rb = rb, ra
        parent[rb] = ra
        depth[ra] = max(depth[ra], depth[rb]+1)
        ans += d
print(ans)