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: Wrong Answer

Solution code:
import sys
fin = sys.stdin.readline
from heapq import heappop, heappush


# assuming that the vertices are 0, 1, ..., N - 1
# if V^2 >> E, use a hashmap representation of w
# time complexity: O(ElgE)
# space complexity: O(E)
def prim(adj, w):
    num_vertices = len(adj)
    # initialize
    min_cost = [float('inf')] * num_vertices
    min_cost[0] = 0
    used = [False] * num_vertices
    priority_queue = [(0, 0)]
    total_cost = 0

    while priority_queue:
        cost, vertex = heappop(priority_queue)
        if cost > min_cost[vertex] or used[vertex]:
            continue
        used[vertex] = True
        total_cost += cost

        for neighbor in adj[vertex]:
            cost_v_to_n = w[(vertex, neighbor)]
            if min_cost[neighbor] > cost_v_to_n:
                min_cost[neighbor] = cost_v_to_n
                heappush(priority_queue, (cost_v_to_n, neighbor))

    return total_cost


N = int(fin())
coords = [[int(elem) for elem in fin().split()] + [i] for i in range(N)]

adj = [set() for _ in range(N)]
w = {}

# sort coords in increasing order of x
coords.sort(key=lambda x: x[0])
for i, (x, _, vertex) in enumerate(coords[:-1]):
    next_x, _, next_idx = coords[i + 1]
    adj[vertex].add(next_idx)
    adj[next_idx].add(vertex)
    weight = next_x - x
    w[(vertex, next_idx)] = weight
    w[(next_idx, vertex)] = weight

# sort coods in increasing order of y
coords.sort(key=lambda x: x[1])
for i, (_, y, vertex) in enumerate(coords[:-1]):
    _, next_y, next_idx = coords[i + 1]
    adj[vertex].add(next_idx)
    adj[next_idx].add(vertex)
    weight = next_y - y
    w[(vertex, next_idx)] = weight
    w[(next_idx, vertex)] = weight


print(prim(adj, w))

Submission status: Wrong Answer

Solution code:
N = int(input())
z = [tuple(map(int,input().split())) for i in range(N)]
z.sort()
y = [(z[i][1],i) for i in range(N)]
y.sort()
cost = [[] for i in range(N)]
for i in range(N):
    j = y[i][1]
    if i != 0:
        cost[i].append((i-1,z[i][0]-z[i-1][0]))
        cost[i].append((i-1,abs(z[i][1]-z[i-1][1])))
        j_ = y[i-1][1]
        cost[j].append((j_,y[i][0]-y[i-1][0]))
        cost[j].append((j_,abs(z[j][0]-z[j_][0])))
    if i != N-1:
        cost[i].append((i+1,z[i+1][0]-z[i][0]))
        cost[i].append((i+1,abs(z[i+1][1]-z[i][1])))
        j_ = y[i+1][1]
        cost[j].append((j_,y[i+1][0]-y[i][0]))
        cost[j].append((j_,abs(z[j_][1]-z[j][1])))

import heapq

def prim(cost):
    V = len(cost)
    res = 0
    mincost = [float('inf')]*V
    used = [False]*V
    hq = []
    mincost[0] = 0
    heapq.heappush(hq,(0,0))
    done = 0
    while hq:
        weight,u = heapq.heappop(hq)
        if not used[u]:
            used[u] = True
            done += 1
            res += weight
            mincost[u] = weight
            for v, v_cost in cost[u]:
                if not used[v]:
                    heapq.heappush(hq,(v_cost,v))
            if done == V:
                break
    return res

Submission status: Wrong Answer

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))

    key = {}
    pred = {}
    in_q = set(V)
    for v in V:
        key[v] = sys.maxsize
        pred[v] = -1

    key[V[0]] = 0
    q = []
    for v in V:
        heapq.heappush(q, (key[v], v))

    while q:
        _, u = heapq.heappop(q)
        for v in g[u].keys():
            w = g[u][v]
            if w < key[v]:
                pred[v] = u
                key[v] = w
                heapq.heappush(q, (key[v], v))
    return pred


@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
    # pprint(g)
    d = Prim(g)
    # print(d)
    ans = 0
    for v, u in d.items():
        if u != -1:
            # print(v, u, g[v][u])
            ans += g[v][u]

    return ans


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import floyd_warshall
N = int(input())
x, y = np.zeros(N, dtype=int), np.zeros(N, dtype=np.int)
for i in range(N):
    x[i], y[i] = map(int, input().split())

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

