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:
import sys
import operator as ope
import numpy as np


class Town:
    def __init__(self, num, x, y):
        self.num = num
        self.x = x
        self.y = y


class Edge:
    def __init__(self, weight, u, v):
        self.weight = weight
        self.u = u
        self.v = v

    def __lt__(self, other):
        return self.weight <= other.weight


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [1] * 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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same_check(self, x, y):
        return self.find(x) == self.find(y)


def main():
    n = int(input())
    towns = []
    for i in range(n):
        x, y = [int(m) for m in input().split()]
        towns.append(Town(i, x, y))
    edges = []
    xsort = sorted(towns, key=ope.attrgetter("x"))
    ysort = sorted(towns, key=ope.attrgetter("y"))
    for i in range(n - 1):
        edges.append(Edge(abs(xsort[i].x - xsort[i + 1].x), xsort[i].num, xsort[i + 1].num))
        edges.append(Edge(abs(ysort[i].y - ysort[i + 1].y), ysort[i].num, ysort[i + 1].num))
    edges.sort()
    ans = 0
    uf = UnionFind(n)
    for e in edges:
        if uf.same_check(e.u, e.v):
            continue
        ans += e.weight
        uf.union(e.u, e.v)
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
import operator as ope
import numpy as np


class Town:
    def __init__(self, num, x, y):
        self.num = num
        self.x = x
        self.y = y


class Edge:
    def __init__(self, weight, u, v):
        self.weight = weight
        self.u = u
        self.v = v

    def __lt__(self, other):
        return self.weight <= other.weight


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [1] * 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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def same_check(self, x, y):
        return self.find(x) == self.find(y)


def main():
    n = int(input())
    towns = []
    for i in range(n):
        x, y = [int(m) for m in input().split()]
        towns.append(Town(i, x, y))
    edges = queue.PriorityQueue()
    xsort = sorted(towns, key=ope.attrgetter("x"))
    ysort = sorted(towns, key=ope.attrgetter("y"))
    for i in range(n - 1):
        edges.put(Edge(abs(xsort[i].x - xsort[i + 1].x), xsort[i].num, xsort[i + 1].num))
        edges.put(Edge(abs(ysort[i].y - ysort[i + 1].y), ysort[i].num, ysort[i + 1].num))
    ans = 0
    uf = UnionFind(n)
    while not edges.empty():
        e = edges.get()
        if uf.same_check(e.u, e.v):
            continue
        ans += e.weight
        uf.union(e.u, e.v)
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
Edge=[[] for i in range(n)]
XY=[]
append=XY.append
for i in range(n):
  x,y=map(int,input().split())
  append([i,x,y])
XY.sort(key=lambda x:x[1])
for i in range(1,n):
  n1,x1,y1=XY[i-1][0],XY[i-1][1],XY[i-1][2]
  n2,x2,y2=XY[i][0],XY[i][1],XY[i][2]
  Edge[n1].append([min(abs(x2-x1),abs(y2-y1)),n2])
  Edge[n2].append([min(abs(x2-x1),abs(y2-y1)),n1])
XY.sort(key=lambda x:x[2])
for i in range(1,n):
  n1,x1,y1=XY[i-1][0],XY[i-1][1],XY[i-1][2]
  n2,x2,y2=XY[i][0],XY[i][1],XY[i][2]
  Edge[n1].append([min(abs(x2-x1),abs(y2-y1)),n2])
  Edge[n2].append([min(abs(x2-x1),abs(y2-y1)),n1])
