Problem:


Score : 500 points

Problem Statement

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

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

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

Constraints

2 ≤ N ≤ 10^5

0 ≤ x_i,y_i ≤ 10^9

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

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

Sample Input 1

3
1 5
3 9
7 8

Sample Output 1

3

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

Sample Input 2

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

Sample Output 2

8



Sample input:
3
1 5
3 9
7 8


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
from heapq import heappop, heappush

#入力受け取り
def getlist():
	return list(map(int, input().split()))

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 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

#処理内容
def main():
	N = int(input())
	L1 = []
	L2 = []
	for i in range(N):
	    x, y = list(map(int, input().split()))
	    L1.append((x, y, i))
	    L2.append((y, x, i))
	Lx = sorted(L1)
	Ly = sorted(L2)
	Q = []

	for i in range(N - 1):
	    u = Lx[i][2]
	    v = Lx[i + 1][2]
	    w = Lx[i + 1][0] - Lx[i][0]
	    heappush(Q, (w, u, v))
	    u = Ly[i][2]
	    v = Ly[i + 1][2]
	    w = Ly[i + 1][0] - Ly[i][0]
	    heappush(Q, (w, u, v))

	Km = Kruskal(Q, N)
	print(Km.cost)	

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    A = [tuple(list(map(int, [str(i)]+input().split()))) for i in range(N)]
    A_x = sorted(A, key=lambda x:x[1])
    A_y = sorted(A, key=lambda x:x[2])
    # print(A)
    network_candidate = []
    network_nodes = []
    
    for i in range(N-1):
        network_candidate.append((A_x[i][0], A_x[i+1][0], A_x[i+1][1]-A_x[i][1]))
        network_candidate.append((A_y[i][0], A_y[i+1][0], A_y[i+1][2]-A_y[i][2]))
        
    network_candidate.sort(key=lambda x:x[2])
    
    edge = network_candidate.pop(0)
    ret = edge[2]
    network_nodes += [edge[0], edge[1]]
    
    while network_candidate or len(network_nodes) < N:
        edge = network_candidate.pop(0)
        if edge[0] not in network_nodes or edge[1] not in network_nodes:
            ret += edge[2]
            if edge[0] not in network_nodes:
                network_nodes.append(edge[0])
            else:
                network_nodes.append(edge[1])
                
    print(ret)
    
solve()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
n=int(input())
xy=[]
yx=[]
for i in range(n):
    x,y=map(int,input().split())
    xy.append([x,y,i])
    yx.append([y,x,i])
xy.sort()
yx.sort()
data=[[0,0] for i in range(n)]
for i in range(n):
    x,y,a=xy[i]
    data[a][0]=i
    y,x,a=yx[i]
    data[a][1]=i
ans=0
que=[[0,0]]
flag=[0]*n
count=0
while count<=n:
    l,a=heappop(que)
    if flag[a]==1:
        continue
    ans+=l
    flag[a]=1
    count+=1
    if count==n:
        break
    b,c=data[a]
    xb=xy[b][0]
    yc=yx[c][0]
    if 1<=b<=n-2:
        xd,yd,d=xy[b-1]
        xe,ye,e=xy[b+1]
        if flag[d]==0:
            heappush(que,[abs(xd-xb),d])
        if flag[e]==0:
            heappush(que,[abs(xe-xb),e])
    elif b==0:
        xe,ye,e=xy[1]
        if flag[e]==0:
            heappush(que,[abs(xb-xe),e])
    else:
        xd,yd,d=xy[n-2]
        if flag[d]==0:
            heappush(que,[abs(xb-xd),d])
    if 1<=c<=n-2:
        yg,xg,g=yx[c+1]
        yf,xf,f=yx[c-1]
        if flag[f]==0:
            heappush(que,[abs(yf-yc),f])
        if flag[g]==0:
            heappush(que,[abs(yg-yc),g])
    elif c==0:
        yg,xg,g=yx[1]
        if flag[g]==0:
            heappush(que,[abs(yg-yc),g])
    else:
        yf,xf,f=yx[n-2]
        if flag[f]==0:
            heappush(que,[abs(yf-yc),f])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Prim():
    def __init__(self,N):
        import collections
        self.N = N
        self.edge = collections.defaultdict(list)
    def add(self,a,b,cost):
        self.edge[a].append((b,cost))
        self.edge[b].append((a,cost))
    def cut_edge(self,start=0):
        import heapq,collections
        #new_edge = collections.defaultdict(list)
        edge_sum = 0
        node_flag = [False for _ in range(self.N)]
        node_flag[start] = True
        q = []
        for to,cost in self.edge[start]:
            heapq.heappush(q,(cost,start,to))
        while q :
            c,s,t = heapq.heappop(q)
            if node_flag[t] is False:
                #new_edge[s].append((t,c))
                edge_sum += c
                node_flag[t] = True
                for to,cost in self.edge[t]:
                    if not node_flag[to]:
                        heapq.heappush(q,(cost,t,to))
        return edge_sum