G = floyd_warshall(D, directed=False)

d = 0
G += np.diag([2*10**9] * N)
for i in range(N):
    for j in range(i + 1, N):
        if np.min(G[i] + G[j]) != G[i, j]:
            d += G[i, j]
print(int(d))

Submission status: Wrong Answer

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):#距離、点
    graph[A[k][2]].append([min(abs(A[k][0]-A[k-1][0]),abs( A[k][1]-A[k-1][1])),A[k-1][2]])
for k in range(N):
    graph[B[k][2]].append([min(abs(B[k][0]-B[k-1][0]),abs( B[k][1]-B[k-1][1])),B[k-1][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: Wrong Answer

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]])
for k in range(N-1):
    graph.append([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: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
cities_x = [list(map(int,input().split())) for _ in range(n)]
for i in range(n):
    cities_x[i].append(i)
cities_y = cities_x[:]
cities_x.sort()
cities_y.sort(key=lambda x:x[1])
graph_1 = [[0] * n] * n
graph_2 = [[0] * n] * n
memory = [[0] * 2] * n
ans = 0

for i in range(n-1):
    if i == n-1:
        p = abs(cities_x[i][0] - cities_x[0][0])
        graph_1[cities_x[i][2]][cities_x[0][2]] = 1
        graph_1[cities_x[0][2]][cities_x[i][2]] = 1
        memory[cities_x[i][2]][0] = p
        ans += p
    else:
        p = abs(cities_x[i][0] - cities_x[i+1][0])
        graph_1[cities_x[i][2]][cities_x[i+1][2]] = 1
        graph_1[cities_x[i+1][2]][cities_x[i][2]] = 1
        memory[cities_x[i][2]][0] = p
        ans += p

for i in range(n):
    if i == n-1:
        p = abs(cities_y[i][0] - cities_y[0][0])
        graph_1[cities_y[i][2]][cities_y[0][2]] = 1
        graph_1[cities_y[0][2]][cities_y[i][2]] = 1
        memory[cities_y[i][2]][1] = p
        ans += p
    else:
        p = abs(cities_y[i][0] - cities_y[i+1][0])
        graph_1[cities_y[i][2]][cities_y[i+1][2]] = 1
        graph_1[cities_y[i+1][2]][cities_y[i][2]] = 1
        memory[cities_y[i][2]][1] = p
        ans += p
for i in range(n):
    ans -= max(memory[i])

print(ans // 2)

Submission status: Wrong Answer

Solution code:
N = int(input())
ixy=[]
for i in range(N):
  x, y = map(int,input().split())
  ixy+=[[i,x,y]]
costs = [[float("inf") for i in range(N)] for j 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])

visited = [1] + [0]*(N-1)
mincost = [0] + [float("inf")]*(N-1)
for i in range(N):
  mincost[i] = min(mincost[i],costs[0][i])

ans=0 
while(True):
  v = -1 
  for u in range(N):
    if not visited[u] and (v==-1 or mincost[u] < mincost[v]): v=u
  
  if v==-1 :break
  visited[v] = 1
  ans += mincost[v]
  
  for u in range(N):
    mincost[u] = min(mincost[u], costs[u][v])
    
print(ans)

Submission status: Wrong Answer

Solution code:
def list_to_dict(val_list):
  return list(zip(range(0,len(val_list)), val_list))


class Edge():
    def __init__(self,_start,_end,_cost):
        self.start = _start
        self.end = _end
        self.cost = _cost
    def __str__(self):
    	return ",".join([str(self.start),str(self.end),str(self.cost)])


n = int(input())
#頂点集合V
V = [[int(_) for _ in input().split()] for i in range(n)]
dicV = list_to_dict(V)
# プリム法

# 集合Eの生成
E_x = sorted(dicV, key=lambda x:x[1][0])
E_y = sorted(dicV, key=lambda x:x[1][1])

edges = []
for i in range(len(E_x)-1):
    edges.append(Edge(E_x[i][0],E_x[i+1][0],E_x[i+1][1][0]-E_x[i][1][0]))
    edges.append(Edge(E_y[i][0],E_y[i+1][0],E_y[i+1][1][1]-E_y[i][1][1]))

edges.sort(key=lambda x:x.cost)

vertexes = [i for i in range(n)]

V = set()
E = []
sums = 0

while(len(V) < n):
	minedge = edges[0]
	for i in range(1,len(edges)):
		edge = edges[i]
		if edge.start in V and edge.end in V:
			edges.pop(i)
			break
		if edge.cost < minedge.cost:
			minedge = edge
	V.add(minedge.start)
	V.add(minedge.end)
	sums += minedge.cost
	edges.remove(minedge)

print(sums)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from collections import deque

N = int(input())

xs, ys = [], []
for _ in range(N):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
    
xis = sorted(list(enumerate(xs)), key = itemgetter(1))
yis = sorted(list(enumerate(ys)), key = itemgetter(1))

xds, yds = [], []
for i in range(N-1):
    xds.append((xis[i+1][1] - xis[i][1], (xis[i][0], xis[i+1][0])))
    yds.append((yis[i+1][1] - yis[i][1], (yis[i][0], yis[i+1][0])))

xdq, ydq = deque(sorted(xds)), deque(sorted(yds))

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

def union(x,y):
    rx, ry = find(x), find(y)
    par[ry] = rx

ans = 0
while xdq or ydq:
    if xdq and (not ydq or xdq[0] < ydq[0]):
        d, (i,j) = xdq.popleft()
    else:
        d, (i,j) = ydq.popleft()
    ans += d
    union(i,j)

print(ans)

Submission status: Wrong Answer

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 range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a
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]=list(map(int,input().split()))
    x[i][1],y[i][1]=i,i
x=sorted(x,key=lambda l:l[0])
y=sorted(y,key=lambda l:l[0])
def cal(d,xl):
    M=len(xl)
    for i in range(M):
        if(i==0):
            r=abs(xl[i+1][0]-xl[i][0])
            d[r]=[[xl[i+1][1],xl[i][1]]]
        elif(i==N-1):
            None
        else:
            r1=abs(xl[i+1][0]-xl[i][0])
            try:
                l=d[r1]
                l.append([xl[i+1][1],xl[i][1]])
                d[r1]=l
            except:
                d[r1]=[[xl[i+1][1],xl[i][1]]]
    return d
p=UnionFind(N)
a=cal(cal({},x),y)
c=1
cost=0
flag=False
while True:
    if(flag==False and p.subsetall()[0][1]==N):
        print(cost)
        break
    try:
        l=a[c]
        for item in l:
            if(p.union(item[0],item[1])):
                cost+=c
                if flag:
                    flag=False
                continue
            else:
                continue
        c+=1
    except:
        c+=1
        continue

Submission status: Wrong Answer

Solution code:
N = int(input())

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

def cost(pt1, pt2):
    return min(abs(pt1[0] - pt2[0]), abs(pt1[1] - pt2[1]))

nearest = [0] * N
weight = [cost(p[0], p[i]) for i in range(N)]
weight[0] = -1

def minPos(ll):
    pos = -1
    cur = -1
    for i in range(len(ll)):
        if (ll[i] > 0) and ((cur < 0) or (cur > ll[i])):
            pos = i
            cur = ll[i]
    return pos

tmp = 0
while True:
    mm = minPos(weight)

    # print('itr: ')
    # print('cost: %d' % (tmp,))
    # print(weight)
    # print(nearest)
    # print('Near Node: %d' % (mm, ))
    # print("---")

    if mm < 0:
        break
    else:
        tmp += weight[mm]
        weight[mm] = -1
        for i in range(N):
            tmp2 = cost(p[mm], p[i])
            if tmp2 < weight[i]:
                nearest[i] = i
                weight[i] = tmp2

print(tmp)

Submission status: Wrong Answer

Solution code:
import math

max_val = 1000000000

def solve():
    n = int(input())
    l = []
    mat = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        l.append(list(map(int,input().split())))
        for j in range(i+1):
            mat[i][j] = min(abs(l[i][0]-l[j][0]), abs(l[i][1]-l[j][1]))
            mat[j][i] = mat[i][j]
            if(i == j):
                mat[i][j] = max_val
                mat[j][i] = mat[i][j]

    ans = 0
    hist = [0]
    l = mat[hist[-1]]

    
#    print(hist, ans)
#    print(mat)
    
    while(len(hist) < n):

        index = l.index(min(l))
        index_x = hist[int(index / n)]
        index_y = index % n

        ans += mat[index_x][index_y]
        
#        print(l, index, index_x, index_y)
#        print(hist, ans)
#        print(mat)
        
        l[index] = max_val
        hist.append(index_y)
        for h in hist:
            mat[h][index_y] = max_val
            mat[index_y][h] = max_val
#        mat[index_x][index_y] = max_val
#        mat[index_y][index_x] = max_val

        l.extend(mat[hist[-1]])


    return ans



if(__name__ == "__main__"):
    print(solve())

Submission status: Wrong Answer

Solution code:
import math

max_val = 1000000000

def solve():
    n = int(input())
    l = []
    mat = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        l.append(list(map(int,input().split())))
        for j in range(i+1):
            mat[i][j] = min(abs(l[i][0]-l[j][0]), abs(l[i][1]-l[j][1]))
            mat[j][i] = mat[i][j]
            if(i == j):
                mat[i][j] = max_val
                mat[j][i] = mat[i][j]

    ans = 0
    hist = [0]
    
    return func(ans, hist, n, mat)

def func(ans, hist, n, mat):
    if(len(hist) == n):
        return ans

    l = []
    for i in hist:
        l.extend(mat[i])
    
    index = l.index(min(l))
    index_x = hist[int(index / n)]
    index_y = index % n
    
    hist.append(index_y)
    hist.sort()
    ans += mat[index_x][index_y]
    mat[index_x][index_y] = max_val
    mat[index_y][index_x] = max_val

    #print(hist, ans)
    #print(l, index, index_x, index_y)
    #for s in mat:
    #    print(s)

    return func(ans, hist, n, mat)


if(__name__ == "__main__"):
    print(solve())

Submission status: Wrong Answer

Solution code:

def distance(P, p1, p2):
    return min(abs(P[p1][1]-P[p2][1]), abs(P[p1][2]-P[p2][2]))
def root(CI, p):
    if CI[p] == p:
        return p
    else:
        CI[p] = root(CI, CI[p])
        return CI[p] 

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]
    if root(CI, s) != root(CI, l):
        CI[root(CI, l)] = root(CI, s)
        disSum += e[2]
    print(CI)