import heapq
def prim_heap():
  used=[True]*n
  Edgelist=[]
  for e in Edge[0]:
    heapq.heappush(Edgelist,e)
  used[0]=False
  res=0
  while len(Edgelist)!=0:
    minedge=heapq.heappop(Edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    used[v]=False
    for e in Edge[v]:
      if used[e[1]]:
        heapq.heappush(Edgelist,e)
    res+=minedge[0]
  return res
print(prim_heap())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
d = dict()
l = []
for i in range(n):
  x,y = map(int, input().split())
  d[(x,y)] = i
  l.append((x,y))
road = [dict() for _ in range(n)]
l.sort()
for i in range(n-1):
  road[d[l[i]]][d[l[i+1]]] = l[i+1][0]-l[i][0]
  road[d[l[i+1]]][d[l[i]]] = l[i+1][0]-l[i][0]
l.sort(key=lambda x:x[1])
for i in range(n-1):
  if d[l[i+1]] in road[d[l[i]]]:
    road[d[l[i]]][d[l[i+1]]] = min(l[i+1][1]-l[i][1],road[d[l[i]]][d[l[i+1]]])
    road[d[l[i+1]]][d[l[i]]] = min(l[i+1][1]-l[i][1],road[d[l[i+1]]][d[l[i]]])
  else:
    road[d[l[i]]][d[l[i+1]]] = l[i+1][1]-l[i][1]
    road[d[l[i+1]]][d[l[i]]] = l[i+1][1]-l[i][1]

def prim(n, cost):
    mincost = [float("inf")]*n
    used = [False] * n
    mincost[0] = 0
    res = 0

    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1 or mincost[i] < mincost[v]):
                v = i
        if v == -1:
            break
        used[v] = True
        res += mincost[v]
        for i in cost[v]:
            mincost[i] = min(mincost[i],cost[v][i])
    return res

print(prim(n, road))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

X = []
Y = []

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

Dist = [[-1]* N for _ in range(N)]

for i in range(N):
    for j in range(i+1, N):
        Dist[i][j] = min(abs(X[i] - X[j]), abs(Y[i] - Y[j]))
        Dist[j][i] = Dist[i][j]

max_d = 10**9 +1
d = [max_d] * N
d[0] = 0
flag = [0] * N

while True:
    min_d = max_d
    for i in range(N):
        if flag[i] == 0 and d[i] < min_d:
            min_d = d[i]
            u = i

    if min_d == max_d:
        break
    
    flag[u] = 1
    
    for i in range(N):
        if flag[i] == 0 and Dist[u][i] >= 0:
            if d[i] > Dist[u][i]:
                d[i] = Dist[u][i]

print(sum(d))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

X = np.array(X)
Y = np.array(Y)
fixed = np.zeros(N, dtype=bool)
fixed[0] = True
cnt = 1
ans = 0

# プリム法 くっつけてく
heap = list(zip(np.minimum(abs(X - X[0]), abs(Y - Y[0])), range(N)))[1:]
heapq.heapify(heap)
while cnt < N:
    dist, v = heapq.heappop(heap)
    if fixed[v]:
        continue
    fixed[v] = True
    ans += dist

    for du in zip(np.minimum(abs(X[~fixed] - X[v]), abs(Y[~fixed] - Y[v])), np.where(~fixed)[0]):
        heapq.heappush(heap, du)
    cnt += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N = int(input())
node = []
INF = float('inf')
for i in range(N):
    xi, yi = map(int, input().split())
    node.append((xi, yi))

def cost(n, m):
    return min(abs(n[0] - m[0]), abs(n[1] - m[1]))

went = [0]
between_edge = []
min_edges = []
for i in range(1, N):
    heapq.heappush(between_edge, (cost(node[0], node[i]), 0, i))

total = 0
while len(went) < N:
    # print(went)
    c, in_X, out_X = heapq.heappop(between_edge)
    if out_X in went:
        continue
    total += c
    went.append(out_X)
    for j in range(N):
        if j not in went:
            heapq.heappush(between_edge, (cost(node[out_X], node[j]), out_X, j))
print(total)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
node = []
used = []
min_cost = []
INF = float('inf')
for i in range(N):
    xi, yi = map(int, input().split())
    node.append((xi, yi))
    min_cost.append(INF)
    used.append(False)

