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
sys.setrecursionlimit(10**6)
from heapq import heappop, heappush

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

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

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

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

print(length_sum)

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict

def mst(N, edges):
    start = 0
    ans = 0
    cnt = 0
    in_tree = [False]*N
    q = [(dist, start, to) for to, dist in edges[start]]
    in_tree[start] = True
    heapq.heapify(q)
    while q and cnt < N-1:
        dist, fr, to = heapq.heappop(q)
        if in_tree[to]:
            continue
        in_tree[to] = True
        cnt += 1
        ans += dist
        for to_, dist in edges[to]:
            if not in_tree[to_]:
                heapq.heappush(q, (dist, to, to_))
    return ans

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(key=lambda e:e[0])
Y.sort(key=lambda e:e[0])

edges = defaultdict(list)

for axis in [X, Y]:
    for i in range(N):
        if i > 0:
            i0, i1 = axis[i-1][1], axis[i][1]
            dist = abs(axis[i-1][0] - axis[i][0])
            edges[i0].append((i1, dist))
            edges[i1].append((i0, dist))
        if i < N-1:
            i0, i1 = axis[i+1][1], axis[i][1]
            dist = abs(axis[i+1][0] - axis[i][0])
            edges[i0].append((i1, dist))
            edges[i1].append((i0, dist))

print(mst(N, edges))

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict

def mst(N, edges):
    start = 0
    ans = 0
    cnt = 0
    in_tree = [False]*N
    q = [(dist, start, to) for to, dist in edges[start]]
    in_tree[start] = True
    heapq.heapify(q)
    while q and cnt < N-1:
        dist, fr, to = heapq.heappop(q)
        if in_tree[to]:
            continue
        in_tree[to] = True
        cnt += 1
        ans += dist
        for to_, dist in edges[to]:
            heapq.heappush(q, (dist, to, to_))
    return ans

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(key=lambda e:e[0])
Y.sort(key=lambda e:e[0])

edges = defaultdict(list)

for axis in [X, Y]:
    for i in range(N):
        if i > 0:
            i0, i1 = axis[i-1][1], axis[i][1]
            dist = abs(axis[i-1][0] - axis[i][0])
            edges[i0].append((i1, dist))
            edges[i1].append((i0, dist))
        if i < N-1:
            i0, i1 = axis[i+1][1], axis[i][1]
            dist = abs(axis[i+1][0] - axis[i][0])
            edges[i0].append((i1, dist))
            edges[i1].append((i0, dist))

print(mst(N, edges))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def find(x, U, r):
  p = []
  while not x == U[x]:
    p.append(x)
    x = U[x]
  for x_ in p:
    U[x_] == x
  return x
  
def merge(x, y, U, r):
  x = find(x, U, r)
  y = find(y, U, r)
  
  if x == y:
    return False
  #print(x,y, U)
  if r[x] < r[y]:
    x, y = y, x
  U[y] = x
  r[x] = max(r[y]+1, r[x])
  #print(x,y, U)
  return True
  
U = [i for i in range(N)]
r = [0 for _ in range(N)]

B = []
C = []
for i in range(N):
  u, v = map(int, input().split())
  B.append((u, v, i))
  C.append((v, u, i))
B.sort()
C.sort()


#辺の作成
R = []
for i in range(1,N):
  c = B[i][0] - B[i-1][0]
  p1 = B[i][2]
  p2 = B[i-1][2]
  R.append((c, p1, p2))
  R.append((c, p2, p1))
  
  c = C[i][0] - C[i-1][0]
  p1 = C[i][2]
  p2 = C[i-1][2]
  R.append((c, p1, p2))
  R.append((c, p2, p1))
R.sort()

#Union Find:
U = [i for i in range(N)]
r = [0 for _ in range(N)]
#print(U)  
ans = 0
for road in R:
  c = road[0]
  x = road[1]
  y = road[2]
  if merge(x, y, U, r):
    #print(U)  
    ans += c
#print(U)    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def find(x, U, r):
  p = []
  while not x == U[x]:
    p.append(x)
    x = U[x]
  for x_ in p:
    U[x_] == x
  return x
  
