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 heapq
class Graph:
    def __init__(self,v,edgelist,w_v = None,directed = False):
        super().__init__()
        self.v = v
        self.w_e = [{} for _ in [0]*self.v]
        self.neighbor = [[] for _ in [0]*self.v]
        self.w_v = w_v
        self.directed = directed

        for i,j,w in edgelist:
            self.w_e[i][j] = w
            self.neighbor[i].append(j)

    def dijkstra(self,v_n):
        d = [float('inf')]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

    def warshallFloyd(self):
        d = [[10**18]*self.v for _ in [0]*self.v]
        for i in range(self.v):
            d[i][i] = 0
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
        
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    check = d[i][k] + d[k][j]
                    if d[i][j] > check:
                        d[i][j] = check
        return d

    def prim(self):
        gb = GraphBuilder(self.v,self.directed)

        queue = []
        for i,w in self.w_e[0].items(): heapq.heappush(queue,(w,0,i))
        rest = [True]*self.v
        rest[0] = False

        while len(queue)>0:
            w,i,j = heapq.heappop(queue)
            if rest[j]:
                gb.addEdge(i,j,w)
                rest[j] = False
                for k,w in self.w_e[j].items():
                    heapq.heappush(queue,(w,j,k))

        return gb

class Tree():
    def __init__(self,v,e):
        pass

class GraphBuilder():
    def __init__(self,v,directed = False):
        self.v = v
        self.directed = directed
        self.edge = []

    def addEdge(self,i,j,w=1):
        if not self.directed:
            self.edge.append((j,i,w))
        self.edge.append((i,j,w))

    def addEdges(self,edgelist,weight = True):
        if weight:
            if self.directed:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
            else:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
                    self.edge.append((j,i,w))
        else:
            if self.directed:
                for i,j,w in edgelist:
                    self.edge.append((i,j,1))
            else:
                for i,j,w in edgelist:
                    self.edge.append((i,j,1))
                    self.edge.append((j,i,1))
            

    def addAdjMat(self, mat):
        for i,mat_i in enumerate(mat):
            for j,w in enumerate(mat_i):
                self.edge.append((i,j,w))

    def buildTree(self):
        pass

    def buildGraph(self):
        return Graph(self.v,self.edge,directed=self.directed)