min_cost[0] = 0
res = 0
while True:
    v = -1
    for u in range(N):
        if not used[u] \
            and (v == -1 or min_cost[u] < min_cost[v]):
            v = u
    if v == -1:
        break
    used[v] = True
    res += min_cost[v]
    for u in range(N):
        min_cost[u] = min(min_cost[u], min(abs(node[u][0] - node[v][0]),abs(node[u][1] - node[v][1])))

print(res)

Submission status: Time Limit Exceeded

Solution code:
# ARC 076 D
# クラスカル法による最小全域木問題

# 辺をコストの小さい順に見ていき、閉路ができない(Union-Findで判定)場合は追加する


class UnionFind(object):

    def __init__(self, N):
        self.tree = [i for i in range(N)]
        self.rank = [0] * (N + 1)

    def find(self, x):
        if self.tree[x] == x:
            return x
        else:
            self.tree[x] = self.find(self.tree[x])  # 経路圧縮
            return self.tree[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        # ランクを考慮しない場合はどちらが親になっても良い
        if self.rank[x] < self.rank[y]:
            self.tree[x] = y
        else:
            self.tree[y] = x

        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def has_same_parent(self, x, y):
        return self.find(x) == self.find(y)


class Edge(object):

    def __init__(self, src, dst, cost):
        self.src = src
        self.dst = dst
        self.cost = cost


N = int(input())
V = [tuple(map(int, input().split())) for _ in range(N)]

edges = list()
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        src_x, src_y = V[i]
        dst_x, dst_y = V[j]
        cost = min(abs(dst_x - src_x), abs(dst_y - src_y))
        edges.append(Edge(i, j, cost))

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

cost = 0
uf = UnionFind(N)
for e in edges:
    if uf.find(e.src) != uf.find(e.dst):
        uf.unite(e.src, e.dst)
        cost += e.cost

print(cost)

Submission status: Time Limit Exceeded

Solution code:
# sort 後のイメージがわからなかったので
# http://drken1215.hatenablog.com/entry/2019/02/14/124300 を愚直に実装
# 実装してみると，なるほどなあ感
N = int(input())
X, Y = list(zip(*[list(map(int, input().split())) for i in range(N)]))
index = [i for i in range(N)]

class UnionFind:
  def __init__(self, n=0):
    self.par = [-1] * n
    
  def root(self, x):
    if self.par[x] < 0:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  
  def is_same(self, x, y):
    return self.root(x) == self.root(y)
    
  def merge(self, x, y):
    x, y = self.root(x), self.root(y)
    if x == y:
      return None
    if self.par[x] > self.par[y]:
      x, y = y, x
    self.par[x] += self.par[y]
    self.par[y] = x
    

edges = []
X = sorted(zip(*[X, index]))
for i in range(N-1):
  edges.append([X[i+1][0]-X[i][0], (X[i][1], X[i+1][1])])
  
Y = sorted(zip(*[Y, index]))
for i in range(N-1):
  edges.append([Y[i+1][0]-Y[i][0], (Y[i][1], Y[i+1][1])])

res = 0
edges = sorted(edges)
uf = UnionFind(N)
for e in edges:
  u, v = e[1]
  cost = e[0]
  if uf.is_same(u, v):
    continue
  uf.merge(u, v)
  res += cost
  
print(res)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 高い方をxとする。
        if self.rank[x] < self.rank[y]:
            x,y = y,x
        # 同じ高さの時は高さ+1
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        # yの親をxとし、xのサイズにyのサイズを加える
        self.par[x] += self.par[y]
        self.par[y] = x

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)


from operator import itemgetter


n = int(input())

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

x = sorted(xy,key=itemgetter(1))
y = sorted(xy,key=itemgetter(2))

xx = []
yy = []

for i in range(n-1):
    xx.append([x[i+1][1]-x[i][1],x[i][0],x[i+1][0]])
    yy.append([y[i+1][2]-y[i][2],y[i][0],y[i+1][0]])