def merge(x, y, U, r):
  x = find(x, U, r)
  y = find(y, U, r)
  
  if x == y:
    return False
  #print(x,y, U)
  if r[x] < r[y]:
    x, y = y, x
  U[y] = x
  r[x] = max(r[y]+1, r[x])
  #print(x,y, U)
  return True
  
U = [i for i in range(N)]
r = [0 for _ in range(N)]

A = [(tuple(map(int, input().split())), j) for j in range(N)]
B = sorted(A)
C = sorted(A, key=lambda t: ((t[0][1],t[0][0]),t[1]))

#辺の作成
R = []
for i in range(1,N):
  c = B[i][0][0] - B[i-1][0][0]
  p1 = B[i][1]
  p2 = B[i-1][1]
  R.append((c, p1, p2))
  R.append((c, p2, p1))
  
  c = C[i][0][1] - C[i-1][0][1]
  p1 = C[i][1]
  p2 = C[i-1][1]
  R.append((c, p1, p2))
  R.append((c, p2, p1))
R.sort()

#Union Find:
U = [i for i in range(N)]
r = [0 for _ in range(N)]
#print(U)  
ans = 0
for road in R:
  c = road[0]
  x = road[1]
  y = road[2]
  if merge(x, y, U, r):
    #print(U)  
    ans += c
#print(U)    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def find(x, U, r):
  while not x == U[x]:
    x = U[x]
  return x
  
def merge(x, y, U, r):
  x = find(x, U, r)
  y = find(y, U, r)
  
  if x == y:
    return False
  #print(x,y, U)
  if r[x] < r[y]:
    x, y = y, x
  U[y] = x
  r[x] = max(r[y]+1, r[x])
  #print(x,y, U)
  return True
  
U = [i for i in range(N)]
r = [0 for _ in range(N)]

A = [(tuple(map(int, input().split())), j) for j in range(N)]
B = sorted(A)
C = sorted(A, key=lambda t: ((t[0][1],t[0][0]),t[1]))

#辺の作成
R = []
for i in range(1,N):
  c = B[i][0][0] - B[i-1][0][0]
  p1 = B[i][1]
  p2 = B[i-1][1]
  R.append((c, p1, p2))
  R.append((c, p2, p1))
  
  c = C[i][0][1] - C[i-1][0][1]
  p1 = C[i][1]
  p2 = C[i-1][1]
  R.append((c, p1, p2))
  R.append((c, p2, p1))
R.sort()

#Union Find:
U = [i for i in range(N)]
r = [0 for _ in range(N)]
#print(U)  
ans = 0
for road in R:
  c = road[0]
  x = road[1]
  y = road[2]
  if merge(x, y, U, r):
    #print(U)  
    ans += c
#print(U)    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x,y = [],[]
for i in range(n):
    a,b = map(int,input().split())
    x.append([a,i])
    y.append([b,i])
x.sort()
y.sort()
g = [[] for _ in range(n)]
for i in range(n-1):
    g[x[i][1]].append([abs(x[i+1][0]-x[i][0]),x[i+1][1]])
    g[x[i+1][1]].append([abs(x[i+1][0]-x[i][0]),x[i][1]])
    g[y[i][1]].append([abs(y[i+1][0]-y[i][0]),y[i+1][1]])
    g[y[i+1][1]].append([abs(y[i+1][0]-y[i][0]),y[i][1]])
import heapq
hq = []
for d,e in g[0]:
    heapq.heappush(hq,[d,e])
cnt = 1
visit = [False]*n
visit[0] = True
ans = 0
while cnt <n:
    cost, end = heapq.heappop(hq)
    if not visit[end]:
        ans += cost
        visit[end] = True
        cnt += 1
        for d,e in g[end]:
            heapq.heappush(hq,[d,e])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

N = int(input())

pos = []
for _ in range(N):
    a, b = map(int, input().split())
    pos.append((a, b))