def main():

    n= int(input())
    edge = []
    for i in range(n):
      x,y = list(map(int,input().split()))
      edge.append((x,y,i))
    
    xs = sorted(edge,key=lambda a:a[0])
    ys = sorted(edge,key=lambda a:a[1])

    edge = []
    
    for i in range(n-1):
      x1,y1,p1 = xs[i]
      x2,y2,p2 = xs[i+1]
      edge.append((p1,p2,min(x2-x1,abs(y2-y1))))
      
      x1,y1,p1 = ys[i]
      x2,y2,p2 = ys[i+1]
      edge.append((p1,p2,min(abs(x2-x1),y2-y1)))
      
      
    gb = GraphBuilder(n)
    gb.addEdges(edge)

    mint = gb.buildGraph().prim()

    ans = 0
    for a in mint.edge:
      ans+=a[2]
    print(ans//2)
      
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
from collections import defaultdict
INF = float('inf')
class Prim:

    def __init__(self,N):#Nはグラフのノード数
        self.N = N
        self.cost = defaultdict(list)
        self.used = [False for _ in range(N)]
    
    def setcost(self,u,v,w):
        self.cost[u].append((v,w))
        self.cost[v].append((u,w))
    
    def prim(self):
        que = []
        heapify(que)
        used = self.used
        for e in self.cost[0]:
            heappush(que,[e[1],e[0]])
        used[0] = True
        res = 0
        while que:
            p = heappop(que)
            cos,v = p
            if used[v]:continue
            self.used[v] = True
            for e in self.cost[v]:
                if not used[e[0]]:
                    heappush(que,[e[1],e[0]])      
            res += cos
        return res

def main():
    N = int(input())
    cost = []
    for i in range(N):
        x,y = map(int,input().split())
        cost.append((x,y,i))
    prim = Prim(N)
    x = sorted(cost,key=lambda x: x[0])
    y = sorted(cost,key=lambda x: x[1])
    for i in range(N-1):
        a,b,u = x[i]
        c,d,v = x[i+1]
        w = min(abs(a-c),abs(b-d))
        prim.setcost(u,v,w)
        e,f,s = y[i]
        g,h,t = y[i+1]
        u = min(abs(e-g),abs(f-h))
        prim.setcost(s,t,u)
    ans = prim.prim()
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
from collections import defaultdict
INF = float('inf')
class Prim:

    def __init__(self,N):#Nはグラフのノード数
        self.N = N
        self.cost = defaultdict(list)
        self.used = [False for _ in range(N)]
    
    def setcost(self,u,v,w):
        self.cost[u].append([v,w])
    
    def prim(self):
        que = []
        heapify(que)
        used = self.used
        for e in self.cost[0]:
            heappush(que,[e[1],e[0]])
        used[0] = True
        res = 0
        while que:
            p = heappop(que)
            cos,v = p
            if used[v]:continue
            self.used[v] = True
            for e in self.cost[v]:
                if not used[e[0]]:
                    heappush(que,[e[1],e[0]])      
            res += cos
        return res

def main():
    N = int(input())
    cost = []
    for i in range(N):
        x,y = map(int,input().split())
        cost.append((x,y,i))
    prim = Prim(N)
    x = sorted(cost,key=lambda x: x[0])
    y = sorted(cost,key=lambda x: x[1])
    for i in range(N-1):
        a,b,u = x[i]
        c,d,v = x[i+1]
        prim.setcost(u,v,min(abs(a-c),abs(b-d)))
        prim.setcost(v,u,min(abs(a-c),abs(b-d)))
        e,f,s = y[i]
        g,h,t = y[i+1]
        prim.setcost(s,t,min(abs(e-g),abs(f-h)))
        prim.setcost(t,s,min(abs(e-g),abs(f-h)))
    ans = prim.prim()
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict
N=int(input())
X=[]
Y=[]
dic_x=defaultdict(list)
dic_y=defaultdict(list)
for i in range(N):
  x,y=map(int,input().split())
  dic_x[x].append(i)
  dic_y[y].append(i)
  X.append(x)
  Y.append(y)
X=sorted(X)
Y=sorted(Y)
V=N
E=(V-1)*2
G=[]
for i in range(N-1):
  if i==0:
    x1,x2=X[0],X[1]
    y1,y2=Y[0],Y[1]
  else:
    x1,x2=x_prev,X[i+1]
    y1,y2=y_prev,Y[i+1]
  x_prev=x2
  y_prev=y2
  heapq.heappush(G,(x2-x1,dic_x[x1].pop(),dic_x[x2][0]))
  heapq.heappush(G,(y2-y1,dic_y[y1].pop(),dic_y[y2][0]))
 
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]

def Minmum_Spanning_Tree(G,V,E):
  uf=UnionFind(V)
  T=[]
  tot_weight=0
  while len(T)!=V-1:
    w,u,v=heapq.heappop(G)
    if uf.same(u-1,v-1)==False:
      uf.unite(u-1,v-1)
      tot_weight+=w
      T.append([u,v])
  return [T,tot_weight]

l=Minmum_Spanning_Tree(G,V,E)
T=l[0]
weight=l[1]
print(weight)

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict
N=int(input())
X=[]
Y=[]
dic_x=defaultdict(list)
dic_y=defaultdict(list)
for i in range(N):
  x,y=map(int,input().split())
  dic_x[x].append(i)
  dic_y[y].append(i)
  X.append(x)
  Y.append(y)
X=sorted(X)
Y=sorted(Y)
V=N
E=(V-1)*2
G=[]
for i in range(N-1):
  heapq.heappush(G,(X[i+1]-X[i],dic_x[X[i]].pop(),dic_x[X[i+1]][0]))
  heapq.heappush(G,(Y[i+1]-Y[i],dic_y[Y[i]].pop(),dic_y[Y[i+1]][0]))
 
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]