N = int(input())
graph = Prim(N)
xy = [list(map(int,input().split())) for _ in range(N)]
nx = [(i,xy[i][0]) for i in range(N)]
ny = [(i,xy[i][1]) for i in range(N)]
nx.sort(key=lambda x:x[1])
ny.sort(key=lambda x:x[1])

for i in range(N-1):
    prev_n,prev_x = nx[i]
    next_n,next_x = nx[i+1]
    graph.add(prev_n,next_n,next_x-prev_x)
    prev_n,prev_y = ny[i]
    next_n,next_y = ny[i+1]
    graph.add(prev_n,next_n,next_y-prev_y)
print(graph.cut_edge())

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
import heapq
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
xlist = []
ylist = []
for i in range(N):
  x, y = IL()
  xlist.append([x, i])
  ylist.append([y, i])

xroot = [[] for _ in range(N+1)]
yroot = [[] for _ in range(N+1)]

xlist.sort(key=itemgetter(0)) # [x, ID]
ylist.sort(key=itemgetter(0)) # [y, ID]

for i in range(N-1):
  x, xID = xlist[i]
  nextx, nextxID = xlist[i + 1]
  costx = nextx - x
  xroot[xID].append([costx, nextxID])
  xroot[nextxID].append([costx, xID])

  y, yID = ylist[i]
  nexty, nextyID = ylist[i + 1]
  costy = nexty - y
  yroot[yID].append([costy, nextyID])
  yroot[nextyID].append([costy, yID])
#print(xroot) # [cost, rootID]
#print(yroot)

hpop = heapq.heappop
hpush = heapq.heappush
data = [] # [val, ID]

visited = [False]*(N+1)
hpush(data, [0, 1])
ans = 0
while data:
  val, num = hpop(data)
  if visited[num] == False:
    visited[num] = True
    #print(val, num)
    ans += val
    for i in xroot[num]:
      if visited[i[1]] == False:
        hpush(data, i)
    for j in yroot[num]:
      if visited[j[1]] == False:
        hpush(data, j)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def init(n):
  for i in range(N):
    par[i]=i
    rnk[i]=0
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if (rnk[x]<rnk[y]):
    par[x]=y
  else:
    par[y]=x
    if(rnk[x]==rnk[y]):
      rnk[x]+=1
def same(x,y):
    return find(x)==find(y)

N = I()
xlist = []
ylist = []

par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
init(N)

for i in range(N):
  x, y = IL()
  xlist.append([x, i])
  ylist.append([y, i])
xlist.sort()
ylist.sort()

node = []
for i in range(N-1):
  x, xID = xlist[i]
  nextx, nextxID = xlist[i + 1]
  y, yID = ylist[i]
  nexty, nextyID = ylist[i + 1]
  
  node.append([nextx - x, xID, nextxID])
  node.append([nexty - y, yID, nextyID])
node.sort(reverse=True)

