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:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    x, a, b = LI()
    if b <= a:
        print("delicious")
    elif b <= a + x:
        print("safe")
    else:
        print("dangerous")

    return

#B
def B():
    n = II()
    a = IR(n)
    check = [False] * (n + 1)
    check[1] = True
    now = a[0]
    for i in range(1,n+1):
        if check[now]:
            break
        if now == 2:
            print(i)
            return
        check[now] = True
        now = a[now - 1]
    print(-1)
    return

#C
def C():
    return

#D
def D():
    def find(x):
        if x == par[x]:
            return x
        par[x] = find(par[x])
        return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y: return False
        par[y] = x
        return True
    def solve():
        for i in range(n-1):
            x, y, z = xy[i]
            vx, vy, v = xy[i + 1]
            z, v = min(z, v), max(z, v)
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
    n = II()
    par = [i for i in range(n)]
    xy = [None] * n
    for i in range(n):
        x, y = LI()
        xy[i] = (x, y, i)
    xy.sort()
    edg = defaultdict(int)
    solve()
    xy.sort(key=lambda x: x[1])
    solve()
    ans = 0
    a = 0
    for key, value in sorted(edg.items(), key=lambda x: x[1]):
        if a == n:
            break
        p0, p1 = key
        if unite(p0, p1):
            a += 1
            ans += value
    print(ans)

    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    x, a, b = LI()
    if b <= a:
        print("delicious")
    elif b <= a + x:
        print("safe")
    else:
        print("dangerous")

    return

#B
def B():
    n = II()
    a = IR(n)
    check = [False] * (n + 1)
    check[1] = True
    now = a[0]
    for i in range(1,n+1):
        if check[now]:
            break
        if now == 2:
            print(i)
            return
        check[now] = True
        now = a[now - 1]
    print(-1)
    return

#C
def C():
    return

#D
def D():
    def find(x):
        if x == par[x]:
            return x
        par[x] = find(par[x])
        return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y: return False
        par[y] = x
        return True
    def solve():
        for i in range(n-1):
            x, y, z = xy[i]
            vx, vy, v = xy[i + 1]
            z, v = min(z, v), max(z, v)
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
    n = II()
    par = [i for i in range(n)]
    xy = []
    for i in range(n):
        x, y = LI()
        xy.append((x, y, i))
    xy.sort()
    edg = defaultdict(int)
    solve()
    xy.sort(key=lambda x: x[1])
    solve()
    ans = 0
    a = 0
    for key, value in sorted(edg.items(), key=lambda x: x[1]):
        if a == n:
            break
        p0, p1 = key
        if unite(p0, p1):
            a += 1
            ans += value
    print(ans)

    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    x, a, b = LI()
    if b <= a:
        print("delicious")
    elif b <= a + x:
        print("safe")
    else:
        print("dangerous")

    return

#B
def B():
    n = II()
    a = IR(n)
    check = [False] * (n + 1)
    check[1] = True
    now = a[0]
    for i in range(1,n+1):
        if check[now]:
            break
        if now == 2:
            print(i)
            return
        check[now] = True
        now = a[now - 1]
    print(-1)
    return

#C
def C():
    return

#D
def D():
    def find(x):
        if x == par[x]:
            return x
        par[x] = find(par[x])
        return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y: return False
        par[y] = x
        return True
    def solve():
        for i in range(n):
            x, y, z = xy[i]
            if i == 0:
                vx, vy, v = xy[i + 1]
                edg[(z, v)] = min(abs(vx - x), abs(vy - y))
            elif i == n - 1:
                vx, vy, v = xy[i - 1]
                edg[(z, v)] = min(abs(vx - x), abs(vy - y))
            else:
                vx, vy, v = xy[i + 1]
                edg[(z, v)] = min(abs(vx - x), abs(vy - y))
                vx, vy, v = xy[i - 1]
                edg[(z, v)] = min(abs(vx - x), abs(vy - y))
    n = II()
    par = [i for i in range(n)]
    xy = []
    for i in range(n):
        x, y = LI()
        xy.append((x, y, i))
    xy.sort()
    edg = defaultdict(int)
    solve()
    xy.sort(key=lambda x: x[1])
    solve()
    ans = 0
    a = 0
    for key, value in sorted(edg.items(), key=lambda x: x[1]):
        if a == n:
            break
        p0, p1 = key
        if unite(p0, p1):
            a += 1
            ans += value
    print(ans)

    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    x, a, b = LI()
    if b <= a:
        print("delicious")
    elif b <= a + x:
        print("safe")
    else:
        print("dangerous")

    return

