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
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def size(self, x):
        return -self.root[self.find_root(x)]


# adj: [[weight, u, v] * num_edge], V: number of vertices
def kruskal(adj, V):
    adj.sort()
    uf = UnionFind(V)
    ans = 0
    for edge in adj:
        weight, u, v = edge
        if not uf.isSameGroup(u, v):
            ans += weight
            uf.unite(u, v)
    return ans


N = int(input())
x_list = [0] * N
y_list = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    x_list[i] = [x, i]
    y_list[i] = [y, i]

x_list.sort()
y_list.sort()
adj = [0] * (2 * (N-1))
for i in range(N-1):
    adj[2*i] = [x_list[i + 1][0] - x_list[i][0], x_list[i + 1][1], x_list[i][1]]
    adj[2*i+1] = [y_list[i + 1][0] - y_list[i][0], y_list[i + 1][1], y_list[i][1]]

print(kruskal(adj, N))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def size(self, x):
        return -self.root[self.find_root(x)]


# adj: [[weight, u, v] * num_edge], V: number of vertices
def kruskal(adj, V):
    adj.sort()
    uf = UnionFind(V)
    ans = 0
    for edge in adj:
        weight, u, v = edge
        if not uf.isSameGroup(u, v):
            ans += weight
            uf.unite(u, v)
    return ans


N = int(input())
x_list = [0] * N
y_list = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    x_list[i] = [x, i]
    y_list[i] = [y, i]

x_list.sort()
y_list.sort()
adj = [0] * (2 * (N-1))
for i in range(N-1):
    adj[2*i] = [x_list[i + 1][0] - x_list[i][0], x_list[i + 1][1], x_list[i][1]]
    adj[2*i+1] = [y_list[i + 1][0] - y_list[i][0], y_list[i + 1][1], y_list[i][1]]

print(kruskal(adj, 2 * (N - 1)))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def size(self, x):
        return -self.root[self.find_root(x)]


# adj: [[weight, u, v] * num_edge], V: number of vertices
def kruskal(adj, V):
    adj.sort()
    uf = UnionFind(V)
    ans = 0
    for edge in adj:
        weight, u, v = edge
        if not uf.isSameGroup(u, v):
            ans += weight
            uf.unite(u, v)
    return ans


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

x_list.sort()
y_list.sort()
adj = []
for i in range(N-1):
    adj.append([x_list[i + 1][0] - x_list[i][0], x_list[i + 1][1], x_list[i][1]])
    adj.append([y_list[i + 1][0] - y_list[i][0], y_list[i + 1][1], y_list[i][1]])

print(kruskal(adj, 2 * (N - 1)))

Submission status: Time Limit Exceeded

Solution code:
def set(a, b):
  R[a].append(b)
  R[b].append(a)

N = int(input())
xy = [[i] + list(map(int, input().split())) for i in range(N)]
R = [[] for _ in range(N)]
xy.sort(key = lambda x: x[1])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  set(a[0], b[0])
xy.sort(key = lambda x: x[2])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  set(a[0], b[0])

xy.sort()
import heapq
q = [[0, 0]]
L = [True] * N
pop = heapq.heappop
push = heapq.heappush
ans = 0

