Problem:


Score : 500 points

Problem Statement

There are N towns on a plane. The i-th town is located at the coordinates (x_i,y_i). There may be more than one town at the same coordinates.

You can build a road between two towns at coordinates (a,b) and (c,d) for a cost of min(|a-c|,|b-d|) yen (the currency of Japan). It is not possible to build other types of roads.

Your objective is to build roads so that it will be possible to travel between every pair of towns by traversing roads. At least how much money is necessary to achieve this?

Constraints

2 ≤ N ≤ 10^5

0 ≤ x_i,y_i ≤ 10^9

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print the minimum necessary amount of money in order to build roads so that it will be possible to travel between every pair of towns by traversing roads.

Sample Input 1

3
1 5
3 9
7 8

Sample Output 1

3

Build a road between Towns 1 and 2, and another between Towns 2 and 3. The total cost is 2+1=3 yen.

Sample Input 2

6
8 3
4 9
12 19
18 1
13 5
7 6

Sample Output 2

8



Sample input:
3
1 5
3 9
7 8


Sample output:
3

Submission status: Wrong Answer

Solution code:
# D
import numpy as np
N = int(input())
X = np.zeros(N, dtype=int)
Y = np.zeros(N, dtype=int)

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

# edges
X_s = np.argsort(X)
Y_s = np.argsort(Y)

edge_list = []
edge_weight = []
for i in range(N-1):
    edge_list.append([X_s[i], X_s[i+1]])
    edge_weight.append(min(abs(X[X_s[i+1]] - X[X_s[i]]), abs(Y[X_s[i+1]] - Y[X_s[i]])))
    edge_list.append([Y_s[i], Y_s[i+1]])
    edge_weight.append(min(abs(X[X_s[i+1]] - X[X_s[i]]), abs(Y[X_s[i+1]] - Y[X_s[i]])))
    
# sort edges
sel = np.argsort(np.array(edge_weight))

res = 0
flg = np.zeros(N)

for s in sel:
    m, n = edge_list[s]
    if flg[m]*flg[n] > 0:
        pass
    else:
        res += edge_weight[s]
        flg[m] = 1
        flg[n] = 1
print(res)

Submission status: Wrong Answer

Solution code:
#定数
INF=1000000

#入力
N=int(input())
xy=[[int(j) for j in input().split()] for i in range(N)]

#x,y座標とその街を、小さい順に並べる
xCity=[[xy[i][0],i] for i in range(N)]
yCity=[[xy[i][1],i] for i in range(N)]
xCity.sort()
yCity.sort()



#連結済みのx,yの列の最大
xIndex=0
yIndex=0

#連結済みの町
linked=[]
if xCity[0][1]==yCity[0][1]:
	linked.append(xCity[0][1])
	N-=1
else:
	linked.append(xCity[0][1])
	linked.append(yCity[0][1])
	N-=2

#所要金額
ans=0

for roop in range(N):
	#連結済みじゃ無い街を指すまで続ける
	while xCity[xIndex][1] in linked:
		xIndex+=1
	while yCity[yIndex][1] in linked:
		yIndex+=1

	#同じ街を見ている場合
	if xCity[xIndex][1]==yCity[yIndex][1]:
		linked.append(xCity[xIndex][1])
		ans+=min(xCity[xIndex][0]-xCity[xIndex-1][0],yCity[yIndex][0]-yCity[yIndex-1][0])
		continue
	#違う街を見ている場合
	xDist=xCity[xIndex][0] - xCity[xIndex-1][0]
	yDist=yCity[yIndex][0] - yCity[yIndex-1][0]
	if xDist<yDist:
		linked.append(xCity[xIndex][1])
		ans+=xDist
	else:
		linked.append(yCity[yIndex][1])
		ans+=yDist

print(ans)

Submission status: Wrong Answer

Solution code:
# D
import numpy as np
N = int(input())
X = np.zeros(N, dtype=int)
Y = np.zeros(N, dtype=int)

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