#B
def B():
    n = II()
    a = IR(n)
    check = [False] * (n + 1)
    check[1] = True
    now = a[0]
    for i in range(1,n+1):
        if check[now]:
            break
        if now == 2:
            print(i)
            return
        check[now] = True
        now = a[now - 1]
    print(-1)
    return

#C
def C():
    return

#D
def D():
    def find(x):
        if x == par[x]:
            return x
        par[x] = find(par[x])
        return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y: return False
        par[y] = x
        return True
    n = II()
    par = [i for i in range(n)]
    xy = []
    for i in range(n):
        x, y = LI()
        xy.append((x, y, i))
    xy.sort()
    edg = defaultdict(int)
    for i in range(n):
        x, y, z = xy[i]
        if i == 0:
            vx, vy, v = xy[i + 1]
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
        elif i == n - 1:
            vx, vy, v = xy[i - 1]
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
        else:
            vx, vy, v = xy[i + 1]
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
            vx, vy, v = xy[i - 1]
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
    xy.sort(key=lambda x: x[1])
    for i in range(n):
        x, y, z = xy[i]
        if i == 0:
            vx, vy, v = xy[i + 1]
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
        elif i == n - 1:
            vx, vy, v = xy[i - 1]
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
        else:
            vx, vy, v = xy[i + 1]
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
            vx, vy, v = xy[i - 1]
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
    ans = 0
    a = 0
    for key, value in sorted(edg.items(), key=lambda x: x[1]):
        if a == n:
            break
        p0, p1 = key
        if unite(p0, p1):
            a += 1
            ans += value
    print(ans)

    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    x, a, b = LI()
    if b <= a:
        print("delicious")
    elif b <= a + x:
        print("safe")
    else:
        print("dangerous")

    return

#B
def B():
    n = II()
    a = IR(n)
    check = [False] * (n + 1)
    check[1] = True
    now = a[0]
    for i in range(1,n+1):
        if check[now]:
            break
        if now == 2:
            print(i)
            return
        check[now] = True
        now = a[now - 1]
    print(-1)
    return

#C
def C():
    return

#D
def D():
    def find(x):
        if x == par[x]:
            return x
        par[x] = find(par[x])
        return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y: return False
        par[y] = x
        return True
    n = II()
    par = [i for i in range(n)]
    xy = []
    for i in range(n):
        x, y = LI()
        xy.append((x, y, i))
    xy.sort()
    edg = defaultdict(int)
    for i in range(n):
        x, y, z = xy[i]
        if i == 0:
            vx, vy, v = xy[i + 1]
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
        elif i == n - 1:
            vx, vy, v = xy[i - 1]
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
        else:
            vx, vy, v = xy[i + 1]
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
            vx, vy, v = xy[i - 1]
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
    xy.sort(key=lambda x: x[1])
    for i in range(n):
        x, y, z = xy[i]
        if i == 0:
            vx, vy, v = xy[i + 1]
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
        elif i == n - 1:
            vx, vy, v = xy[i - 1]
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
        else:
            vx, vy, v = xy[i + 1]
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
            vx, vy, v = xy[i - 1]
            edg[(z, v)] = min(abs(vx - x), abs(vy - y))
    ans = 0
    for key, value in sorted(edg.items(), key=lambda x: x[1]):
        p0,p1 = key
        if unite(p0, p1):
            ans += value
    print(ans)

    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    x, a, b = LI()
    if b <= a:
        print("delicious")
    elif b <= a + x:
        print("safe")
    else:
        print("dangerous")

    return

#B
def B():
    n = II()
    a = IR(n)
    check = [False] * (n + 1)
    check[1] = True
    now = a[0]
    for i in range(1,n+1):
        if check[now]:
            break
        if now == 2:
            print(i)
            return
        check[now] = True
        now = a[now - 1]
    print(-1)
    return