ans = 0
while node:
  val, i, j = node.pop()
  if same(i, j):
    continue
  else:
    unite(i, j)
    ans += val
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import bisect
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def init(n):
  for i in range(N):
    par[i]=i
    rnk[i]=0
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if (rnk[x]<rnk[y]):
    par[x]=y
  else:
    par[y]=x
    if(rnk[x]==rnk[y]):
      rnk[x]+=1
def same(x,y):
    return find(x)==find(y)

N = I()
xlist = []
ylist = []

par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
init(N)

for i in range(N):
  x, y = IL()
  xlist.append([x, i])
  ylist.append([y, i])
xlist.sort()
ylist.sort()

hpop = heapq.heappop
hpush = heapq.heappush

node = []
for i in range(N-1):
  x, xID = xlist[i]
  nextx, nextxID = xlist[i + 1]
  y, yID = ylist[i]
  nexty, nextyID = ylist[i + 1]
  
  hpush(node, [nextx - x, xID, nextxID])
  hpush(node, [nexty - y, yID, nextyID])

ans = 0
while node:
  val, i, j = hpop(node)
  if same(i, j):
    continue
  else:
    unite(i, j)
    ans += val
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
xlist = []
ylist = []
for i in range(N):
  x, y = IL()
  xlist.append([x, i])
  ylist.append([y, i])

xroot = [[] for _ in range(N+1)]
yroot = [[] for _ in range(N+1)]

xlist.sort() # [x, ID]
ylist.sort() # [y, ID]

for i in range(N-1):
  x, xID = xlist[i]
  nextx, nextxID = xlist[i + 1]
  costx = nextx - x
  xroot[xID].append([costx, nextxID])
  xroot[nextxID].append([costx, xID])

  y, yID = ylist[i]
  nexty, nextyID = ylist[i + 1]
  costy = nexty - y
  yroot[yID].append([costy, nextyID])
  yroot[nextyID].append([costy, yID])
#print(xroot) # [cost, rootID]
#print(yroot)

hpop = heapq.heappop
hpush = heapq.heappush
data = [] # [val, ID]

visited = [False]*(N+1)
hpush(data, [0, 1])
ans = 0
while data:
  val, num = hpop(data)
  if visited[num] == False:
    visited[num] = True
    #print(val, num)
    ans += val
    for i in xroot[num]:
      if visited[i[1]] == False:
        hpush(data, i)
    for j in yroot[num]:
      if visited[j[1]] == False:
        hpush(data, j)
print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
cityx = []
cityy = []
for i in range(N):
    x,y = map(int,input().split())
    cityx.append([x,i])
    cityy.append([y,i])
cityx.sort()
cityy.sort()

side = [[]for i in range(N)]
for i in range(N-1):
    a,x = cityx[i]
    b,y = cityx[i+1]
    side[x].append([b-a,y])
    side[y].append([b-a,x])
for i in range(N-1):
    a,x = cityy[i]
    b,y = cityy[i+1]
    side[x].append([b-a,y])
    side[y].append([b-a,x])

f = [1] + [0] * (N-1)
queue = side[0][:]
ans = 0
heapq.heapify(queue)
while queue:
    cost, q = heapq.heappop(queue)
    if f[q] == 0:
        ans += cost
        f[q] = 1
        for a,b in side[q]:
            heapq.heappush(queue,[a,b])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
class Unionfind:
    def __init__(self,n):
        self.per = [i for i in range(n)]

    def find(self, x):
        if self.per[x] == x:
            return x
        else:
            self.per[x] = self.find(self.per[x])
            return self.per[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)
        self.per[x] = y
        
            
N = int(input())
cityx = []
cityy = []
for i in range(N):
    x,y = map(int,input().split())
    cityx.append([x,i])
    cityy.append([y,i])
cityx.sort()
cityy.sort()
side = []
for i in range(N-1):
    side.append([cityx[i+1][0]-cityx[i][0], cityx[i+1][1], cityx[i][1]])
    side.append([cityy[i+1][0]-cityy[i][0], cityy[i+1][1], cityy[i][1]])