xx.sort()
yy.sort()
xx.reverse()
yy.reverse()

a = UnionFind(n)

ans = 0

i = 0
xxx = xx.pop()
yyy = yy.pop()
while i!=n-1:
    if xxx[0] < yyy[0]:
        if not a.same(xxx[1],xxx[2]):
            a.unite(xxx[1],xxx[2])
            ans += xxx[0]
            i += 1
        if xx:
            xxx = xx.pop()
        else:
            xxx = [float('inf'),0,0]
    else:
        if not a.same(yyy[1],yyy[2]):
            a.unite(yyy[1],yyy[2])
            ans += yyy[0]
            i += 1
        if yy:
            yyy = yy.pop()
        else:
            yyy = [float('inf'),0,0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 異なる集合に属する場合のみ併合
        if x != y:
            # 高い方をxとする。
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            # 同じ高さの時は高さ+1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # yの親をxとし、xのサイズにyのサイズを加える
            self.par[x] += self.par[y]
            self.par[y] = x

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]

import heapq
from operator import itemgetter

n = int(input())

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

x = sorted(xy,key=itemgetter(1))
y = sorted(xy,key=itemgetter(2))

xx = []
yy = []

for i in range(n-1):
    xx.append([x[i+1][1]-x[i][1],x[i][0],x[i+1][0]])
    yy.append([y[i+1][2]-y[i][2],y[i][0],y[i+1][0]])

heapq.heapify(xx)
heapq.heapify(yy)

a = UnionFind(n)

ans = 0

i = 0
xxx = heapq.heappop(xx)
yyy = heapq.heappop(yy)
while i!=n-1:
    if xxx[0] < yyy[0]:
        if not a.same(xxx[1],xxx[2]):
            a.unite(xxx[1],xxx[2])
            ans += xxx[0]
            i += 1
        if xx:
            xxx = heapq.heappop(xx)
        else:
            xxx = [float('inf'),0,0]
    else:
        if not a.same(yyy[1],yyy[2]):
            a.unite(yyy[1],yyy[2])
            ans += yyy[0]
            i += 1
        if yy:
            yyy = heapq.heappop(yy)
        else:
            yyy = [float('inf'),0,0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 異なる集合に属する場合のみ併合
        if x != y:
            # 高い方をxとする。
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            # 同じ高さの時は高さ+1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # yの親をxとし、xのサイズにyのサイズを加える
            self.par[x] += self.par[y]
            self.par[y] = x

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]


from operator import itemgetter

n = int(input())

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

x = sorted(xy,key=itemgetter(1))
y = sorted(xy,key=itemgetter(2))

xx = []
yy = []

for i in range(n-1):
    xx.append([x[i][0],x[i+1][0],x[i+1][1]-x[i][1]])
    yy.append([y[i][0],y[i+1][0],y[i+1][2]-y[i][2]])

xx.sort(key=itemgetter(2))
yy.sort(key=itemgetter(2))
xx.reverse()
yy.reverse()

a = UnionFind(n)

ans = 0

i = 0
xxx = xx.pop()
yyy = yy.pop()
while i!=n-1:
    if xxx[2] < yyy[2]:
        if not a.same(xxx[0],xxx[1]):
            a.unite(xxx[0],xxx[1])
            ans += xxx[2]
            i += 1
        if xx:
            xxx = xx.pop()
        else:
            xxx = [0,0,float('inf')]
    else:
        if not a.same(yyy[0],yyy[1]):
            a.unite(yyy[0],yyy[1])
            ans += yyy[2]
            i += 1
        if yy:
            yyy = yy.pop()
        else:
            yyy = [0,0,float('inf')]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
from scipy.sparse import lil_matrix

N = int(input())
edge = lil_matrix((N,N))

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]
for key in [itemgetter(1), itemgetter(2)]:
  XY.sort(key = key)
  for i in range(N-1):
    i1,x1,y1 = XY[i]
    i2,x2,y2 = XY[i+1]
    d = min(abs(x1-x2),abs(y1-y2))
    edge[i1,i2] = d