#C
def C():
    return

#D
def D():
    def find(x):
        if x == par[x]:
            return x
        par[x] = find(par[x])
        return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y: return False
        par[y] = x
        return True
    n = II()
    par = [i for i in range(n)]
    xy = []
    coordinate = defaultdict(list)
    for i in range(n):
        x, y = LI()
        coordinate[i] = (x, y)
        xy.append((x, y, i))
    xy.sort()
    edg = defaultdict(int)
    for i in range(n):
        x, y, z = xy[i]
        if i == 0:
            v = xy[i + 1][2]
            edg[(z, v)] = min(abs(coordinate[v][0] - x), abs(coordinate[v][1] - y))
        elif i == n - 1:
            v = xy[i - 1][2]
            edg[(z, v)] = min(abs(coordinate[v][0] - x), abs(coordinate[v][1] - y))
        else:
            v = xy[i - 1][2]
            edg[(z, v)] = min(abs(coordinate[v][0] - x), abs(coordinate[v][1] - y))
            v = xy[i + 1][2]
            edg[(z, v)] = min(abs(coordinate[v][0] - x), abs(coordinate[v][1] - y))
    xy.sort(key=lambda x: x[1])
    for i in range(n):
        x, y, z = xy[i]
        if i == 0:
            v = xy[i + 1][2]
            edg[(z, v)] = min(abs(coordinate[v][0] - x), abs(coordinate[v][1] - y))
        elif i == n - 1:
            v = xy[i - 1][2]
            edg[(z, v)] = min(abs(coordinate[v][0] - x), abs(coordinate[v][1] - y))
        else:
            v = xy[i - 1][2]
            edg[(z, v)] = min(abs(coordinate[v][0] - x), abs(coordinate[v][1] - y))
            v = xy[i + 1][2]
            edg[(z, v)] = min(abs(coordinate[v][0] - x), abs(coordinate[v][1] - y))
    ans = 0
    for key, value in sorted(edg.items(), key=lambda x: x[1]):
        p0,p1 = key
        if unite(p0, p1):
            ans += value
    print(ans)

    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


import heapq
def prim_heap(n, edges):  # n: 最大の頂点番号+1, edges[頂点番号]=[[重み, 行き先],[重み, 行き先],...]. 無向グラフの場合は相方向有向グラフの表記にしておく。
    seen = [False] * n #True:不使用
    edgelist = []  # heapq
    for e in edges[0]:  # 頂点 0 から伸びる辺をすべて heapq に入れる。
        heapq.heappush(edgelist,(e, 0))  # 一応、どこから来たかの情報を持っておく。
    seen[0] = True  # 頂点 0 は見たと記録する。
    # res_edges = []  # 辺を記録するためのリスト。これを記録することで若干性能が悪くなっている（n=10**6で100msぐらい）ので、不要なら除く。
    res = 0  # 最小全域木の辺の重みの合計。
    while len(edgelist) != 0:
        minedge, start = heapq.heappop(edgelist)  # edgelist から最小の辺を1つ取り出す。
        if seen[minedge[1]]:  # その辺の行き先がすでに見た先だったら棄却して次へ。
            continue
        v = minedge[1]  # 行き先を v とする。
        seen[v] = True  # 頂点 v は見たと記録する。
        for e in edges[v]:  # 頂点 v から伸びる辺すべてについて、もしその行き先を見ていなかったら heapq に追加する。
            if not seen[e[1]]:
                heapq.heappush(edgelist,(e, v))
        # res_edges.append((start, v, minedge[0]))  # Edge: (from, to, weight)
        res += minedge[0]  # いま使った辺の重みを結果に加える。
    # print(res_edges)  # 最小全域木の辺を print する。
    # return res_edges  # 最小全域木の辺を返す。
    return res  # 最小全域木の全体の重みを返す。



