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:
N = int(input())
XY = [list(map(int, input().split())) + [i + 1] for i in range(N)]

dist = []

XY.sort()
for i in range(N - 1):
  dist.append((abs(XY[i][0] - XY[i + 1][0]), (XY[i][2], XY[i + 1][2])))
XY.sort(key = lambda x: x[1])
for i in range(N - 1):
  dist.append((abs(XY[i][1] - XY[i + 1][1]), (XY[i][2], XY[i + 1][2])))
dist.sort()

root = [i for i in range(N + 1)]
comp_size = [1] * (N+1)
 
def root_find(x):
  y = root[x]
  if x == y:
    return x
  else:
    z = root_find(y)
    root[x] = z
    return z

def merge(x, y):
  rx = root_find(x)
  ry = root_find(y)
  sx = comp_size[rx]
  sy = comp_size[ry]
  if rx != ry:
    if sx >= sy:
      root[ry] = rx
      comp_size[rx] = sx + sy
    else:
      root[rx] = ry
      comp_size[ry] = sx + sy
      
answer = 0
for d, (a, b) in dist:
  if root_find(a) != root_find(b):
    merge(a, b)
    answer += d

print(answer)

Submission status: Time Limit Exceeded

Solution code:
def find_parent(x):
    y=parent[x]
    if y<0:
        return x
    parent[x]=find_parent(y)
    return parent[x]

def connect(a,b):
    c=find_parent(a)
    d=find_parent(b)
    if c==d:
        return
    if parent[c]<parent[d]:
        parent[c]+=parent[d]
        parent[d]=c
    else:
        parent[d]+=parent[c]
        parent[c]=d
    return

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

X.sort()
Y.sort()
edge=[]
for i in range(1,N):
    edge.append([X[i][0]-X[i-1][0],X[i-1][1],X[i][1]])
    edge.append([Y[i][0]-Y[i-1][0],Y[i-1][1],Y[i][1]])
edge.sort()
parent=[-1]*N

ans=0
for l,a,b in edge:
    if find_parent(a)==find_parent(b):
        continue
    else:
        ans+=l
        connect(a,b)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush
import sys
input=sys.stdin.readline

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

X.sort()
Y.sort()
data=[[] for i in range(N)]
for i in range(1,N):
    x1,num1=X[i-1]
    x2,num2=X[i]
    data[num1].append([num2,x2-x1])
    data[num2].append([num1,x2-x1])
    y1,num1=Y[i-1]
    y2,num2=Y[i]
    data[num1].append([num2,y2-y1])
    data[num2].append([num1,y2-y1])

que=[[0,0]]
flag=[inf]*N
ans=0

while que:
    l,u=heappop(que)
    if flag[u]!=inf:
        continue
    else:
        flag[u]=l
        ans+=l
        for v,y in data[u]:
            if flag[v]!=inf:
                continue
            else:
                heappush(que,[y,v])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush

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

X.sort()
Y.sort()
data=[[] for i in range(N)]
for i in range(1,N):
    x1,num1=X[i-1]
    x2,num2=X[i]
    data[num1].append([num2,x2-x1])
    data[num2].append([num1,x2-x1])
    y1,num1=Y[i-1]
    y2,num2=Y[i]
    data[num1].append([num2,y2-y1])
    data[num2].append([num1,y2-y1])

que=[[0,0]]
flag=[inf]*N
ans=0

while que:
    l,u=heappop(que)
    if flag[u]!=inf:
        continue
    else:
        flag[u]=l
        ans+=l
        for v,y in data[u]:
            if flag[v]!=inf:
                continue
            else:
                heappush(que,[y,v])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush

N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
inf=float("inf")

yx=[]
for x,y,i in xy:
    yx.append([y,x,i])
xy.sort()
yx.sort()
data=[[] for i in range(N)]
for i in range(1,N):
    x1,y1,num1=xy[i-1]
    x2,y2,num2=xy[i]
    data[num1].append([num2,x2-x1])
    data[num2].append([num1,x2-x1])
    y1,x1,num1=yx[i-1]
    y2,x2,num2=yx[i]
    data[num1].append([num2,y2-y1])
    data[num2].append([num1,y2-y1])