side.sort()
ans = 0
uf = Unionfind(N)
for cost, x, y in side:
    if uf.same_check(x,y):
        continue
    ans += cost
    uf.union(x,y)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
class Unionfind:
    def __init__(self,n):
        self.per = [i for i in range(n)]
        self.rank = [0]*n

    def find(self, x):
        if self.per[x] == x:
            return x
        else:
            self.per[x] = self.find(self.per[x])
            return self.per[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.per[x] = y
        else:
            self.per[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

N = int(input())
cityx = []
cityy = []
for i in range(N):
    x,y = map(int,input().split())
    cityx.append([x,i])
    cityy.append([y,i])
cityx.sort()
cityy.sort()
side = []
for i in range(N-1):
    side.append([cityx[i+1][0]-cityx[i][0], cityx[i+1][1], cityx[i][1]])
    side.append([cityy[i+1][0]-cityy[i][0], cityy[i+1][1], cityy[i][1]])
side.sort()
ans = 0
uf = Unionfind(N)
for cost, x, y in side:
    if uf.same_check(x,y):
        continue
    ans += cost
    uf.union(x,y)

print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
cityx = []
cityy = []
for i in range(N):
    x,y = map(int,input().split())
    cityx.append([x,i])
    cityy.append([y,i])
side = []
cityx.sort()
cityy.sort()
for i in range(N-1):
    side.append([cityx[i+1][0]-cityx[i][0],cityx[i][1],cityx[i+1][1]])
    side.append([cityy[i+1][0]-cityy[i][0],cityy[i][1],cityy[i+1][1]])

side.sort()
node = [[i,[i]]for i in range(N)]
ans = 0
for cost,a,b in side:
    if node[a][0] != node[b][0]:
        ans += cost
        c,d = node[node[a][0]],node[node[b][0]]
        if len(c[1]) < len(d[1]):
            for i in c[1]:
                node[i][0] = d[0]
            d[1] = d[1] + c[1]
        else:
            for i in d[1]:
                node[i][0] = c[0]
            c[1] = d[1] + c[1]
print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
city = []
for i in range(N):
    x,y = map(int,input().split())
    city.append([x,y,i])
side = []
city.sort(key=lambda x:x[0])
for i in range(N-1):
    side.append([city[i+1][0] - city[i][0],city[i][2] ,city[i+1][2]])

city.sort(key=lambda x:x[1])
for i in range(N-1):
    side.append([city[i+1][1] - city[i][1],city[i][2] ,city[i+1][2]])
side.sort()
node = [[i,[i]]for i in range(N)]
ans = 0
for cost,a,b in side:
    if node[a][0] != node[b][0]:
        ans += cost
        c,d = node[node[a][0]],node[node[b][0]]
        if len(c[1]) < len(d[1]):
            for i in c[1]:
                node[i][0] = d[0]
            d[1] = d[1] + c[1]
        else:
            for i in d[1]:
                node[i][0] = c[0]
            c[1] = d[1] + c[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
city = []
for i in range(N):
    x,y = map(int,input().split())
    city.append([x,y,i])
side = []
city.sort(key=lambda x:x[0])
for i in range(N-1):
    side.append([city[i+1][0] - city[i][0],city[i][2] ,city[i+1][2]])

city.sort(key=lambda x:x[1])
for i in range(N-1):
    side.append([city[i+1][1] - city[i][1],city[i][2] ,city[i+1][2]])
side.sort()
node = [[i,[i]]for i in range(N)]
ans = 0
for cost,a,b in side:
    if node[a][0] != node[b][0]:
        ans += cost
        c,d = node[node[a][0]],node[node[b][0]]
        if len(c[1]) < len(d[1]):
            for i in c[1]:
                node[i][0] = d[0]
            d[1] = d[1] + c[1]
        else:
            for i in d[1]:
                node[i][0] = c[0]
            c[1] = d[1] + c[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
import heapq
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
xy = [IL() + [i] for i in range(N)]

xroot = [[] for _ in range(N+1)]
yroot = [[] for _ in range(N+1)]

xlist = sorted(xy, key=itemgetter(0)) # [x, y, ID]
ylist = sorted(xy, key=itemgetter(1))
for i in range(N-1):
  x, hoge, xID = xlist[i]
  nextx, hoge, nextxID = xlist[i + 1]
  costx = abs(x - nextx)
  xroot[xID].append([costx, nextxID])
  xroot[nextxID].append([costx, xID])

  hoge, y, yID = ylist[i]
  hoge, nexty, nextyID = ylist[i + 1]
  costy = abs(y - nexty)
  yroot[yID].append([costy, nextyID])
  yroot[nextyID].append([costy, yID])
#print(xroot) # [cost, rootID]
#print(yroot)

hpop = heapq.heappop
hpush = heapq.heappush
data = [] # [val, ID]

visited = [False]*(N+1)
hpush(data, [0, 0])
ans = 0
while data:
  val, num = hpop(data)
  if visited[num] == False:
    visited[num] = True
    #print(val, num)
    ans += val
    for i in xroot[num]:
      if visited[i[1]] == False:
        hpush(data, i)
    for j in yroot[num]:
      if visited[j[1]] == False:
        hpush(data, j)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import heapq

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

xroot = [[] for _ in range(N+1)]
yroot = [[] for _ in range(N+1)]

xlist = sorted(xy, key=itemgetter(0)) # [x, y, ID]
ylist = sorted(xy, key=itemgetter(1))
for i in range(N-1):
  x, hoge, xID = xlist[i]
  nextx, hoge, nextxID = xlist[i + 1]
  costx = abs(x - nextx)
  xroot[xID].append([costx, nextxID])
  xroot[nextxID].append([costx, xID])

  hoge, y, yID = ylist[i]
  hoge, nexty, nextyID = ylist[i + 1]
  costy = abs(y - nexty)
  yroot[yID].append([costy, nextyID])
  yroot[nextyID].append([costy, yID])
#print(xroot) # [cost, rootID]
#print(yroot)

hpop = heapq.heappop
hpush = heapq.heappush
data = [] # [Val, ID]

visited = [False]*(N+1)
hpush(data, [0, 0])
ans = 0
while data:
  val, num = hpop(data)
  if visited[num] == False:
    visited[num] = True
    #print(val, num)
    ans += val
    for i in xroot[num]:
      hpush(data, i)
    for j in yroot[num]:
      hpush(data, j)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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+1])
    Y.append([y,i+1])
X.append([-10**9,0])
Y.append([-10**9,0])
X.append([10**16,N+1])
Y.append([10**16,N+1])

X.sort()
Y.sort()

DX={}
for i in range(N+2):
    DX[X[i][1]]=i
DY={}
for i in range(N+2):
    DY[Y[i][1]]=i
#print(DX)
#print(DY)

C=[1 for i in range(N+2)]
C[0]=0
C[-1]=0

ans=0
import heapq
Q=[]
P=1
Q.append((X[DX[P]][0]-X[DX[P]-1][0],X[DX[P]-1][1]))
Q.append((X[DX[P]+1][0]-X[DX[P]][0],X[DX[P]+1][1]))
Q.append((Y[DY[P]][0]-Y[DY[P]-1][0],Y[DY[P]-1][1]))
Q.append((Y[DY[P]+1][0]-Y[DY[P]][0],Y[DY[P]+1][1]))
C[P]=0
heapq.heapify(Q)
for i in range(10**7):
    if len(Q)==0:
        break
    elif C[Q[0][1]]==0:
        heapq.heappop(Q)
    else:
        q=heapq.heappop(Q)
        ans+=q[0]
        #print(ans,q,Q)
        
        C[q[1]]=0
        P=q[1]
        #print(X[DX[P]-1],X[DX[P]+1],Y[DY[P]-1],Y[DY[P]+1])
        if C[X[DX[P]-1][1]]==1:
            heapq.heappush(Q,(X[DX[P]][0]-X[DX[P]-1][0],X[DX[P]-1][1]))
        if C[X[DX[P]+1][1]]==1:
            heapq.heappush(Q,(X[DX[P]+1][0]-X[DX[P]][0],X[DX[P]+1][1]))
        if C[Y[DY[P]-1][1]]==1:
            heapq.heappush(Q,(Y[DY[P]][0]-Y[DY[P]-1][0],Y[DY[P]-1][1]))
        if C[Y[DY[P]+1][1]]==1:
            heapq.heappush(Q,(Y[DY[P]+1][0]-Y[DY[P]][0],Y[DY[P]+1][1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import heapq
from heapq import heappush, heappop
global G

def input_graph(N, xy):
  global G
  comb_list = list(itertools.combinations(xy, 2))
  for i in range(N*(N-1)//2):
    a, b = comb_list[i]
    an, axy = a
    ax, ay = axy
    bn, bxy = b 
    bx, by = bxy
    cost = min(abs(ax-bx), abs(ay-by))
    G[an] += [(cost, bn)]
    G[bn] += [(cost, an)]

def prim(V):
  global G, used 
  edgelist = []
  for e in G[0]:
    heappush(edgelist, e)
  used[0] = True
  res = 0
  while edgelist:
    minedge = heappop(edgelist)
    if used[minedge[1]]:
      continue 
    v = minedge[1]
    used[v] = True 
    for e in G[v]:
      if not used[e[1]]:
        heappush(edgelist, e)
    res += minedge[0]
  return res

def main():
  global G, used
  N = int(input())
  xy = []
  for i in range(N):
    xy += [[i, list(map(int, input().split()))]]
  G = [[] for _ in range(N)]
  used = [False for _ in range(N)]
  input_graph(N, xy)
  print(prim(N))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
from heapq import heappush, heappop
global G

def input_graph(N, xy):
  global G
  for i in range(N):
    ax, ay = xy[i]
    for j in range(i+1, N):
      bx, by = xy[j]
      cost = min(abs(ax-bx), abs(ay-by))
      G[i] += [(cost, j)]
      G[j] += [(cost, i)]
  
def prim(V):
  global G, used 
  edgelist = []
  for e in G[0]:
    heappush(edgelist, e)
  used[0] = True
  res = 0
  while edgelist:
    minedge = heappop(edgelist)
    if used[minedge[1]]:
      continue 
    v = minedge[1]
    used[v] = True 
    for e in G[v]:
      if not used[e[1]]:
        heappush(edgelist, e)
    res += minedge[0]
  return res


def main():
  global G, used
  N = int(input())
  xy = [list(map(int, input().split())) for _ in range(N)]
  G = [[] for _ in range(N)]
  used = [False for _ in range(N)]
  input_graph(N, xy)
  print(prim(N))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
import bisect
import heapq
N=int(input())
L=[]
L.append([-10**9,-10**9,0])
X=[]
X.append([-10**9,-10**9,0])
Y=[]
Y.append([-10**9,-10**9,0])
C=[0]*(N+2)
C[0]=1
C[-1]=1

for i in range(N):
    x,y=map(int,input().split())
    L.append([x,y,i+1])
    X.append([x,y,i+1])
    Y.append([y,x,i+1])
X.sort()
Y.sort()
L.append([10**15,10**15,N+1])
X.append([10**15,10**15,N+1])
Y.append([10**15,10**15,N+1])
#print(L)
#print(X)
#print(Y)
ans=0
P=1
C[P]=1
Q=[]
X1=bisect.bisect_left(X,L[P])+1
X2=bisect.bisect_right(X,L[P])-2
l=[L[P][1],L[P][0],L[P][2]]
Y1=bisect.bisect_left(Y,l)+1
Y2=bisect.bisect_right(Y,l)-2
if C[X[X1][2]]==0:
    Q.append([abs(X[X1][0]-X[X1-1][0]),X[X1][2],P])
if C[X[X2][2]]==0:
    Q.append([abs(X[X2][0]-X[X2+1][0]),X[X2][2],P])
if C[Y[Y1][2]]==0:
    Q.append([abs(Y[Y1][0]-Y[Y1-1][0]),Y[Y1][2],P])
if C[Y[Y2][2]]==0:
    Q.append([abs(Y[Y2][0]-Y[Y2+1][0]),Y[Y2][2],P])
#print("Q",Q)
heapq.heapify(Q)
for i in range(10**10):
    
    if len(Q)==0:
        break
    else:
        if C[Q[0][1]]==1:
            heapq.heappop(Q)
        else:
            #print("i",i,ans,Q)
            C[Q[0][1]]=1
            P=Q[0][1]
            ans+=Q[0][0]
            #print("a",ans,"Q",Q)
            heapq.heappop(Q)
            X1=bisect.bisect_left(X,L[P])+1
            X2=bisect.bisect_right(X,L[P])-2
            l=[L[P][1],L[P][0],L[P][2]]
            #print("l",l)
            Y1=bisect.bisect_left(Y,l)+1
            Y2=bisect.bisect_right(Y,l)-2
            #print("C",X[X1][2],X[X2][2],Y[Y1][2],Y[Y2][2],C,Y[Y2],Y[Y2+1])
            if C[X[X1][2]]==0:
                heapq.heappush(Q,[abs(X[X1][0]-X[X1-1][0]),X[X1][2],P])
            if C[X[X2][2]]==0:
                heapq.heappush(Q,[abs(X[X2][0]-X[X2+1][0]),X[X2][2],P])
            if C[Y[Y1][2]]==0:
                heapq.heappush(Q,[abs(Y[Y1][0]-Y[Y1-1][0]),Y[Y1][2],P])
            if C[Y[Y2][2]]==0:
                heapq.heappush(Q,[abs(Y[Y2][0]-Y[Y2+1][0]),Y[Y2][2],P])
            #print("ans",ans,"Q",Q,C)
print(ans)
#print(C)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
import bisect
import heapq
N=int(input())
L=[]
L.append([-10**9,-10**9,0])
X=[]
X.append([-10**9,-10**9,0])
Y=[]
Y.append([-10**9,-10**9,0])
C=[0]*(N+2)
C[0]=1
C[-1]=1

for i in range(N):
    x,y=map(int,input().split())
    L.append([x,y,i+1])
    X.append([x,y,i+1])
    Y.append([y,x,i+1])
X.sort()
Y.sort()
L.append([10**15,10**15,N+1])
X.append([10**15,10**15,N+1])
Y.append([10**15,10**15,N+1])
#print(L)
#print(X)
#print(Y)
ans=0
P=1
C[P]=1
Q=[]
X1=bisect.bisect_left(X,L[P])+1
X2=bisect.bisect_right(X,L[P])-2
l=[L[P][1],L[P][0],L[P][2]]
Y1=bisect.bisect_left(Y,l)+1
Y2=bisect.bisect_right(Y,l)-2
if C[X[X1][2]]==0:
    Q.append([abs(X[X1][0]-X[X1-1][0]),X[X1][2],P])
if C[X[X2][2]]==0:
    Q.append([abs(X[X2][0]-X[X2+1][0]),X[X2][2],P])
if C[Y[Y1][2]]==0:
    Q.append([abs(Y[Y1][0]-Y[Y1-1][0]),Y[Y1][2],P])
if C[Y[Y2][2]]==0:
    Q.append([abs(Y[Y2][0]-Y[Y2+1][0]),Y[Y2][2],P])
#print("Q",Q)
heapq.heapify(Q)
for i in range(10**10):
    
    if len(Q)==0:
        break
    else:
        if C[Q[0][1]]==1:
            heapq.heappop(Q)
        else:
            #print("i",i,ans,Q)
            C[Q[0][1]]=1
            P=Q[0][1]
            ans+=Q[0][0]
            #print("a",ans,"Q",Q)
            heapq.heappop(Q)
            X1=bisect.bisect_left(X,L[P])+1
            X2=bisect.bisect_right(X,L[P])-2
            l=[L[P][1],L[P][0],L[P][2]]
            #print("l",l)
            Y1=bisect.bisect_left(Y,l)+1
            Y2=bisect.bisect_right(Y,l)-2
            #print("C",X[X1][2],X[X2][2],Y[Y1][2],Y[Y2][2],C,Y[Y2],Y[Y2+1])
            if C[X[X1][2]]==0:
                heapq.heappush(Q,[abs(X[X1][0]-X[X1-1][0]),X[X1][2],P])
            if C[X[X2][2]]==0:
                heapq.heappush(Q,[abs(X[X2][0]-X[X2+1][0]),X[X2][2],P])
            if C[Y[Y1][2]]==0:
                heapq.heappush(Q,[abs(Y[Y1][0]-Y[Y1-1][0]),Y[Y1][2],P])
            if C[Y[Y2][2]]==0:
                heapq.heappush(Q,[abs(Y[Y2][0]-Y[Y2+1][0]),Y[Y2][2],P])
            #print("ans",ans,"Q",Q,C)
print(ans)
#print(C)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(2000000000)
 
n = int(input())
nodes = []
done = [0 for _ in range(n)]
par = {}
for _ in range(n):
    x, y = map(int,input().split())
    nodes.append((x,y))
    par[(x,y)]=(x,y)
nodesx = sorted(nodes)
nodesy = sorted(nodes,key=lambda z:z[1])
s = []
 
for i in range(n-1):
    xcost =nodesx[i+1][0]-nodesx[i][0]
    ycost =nodesy[i+1][1]-nodesy[i][1]
    s.append((xcost,(nodesx[i+1],nodesx[i])))
    s.append((ycost,(nodesy[i+1],nodesy[i])))
s.sort()
def root(node,par):
    if node == par[node]:
        return node
    else:
        par[node] =root(par[node],par)
        return par[node]
def unite(node1,node2,par):
    par[root(node1,par)] = root(node2,par)
ans = 0
count =0
for cost,(node1,node2) in s:
    if count == n-1:
        break
    root1 =root(node1,par)
    root2 =root(node2,par)
    if root1 != root2:
        unite(node1,node2,par)
        ans +=cost
        count += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
position = [[]for i in range(n)]
for i in range(n):
    a, b= MAP()
    position[i] = (a, b)

def prim():
    res = 0
    used = [False]*n
    que = []
    heapq.heapify(que)
    used[0] = True
    for i in range(1, n):
        distance = min(abs(position[0][0]-position[i][0]), abs(position[0][1]-position[i][1]))
        heapq.heappush(que,(distance,i))
    while(len(que) > 0):
        cost, vertex = heapq.heappop(que)
        if used[vertex]:continue
        res += cost
        used[vertex] = True
        for i in range(n):
            if used[i]:continue
            distance = min(abs(position[vertex][0]-position[i][0]), abs(position[vertex][1]-position[i][1]))
            heapq.heappush(que,(distance, i))
    return res

print(prim())

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import heapq
def prim_heap():
  used=[True]*n
  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

import sys
input=sys.stdin.readline
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
edge=[[] for i in range(n)]
l.sort()
for i in range(n):
  l[i]=[l[i][0],l[i][1],i]
for i in range(n-1):
  edge[i].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i+1])
  edge[i+1].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i])
l=sorted(l,key=itemgetter(1))
for i in range(n-1):
  edge[l[i][2]].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i+1][2]])
  edge[l[i+1][2]].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i][2]])
print(prim_heap())

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import heapq
def prim_heap():
  used=[True]*n
  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())
l=[list(map(int,input().split())) for i in range(n)]
edge=[[] for i in range(n)]
l.sort()
for i in range(n):
  l[i]=[l[i][0],l[i][1],i]
for i in range(n-1):
  edge[i].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i+1])
  edge[i+1].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i])
l=sorted(l,key=itemgetter(1))
for i in range(n-1):
  edge[l[i][2]].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i+1][2]])
  edge[l[i+1][2]].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i][2]])
print(prim_heap())