def main(): 
    N = II()
    pos_li = []
    for i in range(N):
        x,y = LI()
        pos_li.append((x,y,i))
    edges = [[] for _ in range(N)]
    # # すべての頂点を結ぶグラフを作ってその最小全域木を取ると、時間が足りない（二重ループが O(10^10)）。
    # for i in range(N):
    #     for j in range(N):
    #         weight = min(abs(pos_li[i][0] - pos_li[j][0]), abs(pos_li[i][1] - pos_li[j][1]))
    #         edges[i].append([weight, j])
    #         edges[j].append([weight, i])
    # # なので、座標でソートして、最も近い4点のみへ辺を伸ばす。
    pos_li.sort(key=lambda x: x[0])
    for k in range(N-1):
        x1, y1, p1 = pos_li[k]
        x2, y2, p2 = pos_li[k+1]
        weight = abs(x1-x2)
        edges[p1].append([weight, p2])
        edges[p2].append([weight, p1])

    pos_li.sort(key=lambda x: x[1])
    for k in range(N-1):
        x1, y1, p1 = pos_li[k]
        x2, y2, p2 = pos_li[k+1]
        weight = abs(y1-y2)
        edges[p1].append([weight, p2])
        edges[p2].append([weight, p1])

    # print(edges)
    print(prim_heap(N, edges))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


import heapq
def prim_heap(n, edges):  # n: 最大の頂点番号+1, edges[頂点番号]=[[重み, 行き先],[重み, 行き先],...]. 無向グラフの場合は相方向有向グラフの表記にしておく。
    used = [True] * n #True:不使用
    edgelist = []  # heapq
    for e in edges[0]:  # 頂点 0 から伸びる辺をすべて heapq に入れる。
        heapq.heappush(edgelist,e)
    used[0] = False  # 頂点 0 は見たと記録する。
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)  # edgelist から最小の辺を1つ取り出す。
        if not used[minedge[1]]:  # その辺の行き先がすでに見た先だったら棄却して次へ。
            continue
        v = minedge[1]  # 行き先を v とする。
        used[v] = False  # 頂点 v は見たと記録する。
        for e in edges[v]:  # 頂点 v から伸びる辺すべてについて、もしその行き先を見ていなかったら heapq に追加する。
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]  # いま使った辺の重みを結果に加える。
    return res  # 最小全域木の全体の重みを出力する。