print(disSum)

Submission status: Wrong Answer

Solution code:
#! cat input | python3 main.py

def cost(a, b, c, d):
    return min(abs(a - c), abs(b - d))

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, i, j):
        self.i = i
        self.j = j
        self.c = c

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

field = [[Node(float("inf"), 0, 0)] for x in range(n)]
import heapq

for x, y, i in xyi:
    for j, f in enumerate(field[:i]):
        c = Node(cost(x, y, xyi[j][0], xyi[j][1]), i, j)
        heapq.heappush(field[j], c)
        heapq.heappush(field[i], c)
print("no")
#
# nodes = [False for x in range(n)]
# r = []
# for f in field:
#     while True:
#         try:
#             n = heapq.heappop(f)
#         except:
#             break
#         if not nodes[n.i]:
#             r.append(n.c)
#             nodes[n.i] = True
#             break
#
# print(sum(filter(lambda x: x!= float("inf"), r)))

Submission status: Wrong Answer

Solution code:
def cost(a, b, c, d):
    return min(abs(a - c), abs(b - d))

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, i, j):
        self.i = i
        self.j = j
        self.c = c

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

field = [[Node(float("inf"), 0, 0)] for x in range(n)]
import heapq

for x, y, i in xyi:
    for j, f in enumerate(field[:i]):
        c = Node(cost(x, y, xyi[j][0], xyi[j][1]), i, j)
        heapq.heappush(field[j], c)
        heapq.heappush(field[i], c)