def Minmum_Spanning_Tree(G,V,E):
  uf=UnionFind(V)
  T=[]
  tot_weight=0
  while len(T)!=V-1:
    w,u,v=heapq.heappop(G)
    if uf.same(u-1,v-1)==False:
      uf.unite(u-1,v-1)
      tot_weight+=w
      T.append([u,v])
  return [T,tot_weight]

l=Minmum_Spanning_Tree(G,V,E)
T=l[0]
weight=l[1]
print(weight)

Submission status: Time Limit Exceeded

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def size(self, x):
        return self.parents[ self.find(x) ] * -1

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

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if(x == y):
            return

        if( self.parents[x_root] <= self.parents[y_root] ):
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def members(self,x):
        root = self.find(x)
        ret = [ i for i in range(self.n) if self.find(i) == root ]
        return ret

    def roots(self):
        ret = [ i for i in range(self.n) if self.parents[i] < 0]
        return ret

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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

xs.sort()
ys.sort()

edges = []
for tmp in [xs,ys]:
    for i in range(n-1):
        tmp_0 = tmp[i]
        tmp_1 = tmp[i+1]
        edges.append([ tmp_1[0] - tmp_0[0], tmp_1[1], tmp_0[1] ])

edges.sort()

ans = 0
uf = UnionFind(n)

for edge in edges:
    cost, a, b = edge
    if uf.same(a,b) == False:
        uf.union(a,b)
        ans += cost

    if( uf.size(a) == n):
        print(ans)
        exit()

Submission status: Time Limit Exceeded

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

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

xs.sort()
ys.sort()

edges = []
for tmp in [xs,ys]:
    for i in range(n-1):
        tmp_0 = tmp[i]
        tmp_1 = tmp[i+1]
        edges.append([ tmp_1[0] - tmp_0[0], tmp_1[1], tmp_0[1] ])

edges.sort()

ans = 0
uf = list(range(n))
remains = set(range(1,n))

def get_root(a):
    tmp = uf[a]
    if(a == tmp):
        return a
    uf[a] = get_root(tmp)
    if((uf[a] == 0)& (a in remains) ):
        remains.remove(a)
    return uf[a]

def update(a, next):
    if(a != uf[a]):
        update(uf[a], next)
    uf[a] = next

# print(edges)

for edge in edges:
    cost, a, b = edge
    root_a = get_root(a)
    root_b = get_root(b)
    min_ = min(root_a, root_b)
    if( root_a != root_b):
        update(a, min_)
        update(b, min_)
        ans += cost
        # print(uf)
        # print(ans)
    if(min_ == 0):
        rem_temp = remains.copy()
        for remain in rem_temp:
            get_root(remain)

        if(len(remains) == 0):
            print(ans)
            exit()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from heapq import heappush, heappop, nsmallest
    from itertools import combinations
    import sys
    input = sys.stdin.readline
    n = int(input())
    A = [list(map(int, input().split())) for _ in range(n)]
    def prim_heap():
        used = [False] * (10 ** 5)
        e_lst = []
        for e in edge[0]:
            heappush(e_lst, e)
        used[0] = True
        res = 0
        while e_lst:
            e_min = heappop(e_lst)
            v = e_min[1] - 1
            if used[v]: continue
            used[v] = True
            for e in edge[v]:
                if not used[e[1] - 1]: heappush(e_lst, e)
            res += e_min[0]
        return res

    C = list(combinations(A, 2))
    T = list(combinations(range(1, n + 1), 2))
    W = [min(abs(c[0][0] - c[1][0]), abs(c[0][1] - c[1][1])) for c in C]
    w_list = nsmallest(n, W)
    edge = [[] for _ in range(n + 1)]
    for t, w in zip(T, W):
        if w in w_list:
            edge[t[0]].append((w, t[1]))
            edge[t[1]].append((w, t[0]))
    del edge[0]
    print(prim_heap())
if __name__ == '__main__': main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
from itertools import *
import sys
input = sys.stdin.readline

n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]

