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:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#N=int(input())
#X,Y=map(int,input().split()))
#S=list(map(int,input().split()))
#S=[list(map(int,input().split())) for i in range(N)]

N=int(input())
XY=[list(map(int,input().split()))+[i] for i in range(N)]
Xsort=sorted([[i[0],i[2]] for i in XY],key=lambda x:x[0])
Ysort=sorted([[i[1],i[2]] for i in XY],key=lambda x:x[0])
Nidxlst=[[0,0] for i in range(N)]
for i in range(N):
    idx=Xsort[i][1]
    Nidxlst[idx][0]=i
    idx=Ysort[i][1]
    Nidxlst[idx][1]=i



value=0
x,y=Nidxlst[0]
ittenai=set([i for i in range(1,N)])

stack=[]
heapify(stack)
setI=set()
dic={}

def main(x,y):
    if x>0:
        m=Xsort[x][0]-Xsort[x-1][0]

        a=Xsort[x-1][1]
        if a in ittenai:
            heappush(stack,m)
            if m in dic :

                dic[m].append(a)
            else:
                dic.update({m:[a]})
    if x<N-1:
        m=Xsort[x+1][0]-Xsort[x][0]
        a=Xsort[x+1][1]
        if a in ittenai:
            heappush(stack,m)
            if m in dic :

                dic[m].append(a)
            else:
                dic.update({m:[a]})
    if y>0:
        m=Ysort[y][0]-Ysort[y-1][0]
        a=Ysort[y-1][1]
        if a in ittenai:
            heappush(stack,m)
            if m in dic :

                dic[m].append(a)
            else:
                dic.update({m:[a]})
    if y<N-1:
        m=Ysort[y+1][0]-Ysort[y][0]
        a=Ysort[y+1][1]
        if a in ittenai:
            heappush(stack,m)
            if m in dic :

                dic[m].append(a)
            else:
                dic.update({m:[a]})
main(x,y)
idle=10**9+1
value=0
while ittenai:
    m=heappop(stack)
    if dic[m]:
        a=dic[m].pop()
        if a in ittenai:
            x,y=Nidxlst[a]
            main(x,y)
            ittenai.remove(a)
            value+=m

print(value)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush


class UnionFind(object):

    def __init__(self, N):
        self.tree = [i for i in range(N)]
        self.rank = [0] * (N + 1)
        self.size = [1] * N  # 頂点iの属する連結成分の大きさ

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

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

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

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

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


def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))


N = I()
X = [None] * N
Y = [None] * N
for i in range(N):
    x, y = MI()
    X[i] = (x, i, x, y)
    Y[i] = (y, i, x, y)
X.sort()
Y.sort()

# ある頂点vから最小全域木に含まれる点をたどった先の頂点は、x軸方向で最も近いかy軸方向で最もvから近いはず
q = list()
for i in range(N - 1):
    for axis in [X, Y]:
        _, t0, x0, y0 = axis[i]
        _, t1, x1, y1 = axis[i + 1]
        cost = min(abs(x1 - x0), abs(y1 - y0))
        heappush(q, (cost, t0, t1))

# Kruskal法 := 最小コストの辺から順に見て、新たな頂点が仲間に入るなら加える
uf = UnionFind(N)
ans = 0
while len(q) > 0:
    cost, t0, t1 = heappop(q)
    if not uf.has_same_parent(t0, t1):
        uf.unite(t0, t1)
        ans += cost
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#16:15
n = int(input())
xyi = []
for i in range(n):
  xyi.append(list(map(int,input().split())) + [i])
xyi.sort()
road = [[] for _ in range(n)]
for j in range(n-1):
  z1 = xyi[j][2]
  z2 = xyi[j+1][2]
  d  = xyi[j+1][0] - xyi[j][0]
  road[z1].append([d,z2])
  road[z2].append([d,z1])
xyi.sort(key = lambda x: x[1])
for j in range(n-1):
  z1 = xyi[j][2]
  z2 = xyi[j+1][2]
  d  = xyi[j+1][1] - xyi[j][1]
  road[z1].append([d,z2])
  road[z2].append([d,z1])
