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:
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)]
ans = 0

while D:
    a, b, d = D.pop(0)
    if not connected(a, b):
        parent[root(b)] = root(a)
        ans += d
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = [list(map(int, input().split())) for i in range(n)]
# x,yだけのリストを作る。座標順にソートもします。
x = sorted([[p[i][0], i] for i in range(n)])
y = sorted([[p[i][1], i] for i in range(n)])
# x,yについて隣り合ったものだけをedgeとしてみればよい（これもソートします）
edge = sorted([[abs(x[i][0] - x[i-1][0]), x[i][1], x[i-1][1]] for i in range(n)] + [[abs(y[i][0] - y[i-1][0]), y[i][1], y[i-1][1]] for i in range(n)])
# Union-Find
group = [i for i in range(n)]
def findParent(i):
    if i == group[i]:
        return i
    else:
        group[i] = findParent(group[i])
        return group[i]
def merge(i, j):
    i = findParent(i)
    j = findParent(j)
    group[i] = j
# クラスカル法で最小全域木の重みを求めます
ret = 0
# TLE対策
useedge = 0
for e in edge:
    weight, a, b = e
    if findParent(a) != findParent(b):
        merge(a, b)
        ret += weight
        useedge += 1
        if useedge == n-1:
            break
print(ret)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = [list(map(int, input().split())) for i in range(n)]
# x,yだけのリストを作る。座標順にソートもします。
x = sorted([[p[i][0], i] for i in range(n)])
y = sorted([[p[i][1], i] for i in range(n)])
# x,yについて隣り合ったものだけをedgeとしてみればよい（これもソートします）
edge = [0]*(2*n)
for i in range(n):
    edge[2*i] = [abs(x[i][0] - x[i-1][0]), x[i][1], x[i-1][1]]
    edge[2*i+1] = [abs(y[i][0] - y[i-1][0]), y[i][1], y[i-1][1]]
edge.sort()
# Union-Find
group = [i for i in range(n)]
def findParent(i):
    if i == group[i]:
        return i
    else:
        group[i] = findParent(group[i])
        return group[i]
def merge(i, j):
    i = findParent(i)
    j = findParent(j)
    group[i] = j
# クラスカル法で最小全域木の重みを求めます
ret = 0
# TLE対策
useedge = 0
for e in edge:
    weight, a, b = e
    if findParent(a) != findParent(b):
        merge(a, b)
        ret += weight
        useedge += 1
        if useedge == n-1:
            break
print(ret)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = [list(map(int, input().split())) for i in range(n)]
# x,yだけのリストを作る。座標順にソートもします。
x = sorted([[p[i][0], i] for i in range(n)])
y = sorted([[p[i][1], i] for i in range(n)])
# x,yについて隣り合ったものだけをedgeとしてみればよい（これもソートします）
edge = [0]*(2*n)
for i in range(n):
    edge[2*i] = [abs(x[i][0] - x[i-1][0]), x[i][1], x[i-1][1]]
    edge[2*i+1] = [abs(y[i][0] - y[i-1][0]), y[i][1], y[i-1][1]]
edge.sort()
# Union-Find
group = [i for i in range(n)]
def findParent(i):
    if i == group[i]:
        return i
    else:
        group[i] = findParent(group[i])
        return group[i]
def merge(i, j):
    i = findParent(i)
    j = findParent(j)
    group[i] = j
# クラスカル法で最小全域木の重みを求めます
ret = 0
for e in edge:
    weight, a, b = e
    if findParent(a) != findParent(b):
        merge(a, b)
        ret += weight
print(ret)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = [list(map(int, input().split())) for i in range(n)]
# x,yだけのリストを作る。座標順にソートもします。
x = sorted([[p[i][0], i] for i in range(n)])
y = sorted([[p[i][1], i] for i in range(n)])
# x,yについて隣り合ったものだけをedgeとしてみればよい（これもソートします）
edge = []
for i in range(n):
    edge.append([abs(x[i][0] - x[i-1][0]), x[i][1], x[i-1][1]])
    edge.append([abs(y[i][0] - y[i-1][0]), y[i][1], y[i-1][1]])
edge.sort()
# Union-Find
group = [i for i in range(n)]
def findParent(i):
    if i == group[i]:
        return i
    else:
        group[i] = findParent(group[i])
        return group[i]