def prim_heap():
    used = [False] * (10 ** 5)
    e_lst = []
    for e in edge[0]:
        heappush(e_lst, e)
    used[0] = True
    res = 0
    while e_lst:
        e_min = heappop(e_lst)
        v = e_min[1] - 1
        if used[v]: continue
        used[v] = True
        for e in edge[v]:
            if not used[e[1] - 1]:
                heappush(e_lst, e)
        res += e_min[0]
    return res

C = list(combinations(A, 2))
T = list(combinations(range(1, n + 1), 2))
W = [min(abs(c[0][0] - c[1][0]), abs(c[0][1] - c[1][1])) for c in C]
w_list = nsmallest(n, W)
edge = [[] for _ in range(n + 1)]
for t, w in zip(T, W):
    if w in w_list:
      edge[t[0]].append((w, t[1]))
      edge[t[1]].append((w, t[0]))

del edge[0]
print(prim_heap())

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
input = sys.stdin.readline

def prim_heap():
    used = [False] * n
    e_lst = []
    for e in edge[0]:
        heappush(e_lst, e)
    used[0] = True
    res = 0
    while e_lst:
        e_min = heappop(e_lst)
        v = e_min[1]
        if used[v]: continue
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(e_lst, e)
        res += e_min[0]
    return res

n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]

edge = [[] for _ in range(n)]
for i in range(n - 1):
    for j in range(i + 1, n):
        w = min(abs(A[i][0] - A[j][0]), abs(A[i][1] - A[j][1]))
        if w > n: continue
        edge[i].append((w, j))
        edge[j].append((w, i))
print(prim_heap())

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
from itertools import *
import sys

input = sys.stdin.readline

n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]

def prim_heap():
    used = [False] * (10**5)
    e_lst = []
    for e in edge[0]:
        heappush(e_lst, e)
    used[0] = True
    res = 0
    while e_lst:
        e_min = heappop(e_lst)
        v = e_min[1]-1
        if used[v]: continue
        used[v] = True
        for e in edge[v]:
            if not used[e[1]-1]:
                heappush(e_lst, e)
        res += e_min[0]
    return res

C = list(combinations(A, 2))
T = list(combinations(range(1, n+1), 2))
         
W = [min(abs(c[0][0]-c[1][0]), abs(c[0][1]-c[1][1])) for c in C]

edge = [[] for _ in range(n+1)]
for t, w in zip(T, W):
  edge[t[0]].append((w, t[1]))
  edge[t[1]].append((w, t[0]))
  
del edge[0]
print(prim_heap())

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
input = sys.stdin.readline

def prim_heap():
    used = [False] * n
    e_lst = []
    for e in edge[0]:
        heappush(e_lst, e)
    used[0] = True
    res = 0
    while e_lst:
        e_min = heappop(e_lst)
        v = e_min[1]
        if used[v]: continue
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(e_lst, e)
        res += e_min[0]
    return res

n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]

edge = [[] for _ in range(n)]
for i in range(n - 1):
    for j in range(i + 1, n):
        w = min(abs(A[i][0] - A[j][0]), abs(A[i][1] - A[j][1]))
        edge[i].append((w, j))
        edge[j].append((w, i))

print(prim_heap())

Submission status: Time Limit Exceeded

Solution code:

import heapq
n = int(input())
stw = []
x_list = []
y_list = []
for i in range(n):
  x, y = map(int, input().split())
  x_list += [[x, i]]
  y_list += [[y, i]]
x_list.sort()
y_list.sort()
for [u, fr], [v, to] in zip(x_list, x_list[1:]):
  stw += [[abs(u-v), fr, to]]
for [u, fr], [v, to] in zip(y_list, y_list[1:]):
  stw += [[abs(u-v), fr, to]]
  
heapq.heapify(stw)

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 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())


def kruskal():
  # stw = [[s0, t0, w0], [s1, t1, w1], ..., [sn, tn, wn]]
  # stw: s: 始点, t: 終点, w: st間の重み
  # stwはwを小さい順にソートされたものとする
  res = 0
  uf = UnionFind(n)
  while stw:
    w, s, t = heapq.heappop(stw)
    if not uf.isSameGroup(s, t):
      uf.Unite(s, t)
      res += w
  return res