pre = [i for i in range(n)]
ans = 0
seen = [0 for _ in range(n)]
seen[0] = 1
now = road[0]
import heapq
heapq.heapify(now)
ans = 0
while now:
  d,z = heapq.heappop(now)
  if seen[z] == 1:
    continue
  seen[z] = 1
  ans += d
  for x in road[z]:
    if seen[x[1]] == 0:
      heapq.heappush(now,x)
#print(seen)
#print(road)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#16:15
n = int(input())
xyi = []
for i in range(n):
  xyi.append(list(map(int,input().split())) + [i])
xyi.sort()
road = []
for j in range(n-1):
  road.append([xyi[j+1][0]-xyi[j][0],xyi[j][2],xyi[j+1][2]])
xyi.sort(key = lambda x: x[1])
for j in range(n-1):
  road.append([xyi[j+1][1]-xyi[j][1],xyi[j][2],xyi[j+1][2]])
road.sort()
pre = [i for i in range(n)]
ans = 0
for k in range(2*n-2):
  d,I,J = road[k]
  ii = []
  ic = 0
  jj = []
  jc = 0
  while pre[I] != I:
    ii.append(I)
    ic += 1
    I = pre[I]
  while pre[J] != J:
    jj.append(J)
    jc += 1
    J = pre[J]
  if I != J:
    ans += d
    if ic >= jc:
      for Js in jj:
        pre[Js] = I
      pre[J] = I
    else:
      for Is in ii:
        pre[Is] = J
      pre[I] = J
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#16:15
n = int(input())
xyi = []
for i in range(n):
  xyi.append(list(map(int,input().split())) + [i])
xyi.sort()
road = []
for j in range(n-1):
  road.append([xyi[j+1][0]-xyi[j][0],xyi[j][2],xyi[j+1][2]])
xyi.sort(key = lambda x: x[1])
for j in range(n-1):
  road.append([xyi[j+1][1]-xyi[j][1],xyi[j][2],xyi[j+1][2]])
road.sort()
pre = [i for i in range(n)]
ans = 0
for k in range(2*n-2):
  d,I,J = road[k]
  while pre[I] != I:
    I = pre[I]
  while pre[J] != J:
    J = pre[J]
  if I != J:
    pre[J] = I
    ans += d
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush


class UnionFind(object):

    def __init__(self, N):
        self.tree = [i for i in range(N)]
        self.rank = [0] * (N + 1)
        self.size = [1] * N  # 頂点iの属する連結成分の大きさ

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

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

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

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

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


def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))


N = I()
X = [None] * N
Y = [None] * N
for i in range(N):
    x, y = MI()
    X[i] = (x, i, x, y)
    Y[i] = (y, i, x, y)
X.sort()
Y.sort()

# ある頂点vから最小全域木に含まれる点をたどった先の頂点は、x軸方向で最も近いかy軸方向で最もvから近いはず
q = list()
for i in range(N - 1):
    for axis in [X, Y]:
        _, t0, x0, y0 = axis[i]
        _, t1, x1, y1 = axis[i + 1]
        cost = min(abs(x1 - x0), abs(y1 - y0))
        heappush(q, (cost, t0, t1))

uf = UnionFind(N)
ans = 0
while len(q) > 0:
    cost, t0, t1 = heappop(q)
    if not uf.has_same_parent(t0, t1):
        uf.unite(t0, t1)
        ans += cost
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1 
  def same(self, x, y):
    return self.find(x)==self.find(y)
  
N = int(input())
X = []
Y = []
for i in range(N):
  x, y = map(int, input().split())
  X += [(x,y,i)]
  Y += [(x,y,i)]
X.sort()
Y.sort(key=lambda x:x[1])
hq = []
for i in range(N-1):
  x1, y1, i1 = X[i]
  x2, y2, i2 = X[i+1]
  heappush(hq, (x2-x1,i1,i2))
  x1, y1, i1 = Y[i]
  x2, y2, i2 = Y[i+1]
  heappush(hq, (y2-y1,i1,i2))