def merge(i, j):
    i = findParent(i)
    j = findParent(j)
    group[i] = j
# クラスカル法で最小全域木の重みを求めます
ret = 0
for e in edge:
    weight, a, b = e
    if findParent(a) != findParent(b):
        merge(a, b)
        ret += weight
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import array
import collections
import heapq


def read():
    return int(input())


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


def readmap():
    return map(int, input().split())


AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
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 main():
    N = read()
    vertex = []
    for i in range(N):
        x, y = readmap()
        vertex.append((i, x, y))

    max_v = N
    adjacency_list = collections.defaultdict(set)
    vertex.sort(key=lambda x: x[1])
    for i in range(N-1):
        adjacency_list[vertex[i][0]].add(AdjacentVertex(vertex[i+1][0], vertex[i+1][1] - vertex[i][1]))
        adjacency_list[vertex[i+1][0]].add(AdjacentVertex(vertex[i][0], vertex[i+1][1] - vertex[i][1]))
    vertex.sort(key=lambda x: x[2])
    for i in range(N-1):
        adjacency_list[vertex[i][0]].add(AdjacentVertex(vertex[i + 1][0], vertex[i + 1][2] - vertex[i][2]))
        adjacency_list[vertex[i + 1][0]].add(AdjacentVertex(vertex[i][0], vertex[i + 1][2] - vertex[i][2]))
    (_, key) = compute_mst_prim(max_v, adjacency_list)
    print(sum(key.values()))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import heapq

n = int(input())

V = {}
xs =[]
ys =[]

for i in range(n):
    x, y = tuple(map(int, input().split()))
    V[i] = (x, y, i)
    xs.append((x, i, y))
    ys.append((y, i, x))

xs.sort(key=lambda p:p[0])
ys.sort(key=lambda p:p[0])


def neighbores(p): #, xs, ys):
    found = []
    xi = bisect.bisect_left(xs, (p[0], p[2], p[1]))
    assert(xs[xi] == (p[0], p[2], p[1]))
    yi = bisect.bisect_left(ys, (p[1], p[2], p[0]))
    assert(ys[yi] == (p[1], p[2], p[0]))

    if xi - 1 >= 0:
        q = xs[xi - 1]
        found.append((q[0], q[2], q[1]))
    if xi + 1 < n:
        q = xs[xi + 1]
        found.append((q[0], q[2], q[1]))
    if yi - 1 >= 0:
        q = ys[yi-1]
        found.append((q[2], q[0], q[1]))
    if yi + 1 < n:
        q = ys[yi+1]
        found.append((q[2], q[0], q[1]))
    
    return found

def distance(p, q):
    return min(abs(p[0] - q[0]),  abs(p[1] - q[1]))

def foo():
    visited = set()
    visited.add(0)
    frontier = []
    for p in neighbores(V[0]):
        d = distance(V[0], p)
        heapq.heappush(frontier, (d, p))

    cost = 0
    while len(visited) < n:
        d, p = heapq.heappop(frontier)
        if p[2] in visited :
            continue
        cost += d
        visited.add(p[2])

        for q in neighbores(p):
            d = distance(p, q)
            heapq.heappush(frontier, (d, q))

    return cost

print(foo())

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ixy=[]
for i in range(N):
  x, y = map(int,input().split())
  ixy+=[[i,x,y]]
costs = [[] for i in range(N)]

ixy.sort(key=lambda x:x[1])
for j in range(N-1):
  costs[ixy[j][0]] += [[ixy[j+1][0],abs(ixy[j][1]-ixy[j+1][1])]]
  costs[ixy[j+1][0]] += [[ixy[j][0],abs(ixy[j][1]-ixy[j+1][1])]]
ixy.sort(key=lambda y:y[2])
for j in range(N-1):
  costs[ixy[j][0]] += [[ixy[j+1][0],abs(ixy[j][2]-ixy[j+1][2])]]
  costs[ixy[j+1][0]] += [[ixy[j][0],abs(ixy[j][2]-ixy[j+1][2])]]

import heapq
pq = []
heapq.heappush(pq,[0,0])

visited = [0]*N
ans = 0
while pq:
  cost, v = heapq.heappop(pq)

  if visited[v]: continue
  
  ans += cost
  visited[v]=1
  
  for u,c in costs[v]:
    if not visited[u]:
      heapq.heappush(pq, [c,u])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