# edges
X_s = np.argsort(X)
X_t = X[X_s]
Y_s = np.argsort(Y)
Y_t = Y[Y_s]

edge_list = []
edge_weight = []
for i in range(N-1):
    edge_list.append([X_s[i], X_s[i+1]])
    edge_weight.append(X_t[i+1] - X_t[i])
    edge_list.append([Y_s[i], Y_s[i+1]])
    edge_weight.append(Y_t[i+1] - Y_t[i])
    
# sort edges
sel = np.argsort(np.array(edge_weight))

res = 0
flg = np.zeros(N)

for s in sel:
    m, n = edge_list[s]
    if flg[m]*flg[n] > 0:
        pass
    else:
        res += edge_weight[s]
        flg[m] = 1
        flg[n] = 1
print(res)

Submission status: Wrong Answer

Solution code:
n=int(raw_input())
xy=[]
yx=[]
for i in xrange(n):
    x, y = map(int,raw_input().split())
    xy.append([x,y,i])
    yx.append([y,x,i])
xy.sort()
yx.sort()
dist=[]
for i in xrange(n-1):
    a,b,idx1=xy[i]
    c,d,idx2=xy[i+1]
    dist.append([min(abs(a-c),abs(b-d)),idx1,idx2])
for i in xrange(n-1):
    a,b,idx1=yx[i]
    c,d,idx2=yx[i+1]
    dist.append([min(abs(a-c),abs(b-d)),idx1,idx2])
dist.sort()
used=[False]*n
ans=0
for i in xrange(2*(n-1)):
    d,idx1,idx2=dist[i]
    if used[idx1] and used[idx2]:continue
    used[idx1]=True
    used[idx2]=True
    ans+=d
print ans

Submission status: Wrong Answer

Solution code:
class UnionFind:

    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.size = size
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        # 集合の代表を求める
        while self.table[x] >= 0:
            if self.table[self.table[x]] >= 0:
                self.table[x] = self.table[self.table[x]]
            x = self.table[x]
        return x

    def union(self, x, y):
        # 併合
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] >= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
        return self.table[s1]


n = int(input())
uf = UnionFind(n+1)
p = []
q = []
for i in range(n):
    x,y = map(int, input().split())
    p.append((x, y, i))
    q.append((y, x, i))

p.sort()
q.sort()

total = 0
x = 0
y = 0
while x<n-1 and y<n-1:
    while x < n-1 and uf.find(p[x][2]) == uf.find(p[x+1][2]):
        x += 1
    while y < n-1 and uf.find(p[y][2]) == uf.find(p[y+1][2]):
        y += 1
    if x+1 >= n or y+1 >= n:
        break
    if min(abs(p[x+1][0] - p[x][0]), abs(p[x+1][1] - p[x][1])) < min(abs(q[y+1][0] - q[y][0]), abs(q[y+1][1] - q[y][1])):
        total += min(abs(p[x+1][0] - p[x][0]), abs(p[x+1][1] - p[x][1]))
        uf.union(p[x+1][2], p[x][2])
        x += 1
    else:
        total += min(abs(q[y+1][0] - q[y][0]), abs(q[y+1][1] - q[y][1]))
        uf.union(q[y+1][2], q[y][2])
        y += 1
print(total)

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]))
edge.sort(key=lambda x: x[2])
res=0
uf = UnionFind(n)
for e in edge:
    if uf.same(e[0], e[1]):
        continue
    uf.unite(e[0], e[1])
    res+=e[2]
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
N = int(input())
xseq = []
yseq = []
uf = UnionFind(N)
ans = 0

for i in range(N):
    x,y = (int(x) for x in input().split())
    xseq.append((x,i))
    yseq.append((y,i))
xseq.sort()
yseq.sort()
xdiff = [(xseq[i][0]-xseq[i-1][0],(xseq[i][1],xseq[i-1][1])) for i in range(1,N)]
ydiff = [(yseq[i][0]-yseq[i-1][0],(yseq[i][1],yseq[i-1][1])) for i in range(1,N)]
diff = xdiff + ydiff
diff.sort()
d = deque(diff)