edge = edge.tocsr()

# 最小全域木
from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(edge, overwrite = True).astype(int)
answer = tree.sum()
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
from scipy.sparse import lil_matrix

N = int(input())
edge = lil_matrix((N,N))

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]
for key in [itemgetter(1), itemgetter(2)]:
  XY.sort(key = key)
  for i in range(N-1):
    i1,x1,y1 = XY[i]
    i2,x2,y2 = XY[i+1]
    d = min(abs(x1-x2),abs(y1-y2))
    edge[i1,i2] = d
    edge[i2,i1] = d

edge = edge.tocsc()

# 最小全域木
from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(edge, overwrite = True).astype(int)
answer = tree.sum()
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def MST(n, E):
    def par(m):
        if UF[m] == m:
            return m
        ret = par(UF[m])
        UF[m] = ret
        return ret
    
    UF = [i for i in range(n)]
    E = sorted(E, key=lambda x: x[2])
    ans = 0
    for i, j, d in E:
        if par(i) != par(j):
            ans += d
            UF[par(i)] = par(j)
    return ans

N = int(input())

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

F = []
Y = sorted(X, key = lambda x: x[1])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][1]-Y[i][1])))

Y = sorted(X, key = lambda x: x[2])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][2]-Y[i][2])))

print(MST(N, F))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

def MST(n, E):
    def par(m):
        if UF[m] == m:
            return m
        ret = par(UF[m])
        UF[m] = ret
        return ret
    
    UF = [i for i in range(n)]
    E = sorted(E, key=lambda x: x[2])
    ans = 0
    for i, j, d in E:
        if par(i) != par(j):
            ans += d
            UF[par(i)] = par(j)
    return ans

N = int(input())

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

F = []
Y = sorted(X, key = lambda x: x[1])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][1]-Y[i][1])))

Y = sorted(X, key = lambda x: x[2])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][2]-Y[i][2])))

print(MST(N, F))

Submission status: Time Limit Exceeded

Solution code:

def update_tree(par, a, b):
    frm = par[a][0] if par[par[a][0]][1] < par[par[b][0]][1] else par[b][0]
    to = par[b][0] if frm == par[a][0] else par[a][0]
    if par[par[frm][0]][1] + 1> par[par[to][0]][1]:
        par[par[to][0]][1] = par[par[frm][0]][1] + 1
    
    while par[frm][0] != par[par[frm][0]][0]: 
        par[frm][0], frm = to, par[frm][0]
    par[frm][0] = to

def get_par(par, p):
    while par[p][0] != par[p][1]:
        p = par[p][0]
    return p

manhattan = lambda x,y:min(abs(x[0] - y[0]), abs(x[1]- y[1]))
N = int(input())
points = []
edges = []
for i in range(N):
    x,y = map(int, input().split())
    points.append([i,i,[x,y]])
points.sort(key=lambda x:x[2][0])
for i in range(N-1):
    edges.append((abs(points[i][2][0] - points[i+1][2][0]), points[i][1], points[i+1][1]))
points.sort(key=lambda x:x[2][1])
for i in range(N-1):
    edges.append((abs(points[i][2][1] - points[i+1][2][1]), points[i][1], points[i+1][1]))
edges.sort(key=lambda x:x[0], reverse=True)
cost = 0
count = 0
points.sort()
while count < N - 1:
    edge = edges.pop()
    if get_par(points, edge[1]) == get_par(points, edge[2]):
        continue
    cost += edge[0]
    count += 1
    update_tree(points, edge[1], edge[2])
print(cost)

Submission status: Time Limit Exceeded

Solution code:

def update_tree(par, a, b):
    frm = par[a][0] if par[par[a][0]][1] < par[par[b][0]][1] else par[b][0]
    to = par[b][0] if frm == par[a][0] else par[a][0]
    if par[par[frm][0]][1] > par[par[to][0]][1]:
        par[par[to][0]][1] = par[par[frm][0]][1]
    
    while par[frm][0] != par[par[frm][0]][0]: 
        par[frm][0], frm = to, par[frm][0]
    par[frm][0] = to

def get_par(par, p):
    while par[p][0] != par[p][1]:
        p = par[p][0]
    return p

manhattan = lambda x,y:min(abs(x[0] - y[0]), abs(x[1]- y[1]))
N = int(input())
points = []
edges = []
for i in range(N):
    x,y = map(int, input().split())
    points.append([i,i,[x,y]])
points.sort(key=lambda x:x[2][0])
for i in range(N-1):
    edges.append((abs(points[i][2][0] - points[i+1][2][0]), points[i][1], points[i+1][1]))
points.sort(key=lambda x:x[2][1])
for i in range(N-1):
    edges.append((abs(points[i][2][1] - points[i+1][2][1]), points[i][1], points[i+1][1]))
edges.sort(key=lambda x:x[0], reverse=True)
cost = 0
count = 0
points.sort()
while count < N - 1:
    edge = edges.pop()
    if get_par(points, edge[1]) == get_par(points, edge[2]):
        continue
    cost += edge[0]
    count += 1
    update_tree(points, edge[1], edge[2])
print(cost)

Submission status: Time Limit Exceeded

Solution code:

def update_tree(par, a, b):
    frm = par[a][0] if par[par[a][0]][1] < par[par[b][0]][1] else par[b][0]
    to = par[b][0] if frm == par[a][0] else par[a][0]
    if par[par[frm][0]][1] > par[par[to][0]][1]:
        par[par[to][0]][1] = par[par[frm][0]][1]
    
    while par[frm][0] != par[par[frm][0]][0]: 
        par[frm][0], frm = to, par[frm][0]
    par[frm][0] = to

def get_par(par, p):
    while par[p][0] != par[p][1]:
        p = par[p][0]
    return p

manhattan = lambda x,y:min(abs(x[0] - y[0]), abs(x[1]- y[1]))
N = int(input())
points = []
edges = []
for i in range(N):
    x,y = map(int, input().split())
    points.append([i,i,[x,y]])
    for j in range(i):
        edges.append((abs(points[i][2][0] - points[j][2][0]), j, i))
        edges.append((abs(points[i][2][1] - points[j][2][1]), j, i))
edges.sort(key=lambda x:x[0], reverse=True)
cost = 0
count = 0
while count < N - 1:
    edge = edges.pop()
    if get_par(points, edge[1]) == get_par(points, edge[2]):
        continue
    cost += edge[0]
    count += 1
    update_tree(points, edge[1], edge[2])
print(cost)

Submission status: Time Limit Exceeded

Solution code:

def update_tree(par, a, b):
    frm = par[a][0] if par[par[a][0]][1] < par[par[b][0]][1] else par[b][0]
    to = par[b][0] if frm == par[a][0] else par[a][0]
    if par[par[frm][0]][1] > par[par[to][0]][1]:
        par[par[to][0]][1] = par[par[frm][0]][1]
    
    while par[frm][0] != par[par[frm][0]][0]:
        par[frm][0], frm = to, par[frm][0]
    par[frm][0] = to

def is_match(par, p):
    while par[p][0] != par[p][1]:
        p = par[p][0]
    return p

manhattan = lambda x,y:min(abs(x[0] - y[0]), abs(x[1]- y[1]))
N = int(input())

points = []
for i in range(N):
    x,y = map(int, input().split())
    points.append([i,i,[x,y]])
edges = []
for i in range(N-1):
    for j in range(i+1,N):
        edges.append((manhattan(points[i][2], points[j][2]), i, j))