for _ in range(N):
  k, t = pop(q)
  while not L[t]:
    k, t = pop(q)
  L[t] = False
  ans += k
  for i in R[t]:
    if L[i]:
      x = abs(xy[t][1] - xy[i][1])
      x = min(x, abs(xy[t][2] - xy[i][2]))
      push(q, [x, i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def set(a, b, d):
  if D[a][b] == -1 or D[a][b] > d:
    D[a][b] = d
    R[a].append(b)
  if D[b][a] == -1 or D[b][a] > d:
    D[b][a] = d
    R[b].append(a)

N = int(input())
xy = [[i] + list(map(int, input().split())) for i in range(N)]
M = 10 ** 20
R = [[] for _ in range(N)]
D = [[-1] * N for _ in range(N)]
xy.sort(key = lambda x: x[1])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  d = abs(a[1] - b[1])
  set(a[0], b[0], d)
xy.sort(key = lambda x: x[2])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  d = abs(a[2] - b[2])
  set(a[0], b[0], d)

import heapq
q = [[0, 0]]
L = [True] * N
pop = heapq.heappop
push = heapq.heappush
ans = 0

for _ in range(N):
  k, t = pop(q)
  while not L[t]:
    k, t = pop(q)
  L[t] = False
  ans += k
  for i in R[t]:
    if L[i]:
      push(q, [D[t][i], i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def setR(a, b):
  if a in R: R[a].append(b)
  else: R[a] = [b]
                
def set(a, b, d):
  setR(a, b)
  setR(b, a)
  D[a][b] = min(D[a][b], d)
  D[b][a] = min(D[b][a], d)

N = int(input())
xy = [[i] + list(map(int, input().split())) for i in range(N)]
M = 10 ** 20
R = {}
D = [[M] * N for _ in range(N)]
xy.sort(key = lambda x: x[1])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  d = abs(a[1] - b[1])
  set(a[0], b[0], d)
xy.sort(key = lambda x: x[2])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  d = abs(a[2] - b[2])
  set(a[0], b[0], d)

import heapq
q = [[0, 0]]
L = [True] * N
pop = heapq.heappop
push = heapq.heappush
ans = 0
for _ in range(N):
  k, t = pop(q)
  while not L[t]:
    k, t = pop(q)
  L[t] = False
  ans += k
  for i in R[t]:
    if L[i]:
      push(q, [D[t][i], i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import array

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            self.parent[x]=self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

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

def compute_mst_kruskal(max_v, edges):
    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(max_v)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    return weight

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))
    print(compute_mst_kruskal(N,edges))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import array
import collections

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            self.parent[x]=self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

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

def compute_mst_kruskal(max_v, edges):
    edges.sort(key=lambda edge: edge.weight)
    uf = UnionFind(max_v)
    weight = 0

    for edge in edges:
        if not uf.same(edge.start, edge.end):
            uf.unite(edge.start, edge.end)
            weight+=edge.weight
    return weight

def main():
    Edge = collections.namedtuple('Edge',('start','end','weight'))
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app(Edge(xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app(Edge(yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))
    ans = compute_mst_kruskal(N,edges)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import array
import collections

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            self.parent[x]=self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

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

def compute_mst_kruskal(max_v, edges):
    edges.sort(key=lambda edge: edge.weight)
    uf = UnionFind(max_v)
    weight = 0

    for edge in edges:
        if not uf.same(edge.start, edge.end):
            uf.unite(edge.start, edge.end)
            weight+=edge.weight
    return weight
    
Edge = collections.namedtuple('Edge',('start','end','weight'))
N = int(input())
xli = []
yli = []


for i in range(N):
    x,y = [int(x) for x in input().split()]
    xli.append([x-1,i])
    yli.append([y-1,i])
xli.sort()
yli.sort()

edges = []
for i in range(N-1):
    edges.append(Edge(xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
    edges.append(Edge(yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))
ans = compute_mst_kruskal(N,edges)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.size_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.size_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        parent = self.root()
        return parent.group_id_

    def size(self):
        parent = self.root()
        return parent.size_

    def unite(self, unite_node):
        parent = self.root()
        unite_parent = unite_node.root()

        if parent.group_id_ != unite_parent.group_id_:
            if parent.size() > unite_parent.size():
                unite_parent.parent_ = parent
                parent.size_ = parent.size_ + unite_parent.size_
            else:
                parent.parent_ = unite_parent
                unite_parent.size_ = parent.size_ + unite_parent.size_
    def is_group(self,other):#selfとotherが同じグループに属するか
        return self.root()==other.root()

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()
G=[]
for i in range(N-1):
  G.append([X[i+1][0]-X[i][0],X[i][1],X[i+1][1]])
  G.append([Y[i+1][0]-Y[i][0],Y[i][1],Y[i+1][1]])
G.sort()
U=[UnionFindNode(i) for i in range(N)]
ans=0
for i in range(len(G)):
    c,a,b=G[i]
    if U[a].is_group(U[b]):
        continue
    U[a].unite(U[b])
    ans+=c
    if U[0].size()==N:
        print(ans)
        quit()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)
 
    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
 
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
        
n=int(input())
xlist=[]
ylist=[]
rlist=[]
for i in range(n):
  x,y=map(int,input().split())
  xlist.append([x,i])
  ylist.append([y,i])
xlist=sorted(xlist,key=lambda x:x[0])
ylist=sorted(ylist,key=lambda x:x[0])
for i in range(1,n):
  cost=xlist[i][0]-xlist[i-1][0]
  rlist.append([cost,xlist[i][1],xlist[i-1][1]])
  cost=ylist[i][0]-ylist[i-1][0]
  rlist.append([cost,ylist[i][1],ylist[i-1][1]])
rlist=sorted(rlist,key=lambda x:x[0])
cost=0
t=UnionFind(n)
for c,p1,p2 in rlist:
  if t.isSameGroup(p1,p2):
    continue
  else:
    cost+=c
    t.Unite(p1,p2)
print(cost)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys 
    input = sys.stdin.readline
    from heapq import heappop,heappush
    from operator import itemgetter
    
    def prim():
        used = [True]*n
        edgelist = []
        for e in edge[0]:
            heappush(edgelist,e)
        used[0] = False
        res = 0
        while len(edgelist) != 0:
            short_edge = heappop(edgelist)
            if not used[short_edge[1]]:
                continue
            v = short_edge[1]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heappush(edgelist,e)
            res += short_edge[0]
        return res

    n = int(input())
    A = [list(map(int,input().split()))+[i] for i in range(n)]
    A.append([-10**12,-10**12,-1])
    A.append([10**12,10**12,-1])
    X = sorted(A)
    Y = sorted(A,key = itemgetter(1))
    d = []
    dapp = d.append
    for i in range(1,n+1):
        sx = X[i-1][0]
        sy = Y[i-1][1]
        mx = X[i][0]
        my = Y[i][1]
        lx = X[i+1][0]
        ly = Y[i+1][1]
        nsx = X[i-1][2]
        nsy = Y[i-1][2]
        nmx = X[i][2]
        nmy = Y[i][2]
        nlx = X[i+1][2]
        nly = Y[i+1][2]
        dapp((nsx,nmx,mx-sx))
        dapp((nmx,nlx,lx-mx))
        dapp((nsy,nmy,my-sy))
        dapp((nmy,nly,ly-my))

    edge = [[] for i in range(n)]
    for x,y,z in d:
        if x==-1 or y==-1:
            continue
        edge[x].append([z,y])
        edge[y].append([z,x])

    print(prim()) 

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys 
    input = sys.stdin.readline
    from heapq import heappop,heappush
    from operator import itemgetter
    
    def prim():
        used = [True]*n
        edgelist = []
        for e in edge[0]:
            heappush(edgelist,e)
        used[0] = False
        res = 0
        while len(edgelist) != 0:
            short_edge = heappop(edgelist)
            if not used[short_edge[1]]:
                continue
            v = short_edge[1]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heappush(edgelist,e)
            res += short_edge[0]
        return res

    n = int(input())
    A = []
    Aapp = A.append
    for i in range(n):
        x = list(map(int,input().split()))+[i]
        Aapp(x)
    Aapp([-10**12,-10**12,-1])
    Aapp([10**12,10**12,-1])
    X = sorted(A)
    Y = sorted(A,key = itemgetter(1))
    d = []
    dapp = d.append
    for i in range(1,n+1):
        sx = X[i-1][0]
        sy = Y[i-1][1]
        mx = X[i][0]
        my = Y[i][1]
        lx = X[i+1][0]
        ly = Y[i+1][1]
        nsx = X[i-1][2]
        nsy = Y[i-1][2]
        nmx = X[i][2]
        nmy = Y[i][2]
        nlx = X[i+1][2]
        nly = Y[i+1][2]
        i -= 1
        dapp((nsx,nmx,mx-sx))
        dapp((nmx,nlx,lx-mx))
        dapp((nsy,nmy,my-sy))
        dapp((nmy,nly,ly-my))

    edge = [[] for i in range(n)]
    for x,y,z in d:
        if x==-1 or y==-1:
            continue
        edge[x].append([z,y])
        edge[y].append([z,x])

    print(prim()) 

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    def prim():
        used = [True]*n
        edgelist = []
        for e in edge[0]:
            heappush(edgelist,e)
        used[0] = False
        res = 0
        while len(edgelist) != 0:
            short_edge = heappop(edgelist)
            if not used[short_edge[1]]:
                continue
            v = short_edge[1]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heappush(edgelist,e)
            res += short_edge[0]
        return res

    n = int(input())
    A = [list(map(int,input().split()))+[i] for i in range(n)]
    A.append([-10**12,-10**12,-1])
    A.append([10**12,10**12,-1])
    X = sorted(A)
    Y = sorted(A,key = lambda x:x[1])
    d = []
    for i in range(1,n+1):
        sx = X[i-1][0]
        sy = Y[i-1][1]
        mx = X[i][0]
        my = Y[i][1]
        lx = X[i+1][0]
        ly = Y[i+1][1]
        nsx = X[i-1][2]
        nsy = Y[i-1][2]
        nmx = X[i][2]
        nmy = Y[i][2]
        nlx = X[i+1][2]
        nly = Y[i+1][2]
        i -= 1
        d.append((nsx,nmx,mx-sx))
        d.append((nmx,nlx,lx-mx))
        d.append((nsy,nmy,my-sy))
        d.append((nmy,nly,ly-my))

    edge = [[] for i in range(n)]
    for x,y,z in d:
        if x==-1 or y==-1:
            continue
        edge[x].append([z,y])
        edge[y].append([z,x])

    print(prim())

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush

def prim():
    used = [True]*n
    edgelist = []
    for e in edge[0]:
        heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        short_edge = heappop(edgelist)
        if not used[short_edge[1]]:
            continue
        v = short_edge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heappush(edgelist,e)
        res += short_edge[0]
    return res

n = int(input())
A = [list(map(int,input().split()))+[i] for i in range(n)]
A.append([-10**12,-10**12,-1])
A.append([10**12,10**12,-1])
X = sorted(A)
Y = sorted(A,key = lambda x:x[1])
d = []
for i in range(1,n+1):
    sx = X[i-1][0]
    sy = Y[i-1][1]
    mx = X[i][0]
    my = Y[i][1]
    lx = X[i+1][0]
    ly = Y[i+1][1]
    nsx = X[i-1][2]
    nsy = Y[i-1][2]
    nmx = X[i][2]
    nmy = Y[i][2]
    nlx = X[i+1][2]
    nly = Y[i+1][2]
    i -= 1
    d.append((nsx,nmx,mx-sx))
    d.append((nmx,nlx,lx-mx))
    d.append((nsy,nmy,my-sy))
    d.append((nmy,nly,ly-my))

edge = [[] for i in range(n)]
for x,y,z in d:
    if x==-1 or y==-1:
        continue
    edge[x].append([z,y])
    edge[y].append([z,x])

print(prim())

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush

def prim():
    used = [True]*n
    edgelist = []
    for e in edge[0]:
        heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        short_edge = heappop(edgelist)
        if not used[short_edge[1]]:
            continue
        v = short_edge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heappush(edgelist,e)
        res += short_edge[0]
    return res

n = int(input())
A = [list(map(int,input().split()))+[i] for i in range(n)]
A.append([-10**12,-10**12,-1])
A.append([10**12,10**12,-1])
X = sorted(A)
Y = sorted(A,key = lambda x:x[1])
distance = [[] for i in range(4*n)]
for i in range(1,n+1):
    sx = X[i-1][0]
    sy = Y[i-1][1]
    mx = X[i][0]
    my = Y[i][1]
    lx = X[i+1][0]
    ly = Y[i+1][1]
    nsx = X[i-1][2]
    nsy = Y[i-1][2]
    nmx = X[i][2]
    nmy = Y[i][2]
    nlx = X[i+1][2]
    nly = Y[i+1][2]
    i -= 1
    distance[4*i] = (nsx,nmx,mx-sx)
    distance[4*i+1] = (nmx,nlx,lx-mx)
    distance[4*i+2] = (nsy,nmy,my-sy)
    distance[4*i+3] = (nmy,nly,ly-my)
    
edge = [[] for i in range(n)]
for i in range(4*n):
    x,y,z = distance[i][0],distance[i][1],distance[i][2]
    if x==-1 or y==-1:
        continue
    edge[x].append([z,y])
    edge[y].append([z,x])

print(prim())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def solve(n, x, y):
    def dist(i, j):
        return min(abs(x[i]-x[j]), abs(y[i]-y[j]))
    que = []
    for p in map(np.argsort, [x, y]):
        for i in range(n-1):
            u, v = p[i], p[i+1]
            que.append((u, v, dist(u, v)))
    parent = {i: i for i in range(n)}
    def find(i):
        if parent[i] == i:
            return i
        else:
            j = find(parent[i])
            parent[i] = j
            return j
    ans = 0
    for u, v, d in sorted(que, key=lambda _: _[2]):
        u = find(u)
        v = find(v)
        if u != v:
            ans += d
            if u > v:
                u, v = v, u
            parent[v] = u
    return ans

n = int(input())
x = np.zeros(n, dtype=int)
y = np.zeros(n, dtype=int)
for i in range(n):
    x[i], y[i] = map(int, input().split())
print(solve(n, x, y))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def solve(n, x, y):
    def dist(i, j):
        return min(abs(x[i]-x[j]), abs(y[i]-y[j]))
    que = []
    for v in [x, y]:
        p = np.argsort(v)
        for i in range(n-1):
            u, v = p[i], p[i+1]
            que.append((u, v, dist(u, v)))
    parent = {i: i for i in range(n)}
    def find(i):
        if parent[i] == i:
            return i
        else:
            return find(parent[i])
    ans = 0
    for u, v, d in sorted(que, key=lambda _: _[2]):
        u = find(u)
        v = find(v)
        if u != v:
            ans += d
            if u > v:
                u, v = v, u
            parent[u] = v
    return ans

n = int(input())
x = np.zeros(n, dtype=int)
y = np.zeros(n, dtype=int)
for i in range(n):
    x[i], y[i] = map(int, input().split())
print(solve(n, x, y))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def solve(n, x, y):
    def dist(i, j):
        return min(abs(x[i]-x[j]), abs(y[i]-y[j]))
    que = []
    for v in [x, y]:
        p = np.argsort(v)
        for i in range(n-1):
            u, v = p[i], p[i+1]
            que.append((u, v, dist(u, v)))
    parent = {i: i for i in range(n)}
    def find(i):
        if parent[i] == i:
            return i
        else:
            j = find(parent[i])
            parent[i] = j
            return j
    que = list(sorted(que, key=lambda _: _[2]))
    ans = 0
    while que != []:
        u, v, d = que.pop(0)
        u = find(u)
        v = find(v)
        if u != v:
            ans += d
            parent[u] = v
    return ans

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def solve(n, x, y):
    def dist(i, j):
        return min(abs(x[i]-x[j]), abs(y[i]-y[j]))
    que = []
    for v in [x, y]:
        p = np.argsort(v)
        for i in range(n-1):
            u, v = p[i], p[i+1]
            que.append((u, v, dist(u, v)))
    parent = {i: i for i in range(n)}
    def find(i):
        if parent[i] == i:
            return i
        else:
            return find(parent[i])
    que = list(sorted(que, key=lambda _: _[2]))
    ans = 0
    while que != []:
        u, v, d = que.pop(0)
        u = find(u)
        v = find(v)
        if u != v:
            ans += d
            if u > v:
                u, v = v, u
            parent[u] = v
    return ans

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def solve(n, x, y):
    def dist(i, j):
        return min(abs(x[i]-x[j]), abs(y[i]-y[j]))
    que = []
    for v in [x, y]:
        p = np.argsort(v)
        for i in range(n-1):
            u, v = p[i], p[i+1]
            que.append((u, v, dist(u, v)))
    parent = {i: i for i in range(n)}
    def find(i):
        if parent[i] == i:
            return i
        else:
            return find(parent[i])
    def union(i, j):
        i = find(i)
        j = find(j)
        if i > j:
            i, j = j, i
        parent[j] = i
    que = list(sorted(que, key=lambda _: _[2]))
    ans = 0
    while que != []:
        u, v, d = que.pop(0)
        if find(u) != find(v):
            ans += d
        union(u, v)
    return ans

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def solve(n, x, y):
    def dist(i, j):
        return min(abs(x[i]-x[j]), abs(y[i]-y[j]))
    que = []
    for v in [x, y]:
        p = np.argsort(v)
        for i in range(n-1):
            u, v = p[i], p[i+1]
            que.append((u, v, dist(u, v)))
    parent = {i: i for i in range(n)}
    def find(i):
        if parent[i] == i:
            return i
        else:
            return find(parent[i])
    def union(i, j):
        i = find(i)
        j = find(j)
        if i > j:
            i, j = j, i
        parent[j] = i
    que = sorted(que, key=lambda _: _[2])
    ans = 0
    while que != []:
        u, v, d = que.pop(0)
        if find(u) != find(v):
            ans += d
        union(u, v)
    return ans

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