visited = {v: False for v in pos}
edges = {v: [] for v in pos}
x_sorted = sorted([(p[0], i) for i, p in enumerate(pos)])
for i in range(len(x_sorted) - 1):
    j = x_sorted[i][1]
    l = x_sorted[i+1][1]
    edges[pos[j]].append((pos[l], abs(pos[l][0] - pos[j][0])))
    edges[pos[l]].append((pos[j], abs(pos[l][0] - pos[j][0])))
y_sorted = sorted([(p[1], i) for i, p in enumerate(pos)])
for i in range(len(y_sorted) - 1):
    j = y_sorted[i][1]
    l = y_sorted[i+1][1]
    edges[pos[j]].append((pos[l], abs(pos[l][1] - pos[j][1])))
    edges[pos[l]].append((pos[j], abs(pos[l][1] - pos[j][1])))

que = queue.PriorityQueue()
que.put((0, pos[0]))

res = 0
while not que.empty():
    cost, vertex = que.get()
    if visited[vertex]:
        continue
    visited[vertex] = True
    res += cost

    for to, next_cost in edges[vertex]:
        que.put((next_cost, to))

print(res)

Submission status: Time Limit Exceeded

Solution code:
import queue

N = int(input())

pos = []
for _ in range(N):
    a, b = map(int, input().split())
    pos.append((a - 1, b - 1))

visited = {v: False for v in pos}
que = queue.PriorityQueue()
que.put((0, pos[0]))

res = 0
while not que.empty():
    cost, vertex = que.get()
    if visited[vertex]:
        continue
    visited[vertex] = True
    res += cost

    for i in range(N):
        next_cost = min(abs(pos[i][0] - vertex[0]), abs(pos[i][1] - vertex[1]))
        que.put((next_cost, (pos[i][0], pos[i][1])))

print(res)

Submission status: Time Limit Exceeded

Solution code:
import itertools
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.rank = [1]*n
    
    def root(self, x):
        if x == self.p[x]:
            return x
        self.p[x] = y = self.root(self.p[x])
        return y
    
    def unite(self, x, y):
        px = self.root(x); py = self.root(y)
        if px == py:
            return 0
        rx = self.rank[px]; ry = self.rank[py]
        if ry < rx:
            self.p[py] = px
        elif rx < ry:
            self.p[px] = py
        else:
            self.p[py] = px
            self.rank[px] += 1
        return 1

    def same(self, x, y):
        px = self.root(x); py = self.root(y)
        return px == py

N = int(input())
XY = {i:list(map(int,input().split())) for i in range(N)}

C = itertools.combinations([i for i in range(N)],2)
L = []
for c in C:
    L.append((min(abs(XY[c[0]][0]-XY[c[1]][0]),abs(XY[c[0]][1]-XY[c[1]][1])),c[0],c[1]))
L.sort()
union_find = UnionFind(N)
ans = 0
for d,a,b in L:
    if not union_find.same(a,b):
        ans += d
        union_find.unite(a,b)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC065D

import sys
input=sys.stdin.readline
import heapq

class UnionFind:
    def __init__(self, n):
        self.p=[-1]*n
        self.size=[1]*n
    def root(self, x):
        st=set()
        while(self.p[x]>=0):
            st.add(x)
            x=self.p[x]
        for y in st:
            self.p[y]=x
        return x
    def find(self, x, y):
        return self.root(x)==self.root(y)
    def union(self, x, y):
        r1=self.root(x)
        r2=self.root(y)
        if r1==r2:
            return
        p1=self.p[r1]
        p2=self.p[r2]
        if p1<=p2:
            self.p[r2]=r1
            self.size[r1]+=self.size[r2]
            if p1==p2:
                self.p[r1]-=1
        else:
            self.p[r1]=r2
            self.size[r2]+=self.size[r1]

def main():
    N=int(input())
    r=[tuple(map(int,input().split())) for i in range(N)]
    pq=[]
    for i in range(N):
        for j in range(i+1, N):
            d=min(abs(r[i][0]-r[j][0]), abs(r[i][1]-r[j][1]))
            heapq.heappush(pq,(d,i,j))
    uft=UnionFind(N)
    ans=0
    while(uft.size[uft.root(0)]<N):
        e=heapq.heappop(pq)
        if not(uft.find(e[1],e[2])):
            ans+=e[0]
            uft.union(e[1],e[2])
    print(ans)
    
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1