edges.sort(key=lambda x:x[0])
cost = 0
for i in range(len(edges)):
    # print(edges[i], is_match(points, edges[i][1]), is_match(points, edges[i][2]),points)
    if is_match(points, edges[i][1]) == is_match(points, edges[i][2]):
        # print()
        continue
    cost += edges[i][0]
    update_tree(points, edges[i][1], edges[i][2])
print(cost)

Submission status: Time Limit Exceeded

Solution code:
import heapq
def prim_heap():
    used = [True]*n #True:不使用
    edgelist = []
    for e in edge[0]: #連結なのでedge[0]は必ず存在する
        heapq.heappush(edgelist,e)
    used[0] = False #番号0の頂点を始点とする
    res = 0 #答え
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]: #取り出した辺の行き先が使用済みなら
            continue #捨てる
        v = minedge[1] #そうでないなら行き先を使用済みにする
        used[v] = False
        for e in edge[v]: #行き先の頂点がつながる辺において
            if used[e[1]]: #その先の頂点が未使用なら
                heapq.heappush(edgelist,e) #次につなげる辺の候補にする
        res += minedge[0] #コストを足す
    return res

#########################
n = int(input())
L = []
for i in range(n):
    a,b = map(int,input().split())
    L.append([i,a,b])
L = sorted(L, key = lambda x:x[1])
edge = [[] for i in range(n)] # edge[i]:[コスト,行先]
for i in range(n):
    if i == 0:
        edge[L[0][0]].append([min(abs(L[0][1]-L[1][1]),abs(L[0][2]-L[1][2])),L[1][0]])
        edge[L[1][0]].append([min(abs(L[0][1]-L[1][1]),abs(L[0][2]-L[1][2])),L[0][0]])
    elif i == n-1:
        edge[L[n-1][0]].append([min(abs(L[n-1][1]-L[n-2][1]),abs(L[n-1][2]-L[n-2][2])),L[n-2][0]])
        edge[L[n-2][0]].append([min(abs(L[n-1][1]-L[n-2][1]),abs(L[n-1][2]-L[n-2][2])),L[n-1][0]])
    else:
        edge[L[i][0]].append([min(abs(L[i][1]-L[i-1][1]),abs(L[i][2]-L[i-1][2])),L[i-1][0]])
        edge[L[i-1][0]].append([min(abs(L[i][1]-L[i-1][1]),abs(L[i][2]-L[i-1][2])),L[i][0]])
        edge[L[i][0]].append([min(abs(L[i][1]-L[i+1][1]),abs(L[i][2]-L[i+1][2])),L[i+1][0]])
        edge[L[i+1][0]].append([min(abs(L[i][1]-L[i+1][1]),abs(L[i][2]-L[i+1][2])),L[i][0]])
L = sorted(L, key = lambda x:x[2])
for i in range(n):
    if i == 0:
        edge[L[0][0]].append([min(abs(L[0][1]-L[1][1]),abs(L[0][2]-L[1][2])),L[1][0]])
        edge[L[1][0]].append([min(abs(L[0][1]-L[1][1]),abs(L[0][2]-L[1][2])),L[0][0]])
    elif i == n-1:
        edge[L[n-1][0]].append([min(abs(L[n-1][1]-L[n-2][1]),abs(L[n-1][2]-L[n-2][2])),L[n-2][0]])
        edge[L[n-2][0]].append([min(abs(L[n-1][1]-L[n-2][1]),abs(L[n-1][2]-L[n-2][2])),L[n-1][0]])
    else:
        edge[L[i][0]].append([min(abs(L[i][1]-L[i-1][1]),abs(L[i][2]-L[i-1][2])),L[i-1][0]])
        edge[L[i-1][0]].append([min(abs(L[i][1]-L[i-1][1]),abs(L[i][2]-L[i-1][2])),L[i][0]])
        edge[L[i][0]].append([min(abs(L[i][1]-L[i+1][1]),abs(L[i][2]-L[i+1][2])),L[i+1][0]])
        edge[L[i+1][0]].append([min(abs(L[i][1]-L[i+1][1]),abs(L[i][2]-L[i+1][2])),L[i][0]])