for i in range(len(d)):
    temp = d.popleft()
    if uf.find(temp[1][0]) != uf.find(temp[1][1]):
        uf.union(temp[1][0],temp[1][1])
        ans += temp[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
N = int(input())
same = set()
xseq = []
yseq = []
uf = UnionFind(N)
ans = 0

for i in range(N):
    x,y = (int(x) for x in input().split())
    xseq.append((x,i))
    yseq.append((y,i))
xseq.sort()
yseq.sort()
xdiff = [(xseq[i][0]-xseq[i-1][0],(xseq[i][1],xseq[i-1][1])) for i in range(1,N)]
ydiff = [(yseq[i][0]-yseq[i-1][0],(yseq[i][1],yseq[i-1][1])) for i in range(1,N)]
diff = xdiff + ydiff
diff.sort()
d = deque(diff)

for i in range(len(d)):
    temp = d.popleft()
    if uf.find(temp[1][0]) != uf.find(temp[1][1]):
        uf.union(temp[1][0],temp[1][1])
        ans += temp[0]
    if uf.parents.count(-1*N) == 1:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import deque
class UnionFind(): #Union-Find木の実装
    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 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
N = int(input())
same = set()
xseq = []
yseq = []
edge = []
uf = UnionFind(N)
ans = 0

x,y = (int(x) for x in input().split())
same.add((x,y))
xseq.append((x,0))
yseq.append((y,0))
for i in range(1,N):
    x,y = (int(x) for x in input().split())
    if (x,y) not in same:
        same.add((x,y))
        xb = bisect.bisect_left(xseq,(x,i))
        xseq.insert(xb,(x,i))
        if xb == 0:
            edge.append((xseq[1][0]-x,(xseq[1][1],i)))
        elif xb == len(xseq)-1:
            edge.append((x-xseq[-2][0],(xseq[-2][1],i)))
        else:
            edge.append((xseq[xb+1][0]-x,(xseq[xb+1][1],i)))
            edge.append((x-xseq[xb-1][0],(xseq[xb-1][1],i)))
        yb = bisect.bisect_left(yseq,(y,i))
        yseq.insert(yb,(y,i))
        if yb == 0:
            edge.append((yseq[1][0]-y,(yseq[1][1],i)))
        elif yb == len(yseq)-1:
            edge.append((y-yseq[-2][0],(yseq[-2][1],i)))
        else:
            edge.append((yseq[yb+1][0]-y,(yseq[yb+1][1],i)))
            edge.append((y-yseq[yb-1][0],(yseq[yb-1][1],i)))
edge.sort()
d = deque(edge)
for i in range(len(d)):
    temp = d.popleft()
    if uf.find(temp[1][0]) != uf.find(temp[1][1]):
        uf.union(temp[1][0],temp[1][1])
        ans += temp[0]
    if uf.parents.count(-1*N) == 1:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import deque
class UnionFind(): #Union-Find木の実装
    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 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
N = int(input())
same = set()
xseq = []
yseq = []
edge = []
uf = UnionFind(N)
ans = 0

x,y = (int(x) for x in input().split())
same.add((x,y))
xseq.append((x,0))
yseq.append((y,0))
for i in range(1,N):
    x,y = (int(x) for x in input().split())
    if (x,y) not in same:
        same.add((x,y))
        xb = bisect.bisect_left(xseq,(x,i))
        xseq.insert(xb,(x,i))
        if xb == 0:
            edge.append((xseq[1][0]-x,(xseq[1][1],i)))
        elif xb == len(xseq)-1:
            edge.append((x-xseq[-2][0],(xseq[-2][1],i)))
        else:
            edge.append((xseq[xb+1][0]-x,(xseq[xb+1][1],i)))
            edge.append((x-xseq[xb-1][0],(xseq[xb-1][1],i)))
        yb = bisect.bisect_left(yseq,(y,i))
        yseq.insert(yb,(y,i))
        if yb == 0:
            edge.append((yseq[1][0]-y,(yseq[1][1],i)))
        elif yb == len(yseq)-1:
            edge.append((y-yseq[-2][0],(yseq[-2][1],i)))
        else:
            edge.append((yseq[yb+1][0]-y,(yseq[yb+1][1],i)))
            edge.append((y-yseq[yb-1][0],(yseq[yb-1][1],i)))
edge.sort()
d = deque(edge)
for i in range(len(d)):
    temp = d.popleft()
    if uf.find(temp[1][0]) != uf.find(temp[1][1]):
        uf.union(temp[1][0],temp[1][1])
        ans += temp[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import deque
class UnionFind(): #Union-Find木の実装
    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 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
N = int(input())
same = set()
xseq = []
yseq = []
edge = []
uf = UnionFind(N)
ans = 0

x,y = (int(x) for x in input().split())
same.add((x,y))
xseq.append((x,0))
yseq.append((y,0))
for i in range(1,N):
    x,y = (int(x) for x in input().split())
    if (x,y) not in same:
        same.add((x,y))
        xb = bisect.bisect_left(xseq,(x,i))
        xseq.insert(xb,(x,i))
        if xb == 0:
            edge.append((xseq[1][0]-x,(xseq[1][1],i)))
        elif xb == len(xseq)-1:
            edge.append((x-xseq[-2][0],(xseq[-2][1],i)))
        else:
            edge.append((xseq[xb+1][0]-x,(xseq[xb+1][1],i)))
            edge.append((x-xseq[xb-1][0],(xseq[xb-1][1],i)))
        yb = bisect.bisect_left(yseq,(y,i))
        yseq.insert(yb,(y,i))
        if yb == 0:
            edge.append((yseq[1][0]-y,(yseq[1][1],i)))
        elif yb == len(yseq)-1:
            edge.append((y-yseq[-2][0],(yseq[-2][1],i)))
        else:
            edge.append((yseq[yb+1][0]-y,(yseq[yb+1][1],i)))
            edge.append((y-yseq[yb-1][0],(yseq[yb-1][1],i)))
edge.sort()
d = deque([e[0] for e in edge])
for i in range(len(d)):
    temp = d.popleft()
    a,b = edge[i][1][0],edge[i][1][1]
    if uf.find(a) != uf.find(b):
        uf.union(a,b)
        ans += temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *

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 unite(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()}

n=int(input())
X=[[0,0] for i in range(n)]
Y=[[0,0] for i in range(n)]
edge=[[0,0] for i in range(n)]
for i in range(n):
  x,y=map(int,input().split())
  X[i]=[x,i]
  Y[i]=[y,i]
  edge[i]=[x,y]
X.sort()
Y.sort()
hq=[]
heapify(hq)
for i in range(n-1):
  x1,j1=X[i]
  x2,j2=X[i+1]
  y1,k1=Y[i]
  y2,k2=Y[i+1]
  heappush(hq,(x2-x1,j1,j2))
  heappush(hq,(y2-y1,k1,k2))
ans=0
uf=UnionFind(n)
while hq:
  w,s,t=heappop(hq)
  if uf.find(s)!=uf.find(t):
    uf.unite(s,t)
    ans+=w
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
import sys
input=sys.stdin.readline
X=[[-10**10,0]]
Y=[[-10**10,0]]

for i in range(N):
    x,y=map(int,input().split())
    X.append([x,i+1])
    Y.append([y,i+1])
X.append([10**10,N+1])
Y.append([10**10,N+1])
X.sort()
Y.sort()

#print(X,Y)

L=[[]for i in range(N+1)]
for i in range(1,N+1):
    L[X[i][1]].append([X[i][0]-X[i-1][0],X[i-1][1]])
    L[X[i][1]].append([X[i+1][0]-X[i][0],X[i+1][1]])
for i in range(1,N+1):
    L[Y[i][1]].append([Y[i][0]-Y[i-1][0],Y[i-1][1]])
    L[Y[i][1]].append([Y[i+1][0]-Y[i][0],Y[i+1][1]])
#print(L)
C=[1 for i in range(N+2)]
C[0]=0
C[-1]=0
C[1]=0
import heapq
ans=0
Q=L[1]
heapq.heapify(Q)
for i in range(10**6):
    #print(ans,Q)
    #print(C)
    if len(Q)==0:
        break
    q=heapq.heappop(Q)
    if C[q[1]]==0:
        continue
    else:
        C[q[1]]=0
        ans+=q[0]
        for j in range(4):
            if C[L[q[1]][j][1]]==1:
                heapq.heappush(Q,L[q[1]][j])
print(ans)

Submission status: Time Limit Exceeded

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

def same_tree(node_a, node_b):
    if node_a.root() == node_b.root():
        return True

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

def main():
    N = int(input())
    
    nodes = [Node() for i in range(N)]

    # 各町の座標をタプル(i, x, y)に入れて配列に格納
    xs = []
    ys = []
    for i in range(N):
        x, y = map(int, input().split())
        bisect.insort_left(xs, (x, i))
        bisect.insort_left(ys, (y, i))

    # 使う可能性のある辺のみを取り出す
    edges = []
    for i in range(1, N):
        bisect.insort_left(edges, (xs[i][0] - xs[i-1][0], xs[i-1][1], xs[i][1]))
        bisect.insort_left(edges, (ys[i][0] - ys[i-1][0], ys[i-1][1], ys[i][1]))

    # クラスカル法
    ans = 0
    for (cost, a, b) in edges:
        if not same_tree(nodes[a], nodes[b]):
            unite(nodes[a], nodes[b])
            ans += cost
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

class Node:
    def __init__(self, id):
        self.id = id
        self.check = False
        self.link = []
        self.cost = []
    
    def __lt__(self, other):
        return self.id < other.id

def main():
    N = int(input())
    
    nodes = [Node(i) for i in range(N)]

    xy = []
    for i in range(N):
        x, y = map(int, input().split())
        xy.append((i, x, y))
    
    for t in range(2):
        if t == 0:
            xy = sorted(xy, key=lambda x: x[1])# x昇順
        else:
            xy = sorted(xy, key=lambda x: x[2])# y昇順
        p_n, p_x, p_y = xy[0]
        for i in range(1, N):
            n, x, y = xy[i]
            if t == 0:
                cost = abs(x - p_x)# x
            else:
                cost = abs(y - p_y)# y
            nodes[p_n].link.append(nodes[n])
            nodes[p_n].cost.append(cost)
            nodes[n].link.append(nodes[p_n])
            nodes[n].cost.append(cost)
            p_n, p_x, p_y = n, x, y
    q = []
    ans = 0
    heapq.heappush(q, (0, nodes[0]))# edge_cost, node
    while len(q) > 0:
        edge_cost, node = heapq.heappop(q)
        if node.check:
            continue
        node.check = True
        ans += edge_cost
        for i, next_node in enumerate(node.link):
            if not next_node.check:
                heapq.heappush(q, (node.cost[i], next_node))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
n=int(input())
s=[]
for i in range(n):
    s.append(list(map(int,input().split()))+[i])
x=sorted(s,key=lambda x:x[0])
y=sorted(s,key=lambda x:x[1])
t=[[]for i in range(n)]
for i in range(1,n):
    t[x[i-1][2]].append([x[i][0]-x[i-1][0],x[i][2]])
    t[x[i][2]].append([x[i][0]-x[i-1][0],x[i-1][2]])
    t[y[i-1][2]].append([y[i][1]-y[i-1][1],y[i][2]])
    t[y[i][2]].append([y[i][1]-y[i-1][1],y[i-1][2]])
s=[True]*n
s[0]=False
a=0
h=t[0]
heapify(h)
while h:
    p,q=heappop(h)
    if s[q]:
        s[q]=False
        a+=p
        for i,j in t[q]:
            if s[j]:
                heappush(h,[i,j])
print(a)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush
n=int(input())
s=[]
for i in range(n):
    s.append(list(map(int,input().split()))+[i])
x=sorted(s,key=lambda x:x[0])
y=sorted(s,key=lambda x:x[1])
t=[[]for i in range(n)]
for i in range(1,n):
    t[x[i-1][2]].append([x[i][0]-x[i-1][0],x[i][2]])
    t[x[i][2]].append([x[i][0]-x[i-1][0],x[i-1][2]])
    t[y[i-1][2]].append([y[i][1]-y[i-1][1],y[i][2]])
    t[y[i][2]].append([y[i][1]-y[i-1][1],y[i-1][2]])
s=[True]*n
s[0],h=False,[]
a=0
for i in t[0]:
    heappush(h,i)
while h:
    p,q=heappop(h)
    if s[q]:
        s[q]=False
        a+=p
        for i,j in t[q]:
            if s[j]:
                heappush(h,[i,j])
print(a)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush
n=int(input())
s=[]
for i in range(n):
    a,b=map(int,input().split())
    s.append([a,b,i])
x=sorted(s)
y=sorted(s,key=lambda x:x[1])
t=[[]for i in range(n)]
for i in range(1,n):
    t[x[i-1][2]].append([x[i][0]-x[i-1][0],x[i][2]])
    t[x[i][2]].append([x[i][0]-x[i-1][0],x[i-1][2]])
    t[y[i-1][2]].append([y[i][1]-y[i-1][1],y[i][2]])
    t[y[i][2]].append([y[i][1]-y[i-1][1],y[i-1][2]])
s=[1]*n
s[0],h=0,[]
a=0
for i in t[0]:
    heappush(h,i)
while h:
    p,q=heappop(h)
    if s[q]:
        s[q]=0
        a+=p
        for i in t[q]:
            heappush(h,i)
print(a)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
n=int(input())
s=[]
for i in range(n):
    a,b=map(int,input().split())
    s.append([a,b,i])
x=sorted(s)
y=sorted(s,key=lambda x:x[1])
t=[[]for i in range(n)]
for i in range(1,n):
    t[x[i-1][2]].append([x[i][0]-x[i-1][0],x[i][2]])
    t[x[i][2]].append([x[i][0]-x[i-1][0],x[i-1][2]])
    t[y[i-1][2]].append([y[i][1]-y[i-1][1],y[i][2]])
    t[y[i][2]].append([y[i][1]-y[i-1][1],y[i-1][2]])
s=[1]*n
s[0],h=0,[]
a=0
for i in t[0]:
    heappush(h,i)
while h:
    p,q=heappop(h)
    if s[q]:
        s[q]=0
        a+=p
        for i in t[q]:
            heappush(h,i)
print(a)

Submission status: Time Limit Exceeded

Solution code:
def getlist():
	return list(map(int, input().split()))
import sys
input = sys.stdin.readline

from heapq import heappop, heappush

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

class Kruskal:
    def __init__(self, Q, n):
        self.uf = UnionFind(n)
        self.cost = 0
        self.Q = Q
        while self.Q:
            w, u, v = heappop(self.Q)
            if self.uf.same_check(u, v) != True:
                self.uf.union(u, v)
                self.cost += w

#受け取りと処理
N = int(input())
X = []
Y = []
for i in range(N):
	x, y = getlist()
	X.append([x, i])
	Y.append([y, i])

X = sorted(X)
Y = sorted(Y)

#辺追加
Q = []
wx = X[0][0]
wy = Y[0][0]
xx = X[0][1]
yy = Y[0][1]
for i in range(N - 1):
	Wx = X[i + 1][0]
	Xx = X[i + 1][1]
	Wy = Y[i + 1][0]
	Yy = Y[i + 1][1]
	heappush(Q, [Wx - wx, Xx, xx])
	heappush(Q, [Wy - wy, Yy, yy])
	wx = Wx
	wy = Wy
	xx = Xx
	yy = Yy

#全域木
Km = Kruskal(Q, N)
print(Km.cost)

Submission status: Time Limit Exceeded

Solution code:
def getlist():
	return list(map(int, input().split()))
import sys
input = sys.stdin.readline

from heapq import heappop, heappush

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

class Kruskal:
    def __init__(self, Q, n):
        self.uf = UnionFind(n)
        self.cost = 0
        self.Q = Q
        while self.Q:
            w, u, v = heappop(self.Q)
            if self.uf.same_check(u, v) != True:
                self.uf.union(u, v)
                self.cost += w

#受け取りと処理
N = int(input())
X = []
Y = []
for i in range(N):
	x, y = getlist()
	X.append([x, i])
	Y.append([y, i])

X = sorted(X)
Y = sorted(Y)

#辺追加
Q = []
for i in range(N - 1):
	w, a, b = X[i + 1][0] - X[i][0], X[i][1], X[i + 1][1]
	heappush(Q, [w, a, b])
	w, a, b = Y[i + 1][0] - Y[i][0], Y[i][1], Y[i + 1][1]
	heappush(Q, [w, a, b])

#全域木
Km = Kruskal(Q, N)
print(Km.cost)

Submission status: Time Limit Exceeded

Solution code:
def getlist():
	return list(map(int, input().split()))

from heapq import heappop, heappush

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

class Kruskal:
    def __init__(self, Q, n):
        self.uf = UnionFind(n)
        self.cost = 0
        self.Q = Q
        while self.Q:
            w, u, v = heappop(self.Q)
            if self.uf.same_check(u, v) != True:
                self.uf.union(u, v)
                self.cost += w

#受け取りと処理
N = int(input())
X = []
Y = []
for i in range(N):
	x, y = getlist()
	X.append([x, i])
	Y.append([y, i])

X = sorted(X)
Y = sorted(Y)

#辺追加
Q = []
for i in range(N - 1):
	w, a, b = X[i + 1][0] - X[i][0], X[i][1], X[i + 1][1]
	heappush(Q, [w, a, b])
	w, a, b = Y[i + 1][0] - Y[i][0], Y[i][1], Y[i + 1][1]
	heappush(Q, [w, a, b])

#全域木
Km = Kruskal(Q, N)
print(Km.cost)

Submission status: Time Limit Exceeded

Solution code:

import heapq

def prime_method():
    start = graph[0]
    not_went = [True] * n  # n個の点に行ったかという話
    edges = []
    for e in start:
        heapq.heappush(edges,e)
    not_went[0] = False
    cost = 0
    while len(edges) != 0:
        minedge = heapq.heappop(edges)
        if not not_went[minedge[1]]:
            continue
        v = minedge[1]
        gv = graph[v]
        not_went[v] = False
        for temp in gv:
            if not_went[temp[1]]:  # その頂点に行ってなければ
                heapq.heappush(edges, temp)
        cost += minedge[0]
    return cost
    # a[1] = [[2,3],[5,11]] → 点1からコスト2で頂点3に行ける辺、点1からコスト5で頂点11に行ける辺がある


n = int(input())
# cities = [(a, b, i) for i, (a, b) in enumerate([tuple(map(int, input().split())) for _ in range(N)])]
cities = []
for i in range(n):
    cities.append(tuple(map(int,input().split()))+tuple([i]))

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


citiesX=sorted(cities,key=lambda x:x[0])
citiesY=sorted(cities,key=lambda x:x[1])

for i in range(n-1):
    graph[citiesX[i][2]].append([(citiesX[i+1][0] - citiesX[i][0]),citiesX[i+1][2]])
    graph[citiesX[i+1][2]].append([(citiesX[i+1][0] - citiesX[i][0]),citiesX[i][2]])
    graph[citiesY[i][2]].append([(citiesY[i+1][1] - citiesY[i][1]),citiesY[i+1][2]])
    graph[citiesY[i+1][2]].append([(citiesY[i+1][1] - citiesY[i][1]),citiesY[i][2]])
print(prime_method())