que=[[0,0]]
flag=[inf]*N
while que:
    l,u=heappop(que)
    if flag[u]!=inf:
        continue
    else:
        flag[u]=l
        for v,y in data[u]:
            if flag[v]!=inf:
                continue
            else:
                heappush(que,[y,v])
print(sum(flag))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[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
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
    
    def __str__(self):
        rt=[i if j<0 else j for i,j in enumerate(self.table)]
        return str(rt)
        
def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    
    # calc
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev

n=I()
p=[]
for i in range(n):
    x,y=LI()
    p.append((x,y,i))
    
X=sorted(p,key=lambda x:x[0])
Y=sorted(p,key=lambda x:x[1])

g=[[] for i in range(n)]
q=[]
for i in range(n-1):
    x0,y0,a=X[i]
    x1,y1,b=X[i+1]
    q.append((min(abs(x1-x0),abs(y1-y0)),a,b))
    
for i in range(n-1):
    x0,y0,a=Y[i]
    x1,y1,b=Y[i+1]
    q.append((min(abs(x1-x0),abs(y1-y0)),a,b))
    
uf=UnionFind(n)
heapify(q)

ans=0
e=n-1
while e:
    d,a,b=heappop(q)
    if uf._root(a)!=uf._root(b):
        ans+=d
        uf.union(a,b)
        e-=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[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
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
    
    def __str__(self):
        rt=[i if j<0 else j for i,j in enumerate(self.table)]
        return str(rt)
        
def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    
    # calc
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev

n=I()
p=[]
for i in range(n):
    x,y=LI()
    p.append((x,y,i))
    
X=sorted(p,key=lambda x:x[0])
Y=sorted(p,key=lambda x:x[1])

g=[[] for i in range(n)]
q=[]
for i in range(n-1):
    x0,y0,a=X[i]
    x1,y1,b=X[i+1]
    g[a].append((b,abs(x1-x0)))
    g[b].append((a,abs(x1-x0)))
    q.append((min(abs(x1-x0),abs(y1-y0)),a,b))
    
for i in range(n-1):
    x0,y0,a=Y[i]
    x1,y1,b=Y[i+1]
    g[a].append((b,abs(y1-y0)))
    g[b].append((a,abs(y1-y0)))
    q.append((min(abs(x1-x0),abs(y1-y0)),a,b))
    
uf=UnionFind(n)
heapify(q)

ans=0
e=n-1
while e:
    d,a,b=heappop(q)
    if uf._root(a)!=uf._root(b):
        ans+=d
        uf.union(a,b)
        e-=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

X, Y = [], []
for i in range(N):
  x, y = XY[i]
  X.append((x, i + 1))
  Y.append((y, i + 1))
X.sort()
Y.sort()

edge = [0] * (N - 1) * 2
xa, ax = X[0]
ya, ay = Y[0]
for i in range(N - 1):
  xb, bx = X[i + 1]
  edge[i * 2] = (abs(xa - xb), (ax, bx))
  yb, by = Y[i + 1]
  edge[i * 2 + 1] = (abs(ya - yb), (ay, by))
  xa, ax = xb, bx
  ya, ay = yb, by
edge.sort()

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 size(self, x):
    if self.parents[x] < 0:
      return -self.parents[x]
    else:
      self.parents[x] = self.size(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
  
answer = 0
edge_cnt = 0
U = UnionFind(N + 1)

for e in edge:
  c, ab = e
  a, b = ab
  if U.find(a) != U.find(b):
    U.union(a, b)
    answer += c
    edge_cnt += 1
  if edge_cnt == N - 1:
    break
    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

X, Y = [], []
for i in range(N):
  x, y = XY[i]
  X.append((x, i + 1))
  Y.append((y, i + 1))
X.sort()
Y.sort()

edge = []
for i in range(N - 1):
  xa, a = X[i]
  xb, b = X[i + 1]
  edge.append((abs(xa - xb), (a, b)))
  ya, a = Y[i]
  yb, b = Y[i + 1]
  edge.append((abs(ya - yb), (a, b))) 
edge.sort()

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 size(self, x):
    if self.parents[x] < 0:
      return -self.parents[x]
    else:
      self.parents[x] = self.size(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
  
answer = 0
edge_cnt = 0
U = UnionFind(N + 1)

for e in edge:
  c, ab = e
  a, b = ab
  if U.find(a) != U.find(b):
    U.union(a, b)
    answer += c
    edge_cnt += 1
  if edge_cnt == N - 1:
    break
    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

X, Y = [], []
for i in range(N):
  x, y = XY[i]
  X.append((x, i + 1))
  Y.append((y, i + 1))
X.sort()
Y.sort()

edge = []
for i in range(N - 1):
  xa, a = X[i]
  xb, b = X[i + 1]
  edge.append((abs(xa - xb), (a, b)))
  ya, a = Y[i]
  yb, b = Y[i + 1]
  edge.append((abs(ya - yb), (a, b))) 
edge.sort()

root = [i for i in range(N + 1)]
comp_size = [1] * (N + 1)
 
def find_root(x):
  y = root[x]
  if y == x:
    return x
  else:
    z = find_root(y)
    root[x] = z
    return z

def merge(x, y):
  rx = find_root(x)
  ry = find_root(y)
  if rx == ry:
    return 0
  if comp_size[rx] > comp_size[ry]:
    comp_size[rx] += comp_size[ry]
    root[ry] = rx
  else:
    comp_size[ry] += comp_size[rx]
    root[rx] = ry
  return 1
  
answer = 0
for e in edge:
  c, ab = e
  a, b = ab
  answer += c * merge(a, b)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq as hq
input = sys.stdin.readline
n = int(input())
x_xy = []
y_xy = []
for i in range(n):
  x,y = map(int,input().split())
  x_xy.append([x,i+1])
  y_xy.append([y,i+1])
x_xy.sort()
y_xy.sort()
edge = [[] for i in range(n+1)]
for i in range(1,n):
  xf,v2 = x_xy[i]
  xi,v1 = x_xy[i-1]
  edge[v1].append([abs(xf-xi),v2])
  edge[v2].append([abs(xf-xi),v1])
  yf,v2 = y_xy[i]
  yi,v1 = y_xy[i-1]
  edge[v1].append([abs(yf-yi),v2])
  edge[v2].append([abs(yf-yi),v1])
edges = edge[1]
hq.heapify(edges)
connect = [0 for i in range(n+1)]
connect[1] = 1
ans = 0
while edges:
  cost,v2 = hq.heappop(edges)
  if connect[v2] == 1:
    continue
  ans += cost
  connect[v2] = 1
  for e in edge[v2]:
    hq.heappush(edges,e)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq as hq
input = sys.stdin.readline
n = int(input())
xy = [list(map(int,input().split()))+[i+1] for i in range(n)]
x_xy = sorted(xy)
y_xy = sorted(xy,key = lambda x:x[1])
edge = [[] for i in range(n+1)]
for i in range(1,n):
  xf,yf,v2 = x_xy[i]
  xi,yi,v1 = x_xy[i-1]
  edge[v1].append([abs(xf-xi),v2])
  edge[v2].append([abs(xf-xi),v1])
  xf,yf,v2 = y_xy[i]
  xi,yi,v1 = y_xy[i-1]
  edge[v1].append([abs(yf-yi),v2])
  edge[v2].append([abs(yf-yi),v1])
edges = edge[1]
hq.heapify(edges)
connect = [0 for i in range(n+1)]
connect[1] = 1
ans = 0
while edges:
  cost,v2 = hq.heappop(edges)
  if connect[v2] == 1:
    continue
  ans += cost
  connect[v2] = 1
  for e in edge[v2]:
    hq.heappush(edges,e)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#クラスカル, union find, x,yでソートして隣接辺
import sys
import heapq
input = sys.stdin.readline

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

Edg = []
p1.sort()
for i in range(n):
    u = p1[i-1][2]
    v = p1[i][2]
    heapq.heappush(Edg, (min(abs(p0[u][0]-p0[v][0]), abs(p0[u][1]-p0[v][1])),u,v) )
#p2 = [pxy for pxy in p1]
p1.sort(key = lambda pp: pp[1])

for i in range(n):
    u = p1[i-1][2]
    v = p1[i][2]
    heapq.heappush(Edg, (min(abs(p0[u][0]-p0[v][0]), abs(p0[u][1]-p0[v][1])),u,v) )
   
#print(Edg)
tag = [i for i in range(n)]
cnt = 0

while Edg:
    l,x,y = heapq.heappop(Edg)
    i,j = x,y
    while i != tag[i]:
        i = tag[i]
    while j != tag[j]:
        j = tag[j]
    if i != j:
        cnt += l
        #print(cnt)
        chng1 = []
        chng2 = []
        chng1.append(x)
        x = tag[x]
        chng2.append(y)
        y = tag[y]
        while x != tag[x]:
            chng1.append(x)
            x = tag[x]
        chng1.append(x)
        while y != tag[y]:
            chng2.append(y)
            y = tag[y]
        chng2.append(y)
        if len(chng1) < len(chng2):
            for x_ in chng1:
                tag[x_] = y
        else:
            for y_ in chng2:
                tag[y_] = x
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#クラスカル, union find, x,yでソートして隣接辺
import heapq

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

p1.sort()
p2 = [pxy for pxy in p1]
p2.sort(key = lambda pp: pp[1])

Edg = []

for i in range(n):
    u = p1[i-1][2]
    v = p1[i][2]
    heapq.heappush(Edg, (min(abs(p0[u][0]-p0[v][0]), abs(p0[u][1]-p0[v][1])),u,v) )
    u = p2[i-1][2]
    v = p2[i][2]
    heapq.heappush(Edg, (min(abs(p0[u][0]-p0[v][0]), abs(p0[u][1]-p0[v][1])),u,v) )

#print(Edg)
tag = [i for i in range(n)]
cnt = 0
while Edg:
    l,x,y = heapq.heappop(Edg)
    i,j = x,y
    while i != tag[i]:
        i = tag[i]
    while j != tag[j]:
        j = tag[j]
    if i != j:
        cnt += l
        #print(cnt)
        chng1 = []
        chng2 = []
        chng1.append(x)
        x = tag[x]
        chng2.append(y)
        y = tag[y]
        while x != tag[x]:
            chng1.append(x)
            x = tag[x]
        chng1.append(x)
        while y != tag[y]:
            chng2.append(y)
            y = tag[y]
        chng2.append(y)
        if len(chng1) < len(chng2):
            for x_ in chng1:
                tag[x_] = y
        else:
            for y_ in chng2:
                tag[y_] = x
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq

def solve(N: int, x: "List[int]", y: "List[int]"):
    ## プリム法
    ## 0~N-1の町がある

    isUsed = [False]*N
    isUsed[0]=True
    priority_queue = [] # (cost,node)
    for i in range(1,N):
        heapq.heappush(priority_queue,(min(abs(x[0]-x[i]),abs(y[0]-y[i])),i))

    answer = 0
    while priority_queue:
        cost,node = heapq.heappop(priority_queue)

        if isUsed[node]:
            continue
        else:
            isUsed[node] = True

        answer += cost
        for i in range(N):
            if isUsed[i]:
                continue
            heapq.heappush(priority_queue,(min(abs(x[node]-x[i]),abs(y[node]-y[i])),i))
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
n = int(input())
v_ls = []
for i in range(n):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    v_ls.append((x, y))

already = set()
cur = [(0, 0, 0)]
cost = 0
while len(cur) > 0:
    cur_cost, cur_ind, plus = heapq.heappop(cur)
    cur_x, cur_y = v_ls[cur_ind]
    if cur_ind in already:
        continue
    already.add(cur_ind)
    cost += plus
    for _next, (x, y) in enumerate(v_ls):
        if _next in already:
            continue
        next_cost = min(abs(cur_x - x), abs(cur_y - y))
        heapq.heappush(cur, (cur_cost + next_cost, _next, next_cost))
    if len(already) == n:
        break
print(cost)

Submission status: Time Limit Exceeded

Solution code:
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())

edge = [[] for i in range(n)]
#隣接リスト edge[i]:[コスト,行先]
l=[]
for i in range(n):
    a,b=map(int,input().split())
    l.append([a,b,i])
l=sorted(l,key=lambda x: -x[0])
for i in range(n-1):
    x=l[i][2]
    y=l[i+1][2]
    z=l[i][0]-l[i+1][0]
    edge[x].append([z,y])
    edge[y].append([z,x])
l=sorted(l,key=lambda x: -x[1])
for i in range(n-1):
    x=l[i][2]
    y=l[i+1][2]
    z=l[i][1]-l[i+1][1]
    edge[x].append([z,y])
    edge[y].append([z,x])
print(prim_heap())

Submission status: Time Limit Exceeded

Solution code:
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())

edge = [[] for i in range(n)]
#隣接リスト edge[i]:[コスト,行先]
l=[]
for i in range(n):
    a,b=map(int,input().split())
    l.append([a,b,i])
l=sorted(l,key=lambda x: -x[0])
for i in range(n-1):
    x=l[i][2]
    y=l[i+1][2]
    z=l[i][0]-l[i+1][0]
    edge[x].append([z,y])
    edge[y].append([z,x])
l=sorted(l,key=lambda x: -x[1])
for i in range(n-1):
    x=l[i][2]
    y=l[i+1][2]
    z=l[i][1]-l[i+1][1]
    edge[x].append([z,y])
    edge[y].append([z,x])
print(prim_heap())

Submission status: Time Limit Exceeded

Solution code:
def dist(u, v):
    return min( abs(x[u]-x[v]), abs(y[u]-y[v]) ) 

def mst():

    s, H = 0, []
    
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE for u in range(V)]

    d[s] = 0
    heappush(H, (d[s], s))

    while H:
        x, u = heappop(H)
        if color[u] == BLACK:
            #print(' u is black')
            continue
        
        d[u] = x
        color[u] = BLACK
        #print('pop: d[{}] = {}'.format(u, x))
        
        for v in range(V):
            if color[v] != BLACK:
                color[v] = GRAY
                c = dist(u, v)
                heappush(H, (c, v))
                #print('push: H, u, v',  H, u, v)

#-----

from heapq import heappush, heappop

INF = float('inf') 

V = int(input())
x = [None] * V
y = [None] * V
for i in range(V):
    x[i], y[i] = map(int, input().split())
    
d = [INF for _ in range(V)]

mst()
print(sum(d)); #print(d)

Submission status: Time Limit Exceeded

Solution code:
def dist(u, v):
    return min( abs(x[u]-x[v]), abs(y[u]-y[v]) ) 

def mst():

    s, H = 0, []
    
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE for u in range(V)]

    d[s] = 0
    heappush(H, (d[s], s))

    while H:
        x, u = heappop(H)
        if color[u] == BLACK:
            #print(' u is black')
            continue
        
        d[u] = x
        color[u] = BLACK
        #print('pop: d[{}] = {}'.format(u, x))
           
        for v, c in M[u]:
            if color[v] != BLACK:
                color[v] = GRAY
                heappush(H, (c, v))
                #print('push: H, d',  H, d)