print(prim_heap())

Submission status: Time Limit Exceeded

Solution code:
import heapq
def prim_heap():
    used = [True]*n #True:不使用
    edgelist = []
    for e in edge[0]: #連結なのでedge[0]は必ず存在する
        heapq.heappush(edgelist,e)
    used[0] = False #番号0の頂点を始点とする
    res = 0 #答え
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]: #取り出した辺の行き先が使用済みなら
            continue #捨てる
        v = minedge[1] #そうでないなら行き先を使用済みにする
        used[v] = False
        for e in edge[v]: #行き先の頂点がつながる辺において
            if used[e[1]]: #その先の頂点が未使用なら
                heapq.heappush(edgelist,e) #次につなげる辺の候補にする
        res += minedge[0] #コストを足す
    return res

n = int(input())
L = []
for i in range(n):
    a,b = map(int,input().split())
    L.append([i,a,b])
L = sorted(L, key = lambda x:x[1])
edge = [[] for i in range(n)] # edge[i]:[コスト,行先]
for i in range(n):
    if i == 0:
        edge[L[0][0]].append([min(abs(L[0][1]-L[1][1]),abs(L[0][2]-L[1][2])),L[1][0]])
        edge[L[1][0]].append([min(abs(L[0][1]-L[1][1]),abs(L[0][2]-L[1][2])),L[0][0]])
    elif i == n-1:
        edge[L[n-1][0]].append([min(abs(L[n-1][1]-L[n-2][1]),abs(L[n-1][2]-L[n-2][2])),L[n-2][0]])
        edge[L[n-2][0]].append([min(abs(L[n-1][1]-L[n-2][1]),abs(L[n-1][2]-L[n-2][2])),L[n-1][0]])
    else:
        edge[L[i][0]].append([min(abs(L[i][1]-L[i-1][1]),abs(L[i][2]-L[i-1][2])),L[i-1][0]])
        edge[L[i-1][0]].append([min(abs(L[i][1]-L[i-1][1]),abs(L[i][2]-L[i-1][2])),L[i][0]])
        edge[L[i][0]].append([min(abs(L[i][1]-L[i+1][1]),abs(L[i][2]-L[i+1][2])),L[i+1][0]])
        edge[L[i+1][0]].append([min(abs(L[i][1]-L[i+1][1]),abs(L[i][2]-L[i+1][2])),L[i][0]])
L = sorted(L, key = lambda x:x[2])
for i in range(n):
    if i == 0:
        edge[L[0][0]].append([min(abs(L[0][1]-L[1][1]),abs(L[0][2]-L[1][2])),L[1][0]])
        edge[L[1][0]].append([min(abs(L[0][1]-L[1][1]),abs(L[0][2]-L[1][2])),L[0][0]])
    elif i == n-1:
        edge[L[n-1][0]].append([min(abs(L[n-1][1]-L[n-2][1]),abs(L[n-1][2]-L[n-2][2])),L[n-2][0]])
        edge[L[n-2][0]].append([min(abs(L[n-1][1]-L[n-2][1]),abs(L[n-1][2]-L[n-2][2])),L[n-1][0]])
    else:
        edge[L[i][0]].append([min(abs(L[i][1]-L[i-1][1]),abs(L[i][2]-L[i-1][2])),L[i-1][0]])
        edge[L[i-1][0]].append([min(abs(L[i][1]-L[i-1][1]),abs(L[i][2]-L[i-1][2])),L[i][0]])
        edge[L[i][0]].append([min(abs(L[i][1]-L[i+1][1]),abs(L[i][2]-L[i+1][2])),L[i+1][0]])
        edge[L[i+1][0]].append([min(abs(L[i][1]-L[i+1][1]),abs(L[i][2]-L[i+1][2])),L[i][0]])
print(prim_heap())