nodes = [False for x in range(n)]
r = []
for f in field:
    while True:
        try:
            n = heapq.heappop(f)
        except:
            break
        if not nodes[n.i]:
            r.append(n.c)
            nodes[n.i] = True
            break

print(sum(filter(lambda x: x!= float("inf"), r)))

Submission status: Wrong Answer

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

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

best = [0]
for i in range(1,N):
    best.append(float('inf'))
    for j in range(i):
        d = dist(towns[i],towns[j])
        best[i] = min(best[i], d)
        best[j] = min(best[j], d)

print sum(best)

Submission status: Wrong Answer

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
    C.append(t)
    NC.remove(t)
#     print(minDis)
    disSum += minDis
#     print(C)
#     print(NC)
print(disSum)

Submission status: Wrong Answer

Solution code:
n = int(input())
cityx = []
cityy = []
for _ in range(n):
    x,y = input().split()
    cityx.append(int(x))
    cityy.append(int(y))

done = []
money = 0

x = cityx[-1]
y = cityy[-1]
for i in range(n-1):
    money += min([abs(cityx[i]-x),abs(cityy[i]-y)])

print(money)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N = int(input())
locations = []
for n in range(N):
  locations.append(list(map(int, input().split(' '))))
  
costs = [[0]*N for n in range(N)]
for n1 in range(N-1):
  for n2 in range(n1+1, N):
    costs[n1][n2] = costs[n2][n1] = min(abs(locations[n1][0]-locations[n2][0]), 
                                        abs(locations[n1][1]-locations[n2][1]))