http://abc065.contest.atcoder.jp/tasks/arc076_b

"""
import sys
from sys import stdin
input = stdin.readline
from collections import namedtuple


class DisjointSet(object):
    def __init__(self, size):
        self.rank = []
        self.p = []
        for i in range(size):
            self.makeSet(i)

    def makeSet(self, x):
        self.p.insert(x, x)
        self.rank.insert(x, 0)

    def same(self, x, y):
        return self.findSet(x) == self.findSet(y)

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]


def kruskal(V, E, es):
    es.sort(key=lambda x: x.c)
    uf = DisjointSet(V)
    res = 0

    for i in range(E):
        e = es[i]
        if not uf.same(e.u, e.v):
            uf.unite(e.u, e.v)
            res += e.c
    return res


edge = namedtuple('edge', ['u', 'v', 'c'])
def main(args):
    N = int(input())
    cities = []
    for i in range(1, N+1):
        x, y = map(int, input().split())
        cities.append([x, y, i])

    es = []
    cities.sort(key=lambda x: x[0])
    prev_x, _, prev_i = cities[0]
    for x, y, i in cities[1:]:
        es.append(edge(prev_i, i, x - prev_x))
        es.append(edge(i, prev_i, x - prev_x))
        prev_x = x
        prev_i = i

    cities.sort(key=lambda x: x[1])
    _, prev_y, prev_i = cities[0]
    for x, y, i in cities[1:]:
        es.append(edge(prev_i, i, y - prev_y))
        es.append(edge(i, prev_i, y - prev_y))
        prev_y = y
        prev_i = i

    result = kruskal(N+1, len(es), es)
    print(result)



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

import sys

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

useful_road = []

l = sorted(range(N), key=lambda j: x[j])
for i in range(len(l) - 1):
    cost = min(abs(x[l[i]] - x[l[i + 1]]), abs(y[l[i]] - y[l[i + 1]]))
    useful_road.append((cost, l[i], l[i + 1]))

l = sorted(range(N), key=lambda j: y[j])
for i in range(len(l) - 1):
    cost = min(abs(x[l[i]] - x[l[i + 1]]), abs(y[l[i]] - y[l[i + 1]]))
    useful_road.append((cost, l[i], l[i + 1]))


cost = 0
towngroup = np.array(list(range(N)))
for c, i, j in sorted(useful_road):
    if towngroup[i] == towngroup[j]:
        continue
    cost += c

    towngroup[towngroup == towngroup[j]] = towngroup[i]

    if len(set(towngroup)) == 1:
        print(cost)
        sys.exit()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

import sys

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

towngroup = np.array(list(range(N)))

howmuch = np.array([[10**9+1]*N for i in range(N)])

for i in range(N):
    for j in range(i, N):
        howmuch[i][j] = min(abs(x[i] - x[j]), abs(y[i] - y[j]))

cheapbridge = np.argsort(howmuch.flatten())

cost = 0

for i in cheapbridge[:]:
    a = i // N
    b = i % N
    if towngroup[a] == towngroup[b]:
        continue

    cost += min(abs(x[a] - x[b]), abs(y[a] - y[b]))

    towngroup[towngroup == towngroup[b]] = towngroup[a]

    if len(set(towngroup)) == 1:
        print(cost)
        sys.exit()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xyi = [list(map(int, input().split())) + [x] for x in range(n)]

a = [None for x in range(n)]

class Node:
    def __init__(self, c, f):
        self.c = c
        self.f = f

    def __lt__(self, a):
        return self.c < a.c

    def __str__(self):
        return "{} : {} ->".format(self.c, self.f)

xs = []
ys = []
for x, y, i in xyi:
    xs.append((x, i))
    ys.append((y, i))

xs.sort(key=lambda x: x[0])
ys.sort(key=lambda x: x[0])

ads = [[] for x in range(n)]
for i, t in enumerate(xs[1:]):
    f = xs[i]
    ads[f[1]].append((abs(f[0] - t[0]), t[1]))
    ads[t[1]].append((abs(f[0] - t[0]), f[1]))

for i, t in enumerate(ys[1:]):
    f = ys[i]
    ads[f[1]].append((abs(f[0] - t[0]), t[1]))
    ads[t[1]].append((abs(f[0] - t[0]), f[1]))

pque = []
visited = [Node(float("inf"), None) for x in range(n)]

import heapq
target = 0
visited[0] = Node(0, target)

while True:
    for edge in ads[target]:
        heapq.heappush(pque, Node(*edge))

    while pque:
        n = heapq.heappop(pque)
        if visited[n.f].c == float("inf"):
            break
    else:
        print(sum(map(lambda x: x.c, visited)))
        __import__("sys").exit()
    target = n.f
    visited[target] = n

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
P=[list(map(int,input().split())) for _ in range(N)]
cost=0
PL=[False]*N
count=0
a={}
for i in range(N-1):
    for j in range(i+1,N):
        x=abs(P[i][0]-P[j][0])
        y=abs(P[i][1]-P[j][1])
        r=min(x,y)
        try:
            l=a[r]
            l.append([i,j])
            a[r]=l
        except:
            a[r]=[[i,j]]
c=0
while True:
    if(count>=N-1):
        print(cost)
        break
    try:
        l=a[c]
    except:
        c+=1
        continue
    try:
        t=l[0][0]
        for item in l:
            if(PL[item[0]]==False or PL[item[1]]==False):
                cost+=c
                PL[item[0]]=True
                PL[item[1]]=True
                count+=1
    except:
        if(PL[l[0]]==False or PL[l[1]]==False):
            cost+=c
            PL[l[0]]=True
            PL[l[1]]=True
            count+=1
    c+=1

Submission status: Time Limit Exceeded

Solution code:

def distance(P, p1, p2):
    return min(abs(P[p1][1]-P[p2][1]), abs(P[p1][2]-P[p2][2]))

N = int(input())
P = [[j]+[int(i) for i in input().split(' ')] for j in range(N)]
sortX = sorted(P,key=lambda x:x[1])
sortY = sorted(P,key=lambda x:x[2])
EX = [[sortX[i][0], sortX[i+1][0], distance(P,sortX[i][0],sortX[i+1][0])] for i in range(N-1)]
EY = [[sortY[i][0], sortY[i+1][0], distance(P,sortY[i][0],sortY[i+1][0])] for i in range(N-1)]
E = EX + EY
E = sorted(E, key=lambda x:x[2])
CI = [i for i in range(N)]
disSum = 0
for e in E[:]:
    s,l = min(e[0],e[1]),max(e[0],e[1])
    if CI[s] != CI[l]:
        CI = list(map(lambda x:CI[s] if x == CI[l] else x, CI))
        disSum += e[2]
print(disSum)

Submission status: Time Limit Exceeded

Solution code:
def distance(P, p1, p2):
    return min(abs(P[p1][1]-P[p2][1]), abs(P[p1][2]-P[p2][2]))

N = int(input())
P = [[j]+[int(i) for i in input().split(' ')] for j in range(N)]
sortX = sorted(P,key=lambda x:x[1])
sortY = sorted(P,key=lambda x:x[2])
EX = [sorted([sortX[i][0],sortX[i+1][0]]) for i in range(N-1)]
EY = [sorted([sortY[i][0],sortY[i+1][0]]) for i in range(N-1)]
E = EX + EY

C = [0]
NC = [i for i in range(1,N)]
sumDis = 0
while len(NC) > 0:
    minDis = 1000000000
    for c in C:
        relatedE = [e for e in E if c in e]
        for e in relatedE:
            target = e[0] if e[0] != c else e[1]
            if not target in NC:
                continue
            dis = distance(P, c, target) 
            if minDis > dis:
                minDis = dis
                minTarget = target 
                minEdge = e
    NC.remove(minTarget) 
    C.append(minTarget)
    while minEdge in E:
        E.remove(minEdge)
    sumDis += minDis
print(sumDis)

Submission status: Time Limit Exceeded

Solution code:
class obj:
    def __init__(self, N):
        self.fa = [i for i in range(N)]
    def find(self, x):
        if x == self.fa[x]:
            return x
        else:
            self.fa[x] = self.find(self.fa[x])
            return self.fa[x]

N = int(input())
node = [{"x":0, "y":0, "id":i} for i in range(N)]
edge = [{"u":0, "v":0, "d":0} for i in range(2*(N-1))]
ob = obj(N)
for i in range(N):
    node[i]["x"], node[i]["y"] = map(int, input().split())
    node[i]["id"] = i

xnode = sorted(node, key=lambda x:x["x"])
for i in range(N-1):
    edge[i]["u"] = xnode[i]["id"]
    edge[i]["v"] = xnode[i+1]["id"]
    edge[i]["d"] = xnode[i+1]["x"] - xnode[i]["x"]
ynode = sorted(node, key=lambda x:x["y"])
for i in range(N-1):
    edge[i+N-1]["u"] = ynode[i]["id"]
    edge[i+N-1]["v"] = ynode[i+1]["id"]
    edge[i+N-1]["d"] = ynode[i+1]["y"] - ynode[i]["y"]
dedge = sorted(edge, key=lambda x:x["d"])
ans = 0
for i in range(2*(N-1)):
    if ob.find(dedge[i]["u"]) != ob.find(dedge[i]["v"]):
        ans += dedge[i]["d"]
        ob.fa[ob.fa[dedge[i]["u"]]] = ob.fa[dedge[i]["v"]]
    if all([x==ob.fa[0] for x in ob.fa]):
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind1:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]

    def find(self, x):
        while self.table[x] >= 0: x = self.table[x]
        return 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 union_bad(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

uf=UnionFind1(100001)

n = input()
cities = [map(int,raw_input().split(" "))+[i] for i in range(n)]

cities_x = sorted(cities, key=lambda a:a[0])
cities_y = sorted(cities, key=lambda a:a[1])

road = [[cities_x[i+1][0]-cities_x[i][0],cities_x[i][2],cities_x[i+1][2]] for i in range(n-1)]
road +=[[cities_y[i+1][1]-cities_y[i][1],cities_y[i][2],cities_y[i+1][2]] for i in range(n-1)]

sum = 0
for (cost,i,j) in sorted(road):
    if(uf.find(i)!=uf.find(j)):
        uf.union(i,j)
        sum += cost

print sum

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
N = int(input())
P = np.array([np.array([int(i) for i in input().split(' ')]) for j in range(N)]) 
Distance = [] 
for i in range(N):
    Distance.append([])
    for j in range(N):
        Distance[i].append(min(abs(P[i][0]-P[j][0]), abs(P[i][1]-P[j][1])))
NC = [i for i in range(1, N)]
C = [0]
disSum = 0
while len(NC) > 0:
    minDis = 1000000000
    for c in C:
        for t in NC:
            dis = Distance[c][t]
            if dis < minDis:
                nearest = t
                minDis = dis
#                 print(c,nearest,minDis)
    C.append(nearest)
    NC.remove(nearest)
    disSum += minDis
#     print(C)
#     print(NC)
print(disSum)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

import sys

def minimum(C, visited):
    min_index = -1
    min_cost = 10**9
    for v in visited:
        for i in xrange(0, len(C)):
            if i not in visited:
                cost = min(abs(C[i][0] - C[v][0]), abs(C[i][1] - C[v][1]))
                if cost < min_cost:
                    min_index = i
                    min_cost = cost
    return min_index, min_cost

def main(argv):
    N = sys.stdin.readline()
    while N:
        C = []
        for c in map(lambda i: raw_input().split(" ", 2), xrange(0, int(N))):
            C.append((int(c[0]), int(c[1])))

        total_cost = 0
        index = 0
        visited = set([index])
        while len(visited) < int(N):
            index, cost = minimum(C, visited)
            visited.add(index)
            total_cost += cost
        print total_cost

        N = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

Submission status: Time Limit Exceeded

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

cities = []
N = int(input())
for i in range(N):
    cities.append([int(x) for x in input().split()])


class DisjointSet:
    def __init__ (self, size):
        self.parent = [0] * size
        self.rank =   [0] * size
        for i in range(size):
            self.parent[i] = i

    def union(self, x, y):
        self.link( self.find_set(x), self.find_set(y) )
            
    def link (self, x, y):
        if self.rank[x] > self.rank[y]:
            self.parent[y] = self.parent[x]
        else:
            self.parent[x] = self.parent[y]
            if (self.rank[x] == self.rank[y]):
                self.rank[x] += self.rank[y] + 1

    def find_set (self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find_set(self.parent[x])
        return self.parent[x]

class Edge:
    def __init__(self, src, dst, weight):
        self.src   = src
        self.dst   = dst
        self.weight = weight

def weight(a, b):
    return min(abs(a[0] - b[0]), abs(a[1] - b[1]))

edges = [Edge(i, j, weight(cities[i], cities[j])) for i, j in itertools.combinations(range(N), 2)]

set = DisjointSet(N) # the number of vertices
mst = []

edges.sort(key = lambda x: x.weight)
for x in edges:
    u = x.src
    v = x.dst
    if set.find_set(u) != set.find_set(v):
        mst.append(x)
        set.union(u, v)

print (sum(map(lambda x: x.weight, mst)))

Submission status: Time Limit Exceeded

Solution code:
INF = 10**12

class Point:
    def __init__(s, x, y):
        s.x = x
        s.y = y

def min_dist(u, v):
    return min(abs(u.x - v.x), abs(u.y - v.y))

def MST(ps):

    m =  [[min_dist(ps[i], ps[j]) for i in range(len(ps))] for j in range(len(ps))]
    X = set([0])
    Y = set(range(len(ps))[1:])
    cost = 0
    edges = []
    while len(Y) != 0:
        mcost = INF
        edge = None
        for ex in X:
            for ey in Y:
                if mcost > m[ex][ey]:
                    mcost = m[ex][ey]
                    edge = [ex, ey]
        X.add(edge[1])
        Y.remove(edge[1])

        cost += mcost
        edges.append(edge)
    return cost, edges

N = int(input())
points = [list(map(int, input().split())) for i in range(N)]
ps = [Point(*p) for p in points]
cost, edges = MST(ps)
print(cost)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__ import division, print_function
import sys


def main():
    n = int(sys.stdin.readline().strip())
    xy = []
    for _ in range(n):
        xy.append(map(int, sys.stdin.readline().strip().split(" ")))

    costs = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            ax, ay = xy[i]
            bx, by = xy[j]
            costs[i][j] = min(abs(ax - bx), abs(ay - by))

    a = 10 ** 9 + 1
    min_costs = [a for _ in range(n)]
    min_costs[0] = 0
    used = [False for _ in range(n)]
    result = 0
    while True:
        v = -1
        for u in xrange(n):
            if not used[u] and (v == -1 or min_costs[u] < min_costs[v]):
                v = u
        if v == -1:
            break
        used[v] = True
        result += min_costs[v]
        for u in xrange(n):
            min_costs[u] = min(min_costs[u], costs[v][u])
    print(result)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
N = int(input())
towns = [tuple(map(int, input().split())) for _ in range(N)]
memo = {}
def dist(x, y):
    if (x,y) not in memo:
        memo[(x,y)] = min(abs(x[0] - y[0]), abs(x[1] - y[1]))
    return memo[(x,y)]
l1 = [towns[0]]
l2 = towns[1:]
totalcost = 0
while len(l2) > 0:
    bestscore = None
    for t2 in l2:
        for t1 in l1:
            cost = dist(t1,t2)
            if bestscore is None or cost < bestscore:
                bestscore = cost
                candidate = t2
    l2.remove(candidate)
    l1.append(candidate)
    totalcost += bestscore
print(totalcost)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
import sys
 
def abs(n):
  return n if n > 0 else -n
 
def cost(n,m):
  x = abs(n[0] - m[0])
  y = abs(n[1] - m[1])
  return x if x < y else y
 
vertex = [i for i in sys.stdin]
vertex.pop(0)
for i in range(len(vertex)):
  vertex[i] = [int(i) for i in vertex[i].split()]
yet_built = [i for i in range(len(vertex))]
built = [yet_built.pop()]
builtadd = built.append
all_cost = 0
while True:
  if len(yet_built) == 0:
    break
  min_cost = float("inf")
  min_city = 0
  for i in built:
    for j in yet_built:
      if min_cost > cost(vertex[i],vertex[j]):
        min_cost = cost(vertex[i],vertex[j])
        min_city = j
  all_cost += min_cost
  builtadd(min_city)
  yet_built.remove(min_city)

print(all_cost)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__ import division, print_function
import sys


def main():
    n = int(sys.stdin.readline().strip())
    xy = []
    for _ in range(n):
        xy.append(map(int, sys.stdin.readline().strip().split(" ")))

    costs = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            ax, ay = xy[i]
            bx, by = xy[j]
            costs[i][j] = min(abs(ax - bx), abs(ay - by))

    a = 10 ** 9 + 1
    min_costs = [a for _ in range(n)]
    min_costs[0] = 0
    used = [False for _ in range(n)]
    result = 0
    while True:
        v = -1
        for u in range(n):
            if not used[u] and (v == -1 or min_costs[u] < min_costs[v]):
                v = u
        if v == -1:
            break
        used[v] = True
        result += min_costs[v]
        for u in range(n):
            min_costs[u] = min(min_costs[u], costs[v][u])
    print(result)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
N = int(input())
towns = [tuple(map(int, input().split())) for _ in range(N)]
def dist(x, y):
    return min(abs(x[0] - y[0]), abs(x[1] - y[1]))
l1 = [towns[0]]
l2 = towns[1:]
totalcost = 0
while len(l2) > 0:
    bestscore = None
    for t2 in l2:
        for t1 in l1:
            cost = dist(t1,t2)
            if bestscore is None or cost < bestscore:
                bestscore = cost
                candidate = t2
    l2.remove(candidate)
    l1.append(candidate)
    totalcost += bestscore
print(totalcost)

Submission status: Time Limit Exceeded

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

def abs(n):
  return n if n > 0 else -n

def cost(n,m):
  x = abs(n[0] - m[0])
  y = abs(n[1] - m[1])
  return x if x < y else y

vertex = [i for i in sys.stdin]
vertex.pop(0)
for i in range(len(vertex)):
  vertex[i] = [int(i) for i in vertex[i].split()]
built = [0]
yet_built = [i for i in range(len(vertex))]
yet_built.pop(0)
all_cost = 0
while True:
  if len(yet_built) == 0:
    break
  min_cost = float("inf")
  min_city = 0
  for i in built:
    for j in yet_built:
      if min_cost > cost(vertex[i],vertex[j]):
        min_cost = cost(vertex[i],vertex[j])
        min_city = j
  all_cost += min_cost
  built.append(min_city)
  yet_built.remove(min_city)

print(all_cost)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
ddict = defaultdict
def main():
  N = int(input())
  X = ddict(list)
  Y = ddict(list)
  Pt = []
  for i in range(N):
    x,y = map(int,input().split())
    X[x].append(i)
    Y[y].append(i)
    Pt.append((x,y))
  l = [i for i in range(1,N)]
  sx = {Pt[0][0]}
  sy = {Pt[0][1]}
  cout = 0
  while l:
    m1 = min(abs(Pt[l[0]][0]-x) for x in sx)
    m2 = min(abs(Pt[l[0]][1]-y) for y in sy)
    m = min(m1,m2)
    cand = 0
    for i in range(1,len(l)):
      m1 = min(abs(Pt[l[i]][0]-x) for x in sx)
      m2 = min(abs(Pt[l[i]][1]-y) for y in sy)
      mi = min(m1,m2)
      if mi < m:
        m = mi
        cand = i
      if m == 0:
        break
    li = l.pop(cand)
    sx.add(Pt[li][0])
    sy.add(Pt[li][1])
    cout += m
  print(cout)

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__ import division, print_function
import sys


def main():
    n = int(sys.stdin.readline().strip())
    xy = []
    for _ in range(n):
        xy.append(map(int, sys.stdin.readline().strip().split(" ")))

    table = [-1 for _ in xrange(n)]

    def find(x):
        if table[x] < 0:
            return x
        else:
            table[x] = find(table[x])
            return table[x]

    def union(x, y):
        s1 = find(x)
        s2 = find(y)
        if s1 != s2:
            if table[s1] <= table[s2]:
                table[s1] += table[s2]
                table[s2] = s1
            else:
                table[s2] += table[s1]
                table[s1] = s2
            return True
        return False

    costs = []
    for i in range(n):
        for j in range(i + 1, n):
            ax, ay = xy[i]
            bx, by = xy[j]
            costs.append((i, j, min(abs(ax - bx), abs(ay - by))))
    costs.sort(key=lambda (x, y, c): c)

    visited = set()
    result = 0
    while len(costs) > 0:
        x, y, c = costs.pop(0)
        if x in visited and y in visited:
            pass
        if union(x, y):
            visited.add(x)
            visited.add(y)
            result += c
        # print(x, y, c)
    print(result)


if __name__ == '__main__':
    main()