print(kruskal())

Submission status: Time Limit Exceeded

Solution code:

import heapq
n = int(input())
stw = []
x_list = []
y_list = []
for i in range(n):
  x, y = map(int, input().split())
  x_list += [[x, i]]
  y_list += [[y, i]]
x_list.sort()
y_list.sort()
for i in range(n-1):
  xs = x_list[i][1]
  xt = x_list[i+1][1]
  ys = y_list[i][1]
  yt = y_list[i+1][1]
  dis_x = abs(x_list[i][0]-x_list[i+1][0])
  dis_y = abs(y_list[i][0]-y_list[i+1][0])
  stw += [[dis_x, xs, xt]]
  #stw += [[dis_x, xt, xs]]
  stw += [[dis_y, ys, yt]]
  #stw += [[dis_y, yt, ys]]
  
#print(stw)
heapq.heapify(stw)
#stw = sorted(stw, key=lambda x:x[2])

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 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())


def kruskal():
  # stw = [[s0, t0, w0], [s1, t1, w1], ..., [sn, tn, wn]]
  # stw: s: 始点, t: 終点, w: st間の重み
  # stwはwを小さい順にソートされたものとする
  res = 0
  uf = UnionFind(n)
  while stw:
    w, s, t = heapq.heappop(stw)
    if not uf.isSameGroup(s, t):
      uf.Unite(s, t)
      res += w
  return res

print(kruskal())

Submission status: Time Limit Exceeded

Solution code:

import heapq
n = int(input())
stw = []
x_list = []
y_list = []
for i in range(n):
  x, y = map(int, input().split())
  x_list += [[x, i]]
  y_list += [[y, i]]
x_list.sort()
y_list.sort()
for i in range(n-1):
  xs = x_list[i][1]
  xt = x_list[i+1][1]
  ys = y_list[i][1]
  yt = y_list[i+1][1]
  dis_x = abs(x_list[i][0]-x_list[i+1][0])
  dis_y = abs(y_list[i][0]-y_list[i+1][0])
  stw += [[dis_x, xs, xt]]
  stw += [[dis_x, xt, xs]]
  stw += [[dis_y, ys, yt]]
  stw += [[dis_y, yt, ys]]
  
#print(stw)
heapq.heapify(stw)
#stw = sorted(stw, key=lambda x:x[2])

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 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())


def kruskal():
  # stw = [[s0, t0, w0], [s1, t1, w1], ..., [sn, tn, wn]]
  # stw: s: 始点, t: 終点, w: st間の重み
  # stwはwを小さい順にソートされたものとする
  res = 0
  uf = UnionFind(n)
  while stw:
    w, s, t = heapq.heappop(stw)
    if not uf.isSameGroup(s, t):
      uf.Unite(s, t)
      res += w
  return res

print(kruskal())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
stw = []
x_list = []
y_list = []
for i in range(n):
  x, y = map(int, input().split())
  x_list += [[x, i]]
  y_list += [[y, i]]
x_list.sort()
y_list.sort()
for i in range(n-1):
  xs = x_list[i][1]
  xt = x_list[i+1][1]
  ys = y_list[i][1]
  yt = y_list[i+1][1]
  dis_x = abs(x_list[i][0]-x_list[i+1][0])
  dis_y = abs(y_list[i][0]-y_list[i+1][0])
  stw += [[xs, xt, dis_x]]
  stw += [[xt, xs, dis_x]]
  stw += [[ys, yt, dis_y]]
  stw += [[yt, ys, dis_y]]
  
stw = sorted(stw, key=lambda x:x[2])

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 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())


def kruskal():
  # stw = [[s0, t0, w0], [s1, t1, w1], ..., [sn, tn, wn]]
  # stw: s: 始点, t: 終点, w: st間の重み
  # stwはwを小さい順にソートされたものとする
  res = 0
  uf = UnionFind(n)
  for i in range(len(stw)):
    s, t, w = stw[i]
    if not uf.isSameGroup(s, t):
      uf.Unite(s, t)
      res += w
  return res