u  = UnionFind(N)
cnt = 1
ans = 0
while cnt<N:
  c, i1, i2 = heappop(hq)
  if u.same(i1,i2):
    continue
  ans += c
  cnt += 1
  u.unit(i1,i2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.size = [1]*n
    self.rank = [0]*n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      self.size[y] += self.size[x]
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
      self.size[x] += self.size[y]
    else:
      self.par[y] = x
      self.size[x] += self.size[y]
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  
  def count(self, x):
    return self.size[self.find(x)]
N = int(input())
X = []
Y = []
for i in range(N):
  x, y = map(int, input().split())
  X += [(x,y,i)]
  Y += [(x,y,i)]
X.sort()
Y.sort(key=lambda x:x[1])
hq = []
for i in range(N-1):
  x1, y1, i1 = X[i]
  x2, y2, i2 = X[i+1]
  heappush(hq, (x2-x1,i1,i2))
  x1, y1, i1 = Y[i]
  x2, y2, i2 = Y[i+1]
  heappush(hq, (y2-y1,i1,i2))

u  = UnionFind(N)
cnt = 1
ans = 0
while cnt<N:
  c, i1, i2 = heappop(hq)
  if u.same(i1,i2):
    continue
  ans += c
  cnt += 1
  u.unit(i1,i2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def find(i):
    j = i
    while j!=T[j][0]:
        j = T[j][0]
    k = i
    while k!=T[k][0]:
        m = k
        k = T[k][0]
        T[m][0] = j
#     while j!=T[j][0]:
#         k = j
#         j = T[j][0]
#         T[k][0] = i
#         T[i][1] = max(T[i][1],T[k][1],1)
#     T[i][0] = j
#     if T[i][1]==T[j][1]:
#         T[j][1] += 1
#     elif T[i][1]>T[j][1]:
#         T[j][1] = T[i][1]
    return j
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        if T[rt0][1]==T[rt1][1]:
            T[rt0][1] += 1
        return rt0
    else:
        T[rt0][0] = rt1
        return rt1
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
distX = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    a,i = A[j]
    if j>=curR:
        k = j+1
        while k<N and A[k][0]==a:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = A[curR][0]-a
        distX[i].append((d,A[curR][1]))
    if curL-1>=0:
        d = a-A[curL-1][0]
        distX[i].append((d,A[curL-1][1]))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    b,i = B[j]
    if j>=curR:
        k = j+1
        while k<N and B[k][0]==b:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = B[curR][0]-b
        distY[i].append((d,B[curR][1]))
    if curL-1>=0:
        d = b-B[curL-1][0]
        distY[i].append((d,B[curL-1][1]))
T = {i:[i,0] for i in range(N)}
for j in range(1,N):
    if A[j][0]==A[j-1][0]:
        union(find(A[j-1][1]),find(A[j][1]))
for j in range(1,N):
    if B[j][0]==B[j-1][0]:
        rt = find(B[j-1][1])
        rt0 = find(B[j][1])
        if rt!=rt0:
            union(rt,rt0)
D = []
for i in range(N):
    for d,j in distX[i]:
        D.append((d,i,j))
    for d,j in distY[i]:
        D.append((d,i,j))
D = sorted(D,key=lambda x:x[0])
cnt = 0
for d,i,j in D:
    rt = find(i)
    rt0 = find(j)
    if rt!= rt0:
        cnt += d
        union(rt,rt0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def find(i):
    j = i
    while j!=T[j][0]:
        k = j
        j = T[j][0]
        T[k][0] = i
        T[i][1] = max(T[i][1],T[k][1],1)
    T[i][0] = j
    if T[i][1]==T[j][1]:
        T[j][1] += 1
    elif T[i][1]>T[j][1]:
        T[j][1] = T[i][1]
    return j
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        if T[rt0][1]==T[rt1][1]:
            T[rt0][1] += 1
        return rt0
    else:
        T[rt0][0] = rt1
        return rt1
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
distX = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    a,i = A[j]
    if j>=curR:
        k = j+1
        while k<N and A[k][0]==a:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = A[curR][0]-a
        distX[i].append((d,A[curR][1]))
    if curL-1>=0:
        d = a-A[curL-1][0]
        distX[i].append((d,A[curL-1][1]))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    b,i = B[j]
    if j>=curR:
        k = j+1
        while k<N and B[k][0]==b:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = B[curR][0]-b
        distY[i].append((d,B[curR][1]))
    if curL-1>=0:
        d = b-B[curL-1][0]
        distY[i].append((d,B[curL-1][1]))
T = {i:[i,0] for i in range(N)}
for j in range(1,N):
    if A[j][0]==A[j-1][0]:
        union(find(A[j-1][1]),find(A[j][1]))
for j in range(1,N):
    if B[j][0]==B[j-1][0]:
        rt = find(B[j-1][1])
        rt0 = find(B[j][1])
        if rt!=rt0:
            union(rt,rt0)
D = []
for i in range(N):
    for d,j in distX[i]:
        D.append((d,i,j))
    for d,j in distY[i]:
        D.append((d,i,j))
D = sorted(D,key=lambda x:x[0])
cnt = 0
for d,i,j in D:
    rt = find(i)
    rt0 = find(j)
    if rt!= rt0:
        cnt += d
        union(rt,rt0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def find(i):
    j = i
    while j!=T[j][0]:
        k = j
        j = T[j][0]
        T[k][0] = i
        T[i][1] = max(T[i][1],T[k][1],1)
    T[i][0] = j
    return j
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        if T[rt0][1]==T[rt1][1]:
            T[rt0][1] += 1
        return rt0
    else:
        T[rt0][0] = rt1
        return rt1
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
distX = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    a,i = A[j]
    if j>=curR:
        k = j+1
        while k<N and A[k][0]==a:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = A[curR][0]-a
        distX[i].append((d,A[curR][1]))
    if curL-1>=0:
        d = a-A[curL-1][0]
        distX[i].append((d,A[curL-1][1]))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    b,i = B[j]
    if j>=curR:
        k = j+1
        while k<N and B[k][0]==b:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = B[curR][0]-b
        distY[i].append((d,B[curR][1]))
    if curL-1>=0:
        d = b-B[curL-1][0]
        distY[i].append((d,B[curL-1][1]))
T = {i:[i,0] for i in range(N)}
for j in range(1,N):
    if A[j][0]==A[j-1][0]:
        union(find(A[j-1][1]),find(A[j][1]))
for j in range(1,N):
    if B[j][0]==B[j-1][0]:
        rt = find(B[j-1][1])
        rt0 = find(B[j][1])
        if rt!=rt0:
            union(rt,rt0)
D = []
for i in range(N):
    for d,j in distX[i]:
        D.append((d,i,j))
    for d,j in distY[i]:
        D.append((d,i,j))
D = sorted(D,key=lambda x:x[0])
cnt = 0
for d,i,j in D:
    rt = find(i)
    rt0 = find(j)
    if rt!= rt0:
        cnt += d
        union(rt,rt0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def find(i):
    j = i
    while j!=T[j][0]:
        k = j
        j = T[j][0]
        T[k][0] = i
    T[i][0] = j
    return j
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        if T[rt0][1]==T[rt1][1]:
            T[rt0][1] += 1
        return rt0
    else:
        T[rt0][0] = rt1
        return rt1
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
distX = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    a,i = A[j]
    if j>=curR:
        k = j+1
        while k<N and A[k][0]==a:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = A[curR][0]-a
        distX[i].append((d,A[curR][1]))
    if curL-1>=0:
        d = a-A[curL-1][0]
        distX[i].append((d,A[curL-1][1]))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    b,i = B[j]
    if j>=curR:
        k = j+1
        while k<N and B[k][0]==b:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = B[curR][0]-b
        distY[i].append((d,B[curR][1]))
    if curL-1>=0:
        d = b-B[curL-1][0]
        distY[i].append((d,B[curL-1][1]))
T = {i:[i,0] for i in range(N)}
for j in range(1,N):
    if A[j][0]==A[j-1][0]:
        union(find(A[j-1][1]),find(A[j][1]))
for j in range(1,N):
    if B[j][0]==B[j-1][0]:
        rt = find(B[j-1][1])
        rt0 = find(B[j][1])
        if rt!=rt0:
            union(rt,rt0)
D = []
for i in range(N):
    for d,j in distX[i]:
        D.append((d,i,j))
    for d,j in distY[i]:
        D.append((d,i,j))
D = sorted(D,key=lambda x:x[0])
cnt = 0
for d,i,j in D:
    rt = find(i)
    rt0 = find(j)
    if rt!= rt0:
        cnt += d
        union(rt,rt0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def find(i):
    j = i
    while j!=T[j][0]:
        j = T[j][0]
    T[i][0] = j
#     k = i
#     while k!=T[k][0]:
#         k,T[k][0] = T[k][0],j
    return j
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        if T[rt0][1]==T[rt1][1]:
            T[rt0][1] += 1
        return rt0
    else:
        T[rt0][0] = rt1
        return rt1
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
distX = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    a,i = A[j]
    if j>=curR:
        k = j+1
        while k<N and A[k][0]==a:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = A[curR][0]-a
        distX[i].append((d,A[curR][1]))
    if curL-1>=0:
        d = a-A[curL-1][0]
        distX[i].append((d,A[curL-1][1]))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    b,i = B[j]
    if j>=curR:
        k = j+1
        while k<N and B[k][0]==b:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = B[curR][0]-b
        distY[i].append((d,B[curR][1]))
    if curL-1>=0:
        d = b-B[curL-1][0]
        distY[i].append((d,B[curL-1][1]))
T = {i:[i,0] for i in range(N)}
for j in range(1,N):
    if A[j][0]==A[j-1][0]:
        union(find(A[j-1][1]),find(A[j][1]))
for j in range(1,N):
    if B[j][0]==B[j-1][0]:
        rt = find(B[j-1][1])
        rt0 = find(B[j][1])
        if rt!=rt0:
            union(rt,rt0)
D = []
for i in range(N):
    for d,j in distX[i]:
        D.append((d,i,j))
    for d,j in distY[i]:
        D.append((d,i,j))
D = sorted(D,key=lambda x:x[0])
cnt = 0
for d,i,j in D:
    rt = find(i)
    rt0 = find(j)
    if rt!= rt0:
        cnt += d
        union(rt,rt0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def find(i):
    j = i
    while j!=T[j][0]:
        j = T[j][0]
    T[i][0] = j
    return j
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        if T[rt0][1]==T[rt1][1]:
            T[rt0][1] += 1
        return rt0
    else:
        T[rt0][0] = rt1
        return rt1
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
distX = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    a,i = A[j]
    if j>=curR:
        k = j+1
        while k<N and A[k][0]==a:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = A[curR][0]-a
        distX[i].append((d,A[curR][1]))
    if curL-1>=0:
        d = a-A[curL-1][0]
        distX[i].append((d,A[curL-1][1]))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    b,i = B[j]
    if j>=curR:
        k = j+1
        while k<N and B[k][0]==b:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = B[curR][0]-b
        distY[i].append((d,B[curR][1]))
    if curL-1>=0:
        d = b-B[curL-1][0]
        distY[i].append((d,B[curL-1][1]))
T = {i:[i,0] for i in range(N)}
for j in range(1,N):
    if A[j][0]==A[j-1][0]:
        union(find(A[j-1][1]),find(A[j][1]))
for j in range(1,N):
    if B[j][0]==B[j-1][0]:
        rt = find(B[j-1][1])
        rt0 = find(B[j][1])
        if rt!=rt0:
            union(rt,rt0)
D = []
for i in range(N):
    for d,j in distX[i]:
        D.append((d,i,j))
    for d,j in distY[i]:
        D.append((d,i,j))
D = sorted(D,key=lambda x:x[0])
cnt = 0
for d,i,j in D:
    rt = find(i)
    rt0 = find(j)
    if rt!= rt0:
        cnt += d
        union(rt,rt0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def find(i):
    j = i
    while j!=T[j][0]:
        j = T[j][0]
    T[i][0] = j
    return j
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        T[rt0][1] += T[rt1][1]
        return rt0
    else:
        T[rt0][0] = rt1
        T[rt1][1] += T[rt0][1]
        return rt1
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
distX = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    a,i = A[j]
    if j>=curR:
        k = j+1
        while k<N and A[k][0]==a:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = A[curR][0]-a
        distX[i].append((d,A[curR][1]))
    if curL-1>=0:
        d = a-A[curL-1][0]
        distX[i].append((d,A[curL-1][1]))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    b,i = B[j]
    if j>=curR:
        k = j+1
        while k<N and B[k][0]==b:
            k += 1
        curR = k
        curL = j
    if curR<N:
        d = B[curR][0]-b
        distY[i].append((d,B[curR][1]))
    if curL-1>=0:
        d = b-B[curL-1][0]
        distY[i].append((d,B[curL-1][1]))
T = {i:[i,1] for i in range(N)}
for j in range(1,N):
    if A[j][0]==A[j-1][0]:
        union(find(A[j-1][1]),find(A[j][1]))
        find(A[j][1])
        find(A[j-1][1])
for j in range(1,N):
    if B[j][0]==B[j-1][0]:
        rt = find(B[j-1][1])
        rt0 = find(B[j][1])
        if rt!=rt0:
            union(rt,rt0)
            find(B[j][1])
            find(B[j-1][1])
D = []
for i in range(N):
    for d,j in distX[i]:
        D.append((d,i,j))
    for d,j in distY[i]:
        D.append((d,i,j))
D = sorted(D,key=lambda x:x[0])
cnt = 0
for d,i,j in D:
    rt = find(i)
    rt0 = find(j)
    if rt!= rt0:
        cnt += d
        union(rt,rt0)
        find(i)
        find(j)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def find(i):
    j = i
    while j!=T[j][0]:
        j = T[j][0]
    T[i][0] = j
    return j
def union(rt0,rt1):
    if rt0>rt1:
        rt0,rt1 = rt1,rt0
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        T[rt0][1] += T[rt1][1]
        return rt0
    else:
        T[rt0][0] = rt1
        T[rt1][1] += T[rt0][1]
        return rt1
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
distX = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    a,i = A[j]
    if j>=curR:
        k = j+1
        while k<N and A[k][0]==a:
            k += 1
        curR = k
        k = curL+1
        while A[k][0]!=a:
            k += 1
        curL = k
    if curR<N:
        d = A[curR][0]-a
        distX[i].append((d,A[curR][1]))
    if curL-1>=0:
        d = a-A[curL-1][0]
        distX[i].append((d,A[curL-1][1]))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    b,i = B[j]
    if j>=curR:
        k = j+1
        while k<N and B[k][0]==b:
            k += 1
        curR = k
        k = curL+1
        while B[k][0]!=b:
            k += 1
        curL = k
    if curR<N:
        d = B[curR][0]-b
        distY[i].append((d,B[curR][1]))
    if curL-1>=0:
        d = b-B[curL-1][0]
        distY[i].append((d,B[curL-1][1]))
T = {i:[i,1] for i in range(N)}
for j in range(1,N):
    if A[j][0]==A[j-1][0]:
        union(find(A[j-1][1]),find(A[j][1]))
        find(A[j][1])
for j in range(1,N):
    if B[j][0]==B[j-1][0]:
        rt = find(B[j-1][1])
        rt0 = find(B[j][1])
        if rt!=rt0:
            union(rt,rt0)
            find(B[j][1])
            find(B[j-1][1])
D = []
for i in range(N):
    for d,j in distX[i]:
        D.append((d,i,j))
    for d,j in distY[i]:
        D.append((d,i,j))
D = sorted(D,key=lambda x:x[0])
cnt = 0
for d,i,j in D:
    rt = find(i)
    rt0 = find(j)
    if rt!= rt0:
        cnt += d
        union(rt,rt0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def find(i):
    j = i
    while j!=T[j][0]:
        j = T[j][0]
    T[i][0] = j
    return j
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        T[rt0][1] += T[rt1][1]
        return rt0
    else:
        T[rt0][0] = rt1
        T[rt1][1] += T[rt0][1]
        return rt1
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
distX = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    a,i = A[j]
    if j>=curR:
        k = j+1
        while k<N and A[k][0]==a:
            k += 1
        curR = k
        k = curL+1
        while A[k][0]!=a:
            k += 1
        curL = k
    if curR<N:
        d = A[curR][0]-a
        distX[i].append((d,A[curR][1]))
    if curL-1>=0:
        d = a-A[curL-1][0]
        distX[i].append((d,A[curL-1][1]))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    b,i = B[j]
    if j>=curR:
        k = j+1
        while k<N and B[k][0]==b:
            k += 1
        curR = k
        k = curL+1
        while B[k][0]!=b:
            k += 1
        curL = k
    if curR<N:
        d = B[curR][0]-b
        distY[i].append((d,B[curR][1]))
    if curL-1>=0:
        d = b-B[curL-1][0]
        distY[i].append((d,B[curL-1][1]))
T = {i:[i,1] for i in range(N)}
for j in range(1,N):
    if A[j][0]==A[j-1][0]:
        union(find(A[j-1][1]),find(A[j][1]))
        find(A[j][1])
for j in range(1,N):
    if B[j][0]==B[j-1][0]:
        rt = find(B[j-1][1])
        rt0 = find(B[j][1])
        if rt!=rt0:
            union(rt,rt0)
            find(B[j][1])
            find(B[j-1][1])
D = []
for i in range(N):
    for d,j in distX[i]:
        D.append((d,i,j))
    for d,j in distY[i]:
        D.append((d,i,j))
D = sorted(D,key=lambda x:x[0])
cnt = 0
for d,i,j in D:
    rt = find(i)
    rt0 = find(j)
    if rt!= rt0:
        cnt += d
        union(rt,rt0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def find(i):
    j = i
    while j!=T[j][0]:
        j = T[j][0]
    T[i][0] = j
    return j
def union(rt0,rt1):
    if T[rt0][1]>=T[rt1][1]:
        T[rt1][0] = rt0
        T[rt0][1] += T[rt1][1]
        return rt0
    else:
        T[rt0][0] = rt1
        T[rt1][1] += T[rt0][1]
        return rt1
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = sorted([(X[i][0],i) for i in range(N)],key=lambda x:x[0])
distX = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    a,i = A[j]
    if j>=curR:
        k = j+1
        while k<N and A[k][0]==a:
            k += 1
        curR = k
        k = curL+1
        while A[k][0]!=a:
            k += 1
        curL = k
    if curR<N:
        d = A[curR][0]-a
        distX[i].append((d,A[curR][1]))
    if curL-1>=0:
        d = a-A[curL-1][0]
        distX[i].append((d,A[curL-1][1]))
B = sorted([(X[i][1],i) for i in range(N)],key=lambda x:x[0])
distY = [[] for _ in range(N)]
curL = -1
curR = 0
for j in range(N):
    b,i = B[j]
    if j>=curR:
        k = j+1
        while k<N and B[k][0]==b:
            k += 1
        curR = k
        k = curL+1
        while B[k][0]!=b:
            k += 1
        curL = k
    if curR<N:
        d = B[curR][0]-b
        distY[i].append((d,B[curR][1]))
    if curL-1>=0:
        d = b-B[curL-1][0]
        distY[i].append((d,B[curL-1][1]))
T = {i:[i,1] for i in range(N)}
for j in range(1,N):
    if A[j][0]==A[j-1][0]:
        union(find(A[j][1]),find(A[j-1][1]))
        find(A[j][1])
for j in range(1,N):
    if B[j][0]==B[j-1][0]:
        rt = find(B[j-1][1])
        rt0 = find(B[j][1])
        if rt!=rt0:
            union(rt,rt0)
            find(B[j][1])
            find(B[j-1][1])
D = []
for i in range(N):
    for d,j in distX[i]:
        D.append((d,i,j))
    for d,j in distY[i]:
        D.append((d,i,j))
D = sorted(D,key=lambda x:x[0])
cnt = 0
for d,i,j in D:
    rt = find(i)
    rt0 = find(j)
    if rt!= rt0:
        cnt += d
        union(rt,rt0)
print(cnt)