from collections import defaultdict
from itertools import chain
from bisect import bisect

N = int(input())
points = tuple(tuple(map(int,input().split())) for _ in range(N))

ds = DisjointSet(N)

x_i = sorted((x,i) for i,(x,y) in enumerate(points))
y_i = sorted((y,i) for i,(x,y) in enumerate(points))

xr = [x_i[0]]
yr = [y_i[0]]

for (x0,i0),(x1,i1) in zip(x_i,x_i[1:]):
    if x0 == x1:
        ds.union(i0,i1)
    else:
        xr.append((x1,i1))

for (y0,i0),(y1,i1) in zip(y_i,y_i[1:]):
    if y0 == y1:
        ds.union(i0,i1)
    else:
        yr.append((y1,i1))

deltas = sorted(
        chain(
            ((x1-x0,i0,i1) for (x0,i0), (x1,i1) in zip(xr,xr[1:])),
            ((y1-y0,i0,i1) for (y0,i0), (y1,i1) in zip(yr,yr[1:])),
        )
    )


def it():
    for d,i0,i1 in deltas:
        if ds.find(i0) != ds.find(i1):
            ds.union(i0,i1)
            yield d
print(sum(it()))

Submission status: Time Limit Exceeded

Solution code:
class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1

from collections import defaultdict
from itertools import chain

N = int(input())
points = tuple(tuple(map(int,input().split())) for _ in range(N))

ds = DisjointSet(N)

x_bin = defaultdict(list)
y_bin = defaultdict(list)
for i,(x,y) in enumerate(points):
    x_bin[x].append(i)
    y_bin[y].append(i)

for L in x_bin.values():
    for i,j in zip(L, L[1:]):
        ds.union(i,j)

for L in y_bin.values():
    for i,j in zip(L, L[1:]):
        ds.union(i,j)

X = sorted(x_bin.keys())
Y = sorted(y_bin.keys())
deltas = sorted(
        chain(
            ((x1-x0,x0,x1, True) for x0, x1 in zip(X,X[1:])),
            ((y1-y0,y0,y1, False) for y0, y1 in zip(Y,Y[1:])),
        )
    )

res = 0
for d,v0,v1,xy in deltas:
    b = x_bin if xy else y_bin
    if ds.find(b[v0][0]) != ds.find(b[v1][0]):
        ds.union(b[v0][0],b[v1][0])
        res += d

print(res)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.size = [1] * (n + 1)

    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 same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            if self.same_check(x, y) != True:
                self.size[y] += self.size[x]
                self.size[x] = 0
            self.par[x] = y
        else:
            if self.same_check(x, y) != True:
                self.size[x] += self.size[y]
                self.size[y] = 0
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def siz(self, x):
        x = self.find(x)
        return self.size[x]


N = int(input())
UF = UnionFind(N)
X = []
Y = []
Branch = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((x, i))
    Y.append((y, i))
X.sort()
Y.sort()
for X1, X2 in zip(X, X[1:]):
    Branch.append((X2[0] - X1[0], X1[1], X2[1]))
for Y1, Y2 in zip(Y, Y[1:]):
    Branch.append((Y2[0] - Y1[0], Y1[1], Y2[1]))
Branch.sort()

# 負のとき size, 非負のとき parent
par = [-1] * N
ans = 0
for c, a, b in Branch:
    if N <= 1:
        break
    if not UF.same_check(a, b):
        UF.union(a, b)
        ans += c
        N -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# Union-Find
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x
    return True


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


def size(x):
    return -par[find(x)]


N = int(input())
X = []
Y = []
Branch = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((x, i))
    Y.append((y, i))
X.sort()
Y.sort()
for X1, X2 in zip(X, X[1:]):
    Branch.append((X2[0] - X1[0], X1[1], X2[1]))