#-----

from heapq import heappush, heappop

INF = float('inf') 

V = int(input())
x = [None] * V
y = [None] * V
for i in range(V):
    x[i], y[i] = map(int, input().split())
    
d = [INF for _ in range(V)]
p = [ -1 for _ in range(V)]

M = [ [] for _ in range(V) ]
for s in range(V):
    for t in range(s+1, V):
        w = dist(s, t)
        M[s].append((t, w))
        M[t].append((s, w))
        
#print(M)
mst()
print(sum(d)); #print(d)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
L = []
ans = 0
for i in range(n):
    a,b = map(int,input().split())
    L.append([a,b,i])
P = []
L.sort()
for i in range(n-1):
    dist = min(abs(L[i][0]-L[i+1][0]),abs(L[i][1]-L[i+1][1]))
    P.append([dist,L[i][2],L[i+1][2]])
L = sorted(L, key = lambda x:x[1])
for i in range(n-1):
    dist = min(abs(L[i][0]-L[i+1][0]),abs(L[i][1]-L[i+1][1]))
    P.append([dist,L[i][2],L[i+1][2]])
P.sort()
par = [i for i in range(n)]
rank = [0]*n
def find(x,par):
    if x == par[x]:
        return par[x]
    else:
        return find(par[x],par)
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    if x != y:
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
for i in range(len(P)):
    if find(P[i][1],par) != find(P[i][2],par):
        ans += P[i][0]
        unite(P[i][1],P[i][2],par,rank)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import heapq
    def root(index):
        if tree[index][0]==index:
            return index
        else:
            tree[index][0]=root(tree[index][0])
            return tree[index][0]

    def unite(index1,index2):
        r1=root(index1)
        r2=root(index2)
        if r1!=r2:
            d1,d2=tree[r1][1],tree[r2][1]
            if d1<=d2:
                tree[r1][0]=r2
                tree[r2][1]=max(d1+1,d2)
            else:
                tree[r2][0]=r1
                tree[r1][1]=max(d2+1,d1)

    def same(index1,index2):
        return root(index1)==root(index2)
    
    n=int(input())
    xy=[list(map(int,input().split())) for _ in [0]*n]
    xyz=[xy[i]+[i] for i in range(n)]
    x_sort=sorted(xyz,key=lambda x:x[0])
    y_sort=sorted(xyz,key=lambda x:x[1])
    
    tree=[[i,1] for i in range(n)]#root,depth
    g=[]
    heapq.heapify(g)
    for i in range(n-1):
        heapq.heappush(g,[abs(x_sort[i+1][0]-x_sort[i][0]),x_sort[i][2],x_sort[i+1][2]])
    for i in range(n-1):
        heapq.heappush(g,[abs(y_sort[i+1][1]-y_sort[i][1]),y_sort[i][2],y_sort[i+1][2]])

    cnt=0
    while g:
        d,i,j=heapq.heappop(g)
        if same(i,j)==False:
            cnt+=d
            unite(i,j)
    print(cnt)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import heapq
    class unionfind():
        #size:要素数,tree：unionfind木
        def __init__(self,size):#self,要素数
            self.size=size
            self.tree=[[i,1] for i in range(self.size)]#root,depth
        
        #rootを探す
        def root(self,index):
            if self.tree[index][0]==index:
                return index
            else:
                self.tree[index][0]=self.root(self.tree[index][0])
                return self.tree[index][0]
    
        #結合
        def unite(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1!=r2:
                d1,d2=self.tree[r1][1],self.tree[r2][1]
                if d1<=d2:
                    self.tree[r1][0]=r2
                    self.tree[r2][1]=max(d1+1,d2)
                else:
                    self.tree[r2][0]=r1
                    self.tree[r1][1]=max(d2+1,d1)
    
        #同じか判定
        def same(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            return r1==r2
    
    n=int(input())
    xy=[list(map(int,input().split())) for _ in [0]*n]
    xyz=[xy[i]+[i] for i in range(n)]
    x_sort=sorted(xyz,key=lambda x:x[0])
    y_sort=sorted(xyz,key=lambda x:x[1])
    g=[]
    heapq.heapify(g)
    for i in range(n-1):
        heapq.heappush(g,[abs(x_sort[i+1][0]-x_sort[i][0]),x_sort[i][2],x_sort[i+1][2]])
    for i in range(n-1):
        heapq.heappush(g,[abs(y_sort[i+1][1]-y_sort[i][1]),y_sort[i][2],y_sort[i+1][2]])
    u=unionfind(n)
    cnt=0
    while g:
        d,i,j=heapq.heappop(g)
        if u.same(i,j)==False:
            cnt+=d
            u.unite(i,j)
    print(cnt)
main()