def prim(start):
  global N
  total_cost = 0
  visited = [False for n in range(N)]
  visited[start] = True
  hq = []
  
  for n in range(N):
    if n == start: continue
    heapq.heappush(hq, [costs[start][n], n])
  
  while len(hq):
    current = heapq.heappop(hq)
    if not visited[current[1]]:
      visited[current[1]] = True
      total_cost += current[0]
      for n in range(N):
        if n == current or visited[n]: continue
        heapq.heappush(hq, [costs[current[1]][n], n])
      
  return total_cost

print(prim(0))

Submission status: Time Limit Exceeded

Solution code:
with open(0) as f:
    N, *xy = map(int, f.read().split())
from collections import namedtuple
v = namedtuple('v',['x','y'])
V = [v(x-1,y-1) for x,y in zip(xy[::2],xy[1::2])] #頂点
cost = lambda i,j:min(abs(V[i].x-V[j].x), abs(V[i].y-V[j].y))
from itertools import combinations 
Edge = sorted([(cost(i,j), i, j) for i,j in combinations(range(N),2)])
root = namedtuple('root',['num', 'rank']) #(num_of_root, rank_of_root)
Root = [root(i,0) for i in range(N)] 

def fr(i): #findRoot
    if i == Root[i].num:
        return Root[i]
    Root[i] = fr(Root[i].num)
    return Root[i]


def unionT(i, j): #unionTree
    p, q = fr(i), fr(j)
    if p.rank < q.rank:
        Root[p.num] = q
    elif p.rank > q.rank:
        Root[q.num] = p
    elif p.rank == q.rank:
        r, s = min(p, q), max(p, q)
        Root[r.num] = Root[s.num] = root(r.num, r.rank+1)
    

ans = 0
#最小全域木の大きさ算出(環状にならないように辺を小さい順に足してゆく)
for w, i, j in Edge:
    p, q = fr(i), fr(j)
    if p.num == q.num: #既に連結済み
        continue
    else:
        unionT(i,j)
        ans += w
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
from operator import itemgetter

N = int(input())
P = []
for i in range(N):
  x,y = map(int, input().split())
  P.append((x,y,i))
  
P.sort() 
D = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N-1):
  a,b,p = P[i]
  c,d,q = P[i+1]
  D[p][q] = min(abs(a-c), abs(b-d))
    
P.sort(key=itemgetter(1))
for i in range(N-1):
  a,b,p = P[i]
  c,d,q = P[i+1]
  D[p][q] = min(abs(a-c), abs(b-d))

mst = minimum_spanning_tree(D)
print(int(mst.sum()))

Submission status: Time Limit Exceeded

Solution code:
import heapq
n = int(raw_input())
points = [map(int, raw_input().split()) for _ in range(n)]
heap  =[]

for i in range(len(points)):
	for j in range(i + 1, len(points)):
		a,b = points[i], points[j]
		
		heapq.heappush(heap,(min(abs(a[0]-  b[0]), abs(a[1] - b[1])),i,j))

parent = range(n)
size = [1] * n
cumul = 0

def get(u, parent):
	if u != parent[u]: parent[u] = get(parent[u], parent)
	return parent[u]