for Y1, Y2 in zip(Y, Y[1:]):
    Branch.append((Y2[0] - Y1[0], Y1[1], Y2[1]))
Branch.sort()

# 負のとき size, 非負のとき parent
par = [-1] * N
ans = 0
for c, a, b in Branch:
    if N <= 1:
        break
    if not same(a, b):
        unite(a, b)
        ans += c
        N -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read

def main():
    # heapqをつかうプリム法
    import heapq
    def prim_heap():
        used = [True] * n  # True:不使用
        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

    n = int(input())
    xy = [tuple(map(int, input().split())) for _ in range(n)]
    edge = {e:[] for e in range(n)}
    for i1 in range(n):
        for i2 in range(i1 + 1):
            dis = min(abs(xy[i1][0] - xy[i2][0]), abs(xy[i1][1] - xy[i2][1]))
            edge[i1].append([dis, i2])
            edge[i2].append([dis, i1])
    r = prim_heap()
    print(r)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
x,y=zip(*xy)
x=list(zip(list(range(n)),x))
y=list(zip(list(range(n)),y))
x.sort(key=lambda a:a[1])
y.sort(key=lambda a:a[1])
d=[]
for i in range(n-1):
  d.append([x[i+1][1]-x[i][1],1,x[i+1][0],x[i][0]])
  d.append([y[i+1][1]-y[i][1],1,y[i+1][0],y[i][0]])
d.sort(key=lambda a:a[0],reverse=True)
# Union FInd
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