print(kruskal())

Submission status: Time Limit Exceeded

Solution code:

import heapq

def input_graph(n):
  graph = [[] for _ in range(n)]
  x_list = []
  y_list = []
  for i in range(n):
    x, y = map(int, input().split())
    x_list += [[x, i]]
    y_list += [[y, i]]
  x_list.sort()
  y_list.sort()

  for i in range(n-1):
    xs = x_list[i][1]
    xt = x_list[i+1][1]
    ys = y_list[i][1]
    yt = y_list[i+1][1]

    dis_x = abs(x_list[i][0]-x_list[i+1][0])
    dis_y = abs(y_list[i][0]-y_list[i+1][0])

    graph[xs] += [[dis_x, xt]]
    graph[xt] += [[dis_x, xs]]
    graph[ys] += [[dis_y, yt]]
    graph[yt] += [[dis_y, ys]]

  return graph

def prim(n, graph):
  # graph[i]は第一要素が重み、第二要素が頂点になるように
  # graph[s] += [[w, t]], w:重み, s,t:頂点
  used = [-1]*n
  edgelist = []
  for e in graph[0]:
    heapq.heappush(edgelist, e)
  used[0] = 1
  res = 0
  while edgelist:
    minedge = heapq.heappop(edgelist)
    if used[minedge[1]] == 1:
      continue 
    v = minedge[1]
    used[v] = 1
    for e in graph[v]:
      if used[e[1]] == -1:
        heapq.heappush(edgelist, e)
    res += minedge[0]
  return res 

def main():
  n = int(input())
  graph = input_graph(n)
  print(prim(n, graph))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:

import heapq
n = int(input())
graph = [[] for _ in range(n)]
x_list = []
y_list = []
for i in range(n):
  x, y = map(int, input().split())
  x_list += [[x, i]]
  y_list += [[y, i]]
x_list.sort()
y_list.sort()

for i in range(n-1):
  xs = x_list[i][1]
  xt = x_list[i+1][1]
  ys = y_list[i][1]
  yt = y_list[i+1][1]

  dis_x = abs(x_list[i][0]-x_list[i+1][0])
  dis_y = abs(y_list[i][0]-y_list[i+1][0])

  graph[xs] += [[dis_x, xt]]
  graph[xt] += [[dis_x, xs]]
  graph[ys] += [[dis_y, yt]]
  graph[yt] += [[dis_y, ys]]

def prim():
  # graph[i]は第一要素が重み、第二要素が頂点になるように
  # graph[s] += [[w, t]], w:重み, s,t:頂点
  used = [-1]*n
  edgelist = []
  for e in graph[0]:
    heapq.heappush(edgelist, e)
  used[0] = 1
  res = 0
  while edgelist:
    minedge = heapq.heappop(edgelist)
    if used[minedge[1]] == 1:
      continue 
    v = minedge[1]
    used[v] = 1
    for e in graph[v]:
      if used[e[1]] == -1:
        heapq.heappush(edgelist, e)
    res += minedge[0]
  return res 

print(prim())

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(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(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 same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(input())
l=sorted([tuple(map(int,input().split())) for i in range(n)])
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
pq=[]
for i in range(n-1):
    pq.append((l[i+1][0]-l[i][0],d[l[i]],d[l[i+1]]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    pq.append((l[i+1][1]-l[i][1],d[l[i]],d[l[i+1]]))
ans=0
pq.sort()
uf=unionfind(n)
for c,x,y in pq:
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
print(ans)

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(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(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 same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(input())
l=sorted([tuple(map(int,input().split())) for i in range(n)])
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
from heapq import heappush,heappop
pq=[]
for i in range(n-1):
    c=l[i+1][0]-l[i][0]
    heappush(pq,(c,d[l[i]],d[l[i+1]]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    c=l[i+1][1]-l[i][1]
    heappush(pq,(c,d[l[i]],d[l[i+1]]))
ans=0
uf=unionfind(n)
while pq:
    c,x,y=heappop(pq)
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
print(ans)