def main(): 
    N = II()
    pos_li = []
    for _ in range(N):
        pos_li.append(LI())
    edges = [[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            weight = min(abs(pos_li[i][0] - pos_li[j][0]), abs(pos_li[i][1] - pos_li[j][1]))
            edges[i].append([weight, j])
            edges[j].append([weight, i])

    # print(edges)
    print(prim_heap(N, edges))


main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
pt=[]
qt=[]
for i in range(n):
  pt.append(list(map(int,input().split())))
qt.append(pt[0])
pt.pop(0)
ans=0
for k in range(n-1):
  min_num=1000000000
  min_t=0
  for i in range(len(qt)):
    for j in range(len(pt)):
      if min_num>min(abs(qt[i][0]-pt[j][0]),abs(qt[i][1]-pt[j][1])):
        min_num=min(abs(qt[i][0]-pt[j][0]),abs(qt[i][1]-pt[j][1]))
        min_t=j
  ans+=min_num     
  qt.append(pt[min_t])
  pt.pop(min_t)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納　par[x] == x の時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0)
        self.rank = [0] * (n+1)
        # 各々の集合の要素数（根が代表して値を持っておく）
        self.count = [1] * (n+1)

    # 検索
    def find(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        # 根でないなら親の要素で再検索
        else:
            # 検索する過程で親を更新
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        t = (x == y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        return t


    # 同じ集合に属しているか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 属している集合の要素数
    def size(self,x):
        q = UnionFind.find(self,x)
        return self.count[q]

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

data.sort()
edge = []
append = edge.append
for i in range(1,n):
    append([data[i][0]-data[i-1][0],data[i][2],data[i-1][2]])
data.sort(key=lambda x:x[1])
for i in range(1,n):
    append([data[i][1]-data[i-1][1],data[i][2],data[i-1][2]])

edge.sort()
uf = UnionFind(n)
ans = 0
for x,y,z in edge:
    if not uf.same_check(y,z):
        uf.union(y,z)
        ans += x

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
xys = []
for i in range(N):
  x, y = map(int, input().split())
  xys.append((x, y))
Isx = sorted(range(N), key=lambda i: (xys[i][0], xys[i][1]))
Isy = sorted(range(N), key=lambda i: (xys[i][1], xys[i][0]))
#print(Isx)
#print(Isy)
M = set()
for i in range(N):
  p, q = Isx[i-1], Isx[i]
  a, b = xys[p]
  c, d = xys[q]
  cost = min(abs(a-c), abs(b-d))
  M.add((cost, p, q))
for i in range(N):
  p, q = Isy[i-1], Isy[i]
  a, b = xys[p]
  c, d = xys[q]
  cost = min(abs(a-c), abs(b-d))
  M.add((cost, p, q))
#print(M)
F = [{i} for i in range(N)]
S = list(M)
S.sort(reverse=True)
#print(S)
r = 0
while S:
  cost, p, q = S.pop()
  for i in range(N):
    s = F[i]
    if p in s:
      break
  for j in range(N):
    s = F[j]
    if q in s:
      break
  #print(i, j)
  if i != j:
    r += cost
    s = F[i]|F[j]
    F.pop(max(i, j))
    F.pop(min(i, j))
    F.append(s)
  #print(F)
print(r)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import lil_matrix

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

G = lil_matrix((N, N))

for j in [1, 2]:
  iXY.sort(key=lambda a: a[j])
  for i in range(1, N):
    i0, x0, y0 =  iXY[i - 1]
    i1, x1, y1 =  iXY[i]
    G[i0, i1] = min(abs(x1 - x0), abs(y1 - y0))

mst = minimum_spanning_tree(G)
print(int(mst.sum()))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
import heapq
INF = float("inf")


class Graph(object):

    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """
        args:
          edge : (from_, to_, weight)
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  # 無向グラフを仮定。逆向きにも辺を張る


class UnionFind(object):
    """UnionFind木
    """

    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def Kruskal(g):
    edges = []
    for from_ in range(g.N):
        for to_, weight in g.E[from_]:
            heapq.heappush(edges, [weight, from_, to_])

    tree = Graph(g.N)
    group = UnionFind(g.N)
    while len(edges) > 0:
        w_, f_, t_ = heapq.heappop(edges)
        if not group.same(f_, t_):
            tree.add_edge([f_, t_, w_])
            group.unite(f_, t_)
    return tree


def solve(N: int, x: "List[int]", y: "List[int]"):

    g = Graph(N)
    XYN = sorted(zip(x, y, range(N)))
    YXN = sorted(zip(y, x, range(N)))
    g = Graph(N)
    for i in range(N-1):
        x1, y1, n1 = XYN[i]
        x2, y2, n2 = XYN[i+1]
        g.add_edge([n1, n2, min(abs(x1-x2), abs(y1-y2))])
        x1, y1, n1 = YXN[i]
        x2, y2, n2 = YXN[i+1]
        g.add_edge([n1, n2, min(abs(y1-y2), abs(x1-x2))])

    tree = Kruskal(g)

    tot = 0
    for f in range(N):
        for t, w in tree.E[f]:
            tot += w
    print(tot//2)

    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:
#!/usr/bin/env python3
import sys
import heapq
INF = float("inf")


class Graph(object):

    def __init__(self, N):
        self.N = N
        self.E = []

    def add_edge(self, edge):
        """
        args:
          edge : (from_, to_, weight)
        """
        s, t, w = edge
        if s > t:
            s, t = t, s
        self.E.append([s, t, w])


class UnionFind(object):
    """UnionFind木
    """

    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def solve(N: int, x: "List[int]", y: "List[int]"):

    XYN = sorted(zip(x, y, range(N)))
    YXN = sorted(zip(y, x, range(N)))
    edges = []
    for i in range(N-1):
        (x1, y1, n1), (x2, y2, n2) = XYN[i:i+2]
        heapq.heappush(edges, [min(abs(x1-x2), abs(y1-y2)), n1, n2])
        (y1, x1, n1), (y2, x2, n2) = YXN[i:i+2]
        heapq.heappush(edges, [min(abs(x1-x2), abs(y1-y2)), n1, n2])
    tot, counter = 0, 0
    group = UnionFind(N)
    while len(edges) > 0 and counter <= N:
        w, f, t = heapq.heappop(edges)
        if not group.same(f, t):
            tot += w
            counter += 1
            group.unite(f, t)

    print(tot)
    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()