ans=0
flg=True
uf=UnionFind(n)
while d and uf.group_count()>1:
  dist,f,i,j=d.pop()
  if uf.same(i,j):
    continue
  uf.union(i,j)
  ans+=dist
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def myprim_heap(graph, n):
    #始点sから各頂点への最短距離
    INF = 10**9
    d = [INF] * n
    used = [False] * n #True:未確定
    s = 0
    d[s] = 0
    used[s] = True
    res = 0
    edgelist = []
    for e in graph[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if used[minedge[1]]:
            continue
        res += minedge[0]
        v = minedge[1]
        used[v] = True
        for e in graph[v]:
            if not used[e[1]]:
                heapq.heappush(edgelist, e)
    return res


n = int(input()) 
graph = [[] for _ in range(n)]
ixy = [[i] + [int(x) for x in input().split()] for i in range(n)]

ixy = sorted(ixy, key=lambda x:x[1])
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d = ixy[i+1][1] - ixy[i][1]
    graph[j].append([d,k])
    graph[k].append([d,j])

ixy = sorted(ixy, key=lambda x:x[2])
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d = ixy[i+1][2] - ixy[i][2]
    graph[j].append([d,k])
    graph[k].append([d,j])

res = myprim_heap(graph, n)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def myprim_heap(graph, n):
    #始点sから各頂点への最短距離
    INF = 10**9
    d = [INF] * n
    used = [False] * n #True:未確定
    s = 0
    d[s] = 0
    used[s] = True
    res = 0
    edgelist = []
    for e in graph[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if used[minedge[1]]:
            continue
        res += minedge[0]
        v = minedge[1]
        used[v] = True
        for e in graph[v]:
            if not used[e[1]]:
                heapq.heappush(edgelist, e)
    return res


n = int(input()) 
graph = [[] for _ in range(n)]
ixy = [[i] + [int(x) for x in input().split()] for i in range(n)]

ixy = sorted(ixy, key=lambda x:(x[1], x[2]))
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d = ixy[i+1][1] - ixy[i][1]
    graph[j].append([d,k])
    graph[k].append([d,j])

ixy = sorted(ixy, key=lambda x:(x[2], x[1]))
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d = ixy[i+1][2] - ixy[i][2]
    graph[j].append([d,k])
    graph[k].append([d,j])

res = myprim_heap(graph, n)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def myprim_heap(graph, n):
    #始点sから各頂点への最短距離
    INF = 10**9
    d = [INF] * n
    used = [False] * n #True:未確定
    s = 0
    d[s] = 0
    used[s] = True
    res = 0
    edgelist = []
    for e in graph[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if used[minedge[1]]:
            continue
        res += minedge[0]
        v = minedge[1]
        used[v] = True
        for e in graph[v]:
            if not used[e[1]]:
                heapq.heappush(edgelist, e)
    return res


n = int(input()) 
graph = [[] for _ in range(n)]
ixy = [[i] + [int(x) for x in input().split()] for i in range(n)]

ixy = sorted(ixy, key=lambda x:(x[1], x[2]))
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d = abs(ixy[i][1] - ixy[i+1][1])
    graph[j].append([d,k])
    graph[k].append([d,j])

ixy = sorted(ixy, key=lambda x:(x[2], x[1]))
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d = abs(ixy[i][2] - ixy[i+1][2])
    graph[j].append([d,k])
    graph[k].append([d,j])

res = myprim_heap(graph, n)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
#import time
import copy
#from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import heapq
#import time

input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

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

    # ノードxのrootノードを見つける
    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
    # xとyが同じグループに属するか判断
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # ノードxが属する木のサイズを返す
    def size(self, x):
        return -self.root[self.find(x)]


def kruskal(v, edge):
    edge.sort(key=lambda x: x[2])
    res=0
    uf = UnionFind(v)
    for e in edge:
        if uf.same(e[0], e[1]):
            continue
        uf.unite(e[0], e[1])
        res+=e[2]
    return res

n = ri()
d1=[rl()+[i] for i in range(n)]
d2=copy.deepcopy(d1)
d1.sort(key=lambda x: x[0])
d2.sort(key=lambda x: x[1])


edge=[]
for i in range(n-1):
    edge.append(( d1[i+1][2], d1[i][2],d1[i+1][0]-d1[i][0]))
    edge.append(( d2[i+1][2], d2[i][2],d2[i+1][1]-d2[i][1]))

print(kruskal(n, edge))

Submission status: Time Limit Exceeded

Solution code:
import sys
#import time
import copy
from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
import heapq
import time

start = time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

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

    # ノードxのrootノードを見つける
    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
    # xとyが同じグループに属するか判断
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # ノードxが属する木のサイズを返す
    def size(self, x):
        return -self.root[self.find(x)]


def kruskal(v, edge):
    edge.sort(key=lambda x: x[2])
    res=0
    uf = UnionFind(v)
    for e in edge:
        if uf.same(e[0], e[1]):
            continue
        if uf.size(0)==v:
            break
        uf.unite(e[0], e[1])
        res+=e[2]
    return res

n = ri()
d1=[rl()+[i] for i in range(n)]
d2=copy.deepcopy(d1)
d1.sort(key=lambda x: x[0])
d2.sort(key=lambda x: x[1])


edge=[]
for i in range(n-1):
    edge.append(( d1[i+1][2], d1[i][2],d1[i+1][0]-d1[i][0]))
    edge.append(( d2[i+1][2], d2[i][2],d2[i+1][1]-d2[i][1]))



print(kruskal(n, edge))

Submission status: Time Limit Exceeded

Solution code:
import sys
#import time
import copy
from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
import heapq
import time

start = time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

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

    # ノードxのrootノードを見つける
    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
    # xとyが同じグループに属するか判断
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # ノードxが属する木のサイズを返す
    def size(self, x):
        return -self.root[self.find(x)]
c=[]

def kruskal(v, edge):
    edge.sort(key=lambda x: x[2])
    res=0
    uf = UnionFind(v)
    for e in edge:
        if uf.same(e[0], e[1]):
            continue
        uf.unite(e[0], e[1])
        res+=e[2]
    return res

n = ri()
d1=[rl()+[i] for i in range(n)]
d2=copy.deepcopy(d1)
d1.sort(key=lambda x: x[0])
d2.sort(key=lambda x: x[1])


edge=[]
for i in range(n-1):
    edge.append(( d1[i+1][2], d1[i][2],d1[i+1][0]-d1[i][0]))
    edge.append(( d2[i+1][2], d2[i][2],d2[i+1][1]-d2[i][1]))



print(kruskal(n, edge))