while(heap):
	cost,i,j = heapq.heappop(heap)
	pi,pj = get(i,parent), get(j, parent)
	if pi != pj:
		cumul += cost
		parent[pi] = pj
		size[pj] += size[pi]
		if size[pj] == n:
			break
print cumul

Submission status: Time Limit Exceeded

Solution code:
import heapq
n = int(raw_input())
points = [map(int, raw_input().split()) for _ in range(n)]
heap  =[]

for i in range(len(points)):
	for j in range(i+1, len(points)):
		a,b = points[i], points[j]
		heapq.heappush(heap,(min(abs(a[0]-  b[0]), abs(a[1] - b[1])),i,j))

parent = {i:i for i in range(n)}
cumul = 0

def get(u, parent):
	if u != parent[u]: parent[u] = get(parent[u], parent)
	return parent[u]
while(heap):
	cost,i,j = heapq.heappop(heap)
	pi,pj = get(i,parent), get(j, parent)
	if pi != pj:
		cumul += cost
		parent[pi] = pj
print cumul

Submission status: Time Limit Exceeded

Solution code:
class UnionFind(object):
  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ in range(n)]
    self.size = [1 for _ in range(n)]
  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 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
      self.size[x] += self.size[y]
  def is_same(self, x, y):
    return self.find(x) == self.find(y)
  def get_size(self, x):
    x = self.find(x)
    return self.size[x]


from heapq import heapify, heappop, heappush

N = int(input())
X = []; Y = []
for i in range(N):
  x,y = map(int,input().split())
  X.append((x,i));Y.append((y,i))
X.sort();Y.sort()
dx = [];dy =[]
for i in range(N-1):
  tx = X[i+1][0]-X[i][0]
  dx.append((tx,(X[i+1][1],X[i][1])))
  ty = Y[i+1][0]-Y[i][0]
  dy.append((ty,(Y[i+1][1],Y[i][1])))
heapify(dx);heapify(dy)
#print(dx,dy)
visited = set([])
ans = 0
uf = UnionFind(N)
while uf.get_size(0) < N:
  if not dy or dx[0] <= dy[0]:
    cost, loc = heappop(dx)
  else:
    cost, loc = heappop(dy)
  if uf.is_same(loc[0],loc[1]): #すでに接続済みのところはスキップ
    continue
  ans += cost
  #print(cost)
  uf.union(loc[0],loc[1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()


def main():
    """
    道を全部張った後に最小全域木を求めれば良いー＞プリム
    """
    N = int(input())
    city = {}
    for i in range(N):
        x, y = map(int, input().split())
        city[i] = x * 10**10 + y
    unvisited = set([i for i in range(1, N)])
    ans = 0
    q = []
    # qに頂点0から延びる道を追加
    for i in range(1, N):
        x0, y0 = city[0] // 10**10, city[0] % 10**10
        x, y = city[i] // 10**10, city[i] % 10**10
        cost = min(abs(x - x0), abs(y - y0))
        heappush(q, (cost, i))
    while q:
        cost, v = heappop(q)
        if v not in unvisited: continue
        ans += cost
        unvisited.remove(v)
        if not unvisited: break
        for u in unvisited:
            xv, yv = city[v] // 10**10, city[v] % 10**10
            xu, yu = city[u] // 10**10, city[u] % 10**10
            cost = min(abs(xv - xu), abs(yv - yu))
            heappush(q, (cost, u))
    print(ans)





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from heapq import heappop, heappush

icase=0
if icase==0:
    n=int(input())
    xy=[[0]*2 for i in range(n)]
    for i in range(n):
        xy[i]=list(map(int,input().split()))
elif icase==1:    
    n=3
    xy=[[1, 5], [3, 9], [7, 8]]
elif icase==2:    
    n=6
    xy=[[8, 3], [4, 9], [12, 19], [18, 1], [13, 5], [7, 6]]

#xy = list(map(list, set(map(tuple, xy))))
xy.sort()
xy=xy[:n]

pair_lst = [i for i in range(n)]
que=[]
for i in range(n-1):
    for j in range(i+1,n):
        wi=min(abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1]))
        heappush(que,(wi,i,j))

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

length_sum = 0
while que:
    w, s, t = heappop(que)
    root_s = find(s)
    root_t = find(t)
    if root_s != root_t:
        pair_lst[root_s] = root_t
        length_sum += w

print(length_sum)