Problem:


Score : 500 points

Problem Statement

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

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

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

Constraints

2 ≤ N ≤ 10^5

0 ≤ x_i,y_i ≤ 10^9

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

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

Sample Input 1

3
1 5
3 9
7 8

Sample Output 1

3

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

Sample Input 2

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

Sample Output 2

8



Sample input:
3
1 5
3 9
7 8


Sample output:
3

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
import heapq

def solve():
    input = sys.stdin.readline
    N = int(input())
    town = dict()
    road = [None] * N
    roadx, roady = [None] * N, [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        town[(x, y)] = i
        road[i] = (x, y)
        roadx[i] = (x, y)
        roady[i] = (x, y)
    roadx.sort()
    roadx_id = dict()
    roady.sort(key = itemgetter(1))
    roady_id = dict()
    for i in range(N):
        roadx_id[roadx[i]] = i
        roady_id[roady[i]] = i

    visited = [False] * N
    q = []
    heapq.heapify(q)
    heapq.heappush(q, (0, 0)) #(cost, town_id)
    cost = 0
    while q:
        add_cost, id = heapq.heappop(q)
        #print(add_cost, id, cost)
        #print(visited)
        if not visited[id]:
            cost += add_cost
            visited[id] = True
            for s in range(2):
                nx = roadx_id[road[id]] + (-1) ** s #roadxにおけるid
                if 0 <= nx < N:
                    if not visited[town[roadx[nx]]]: heapq.heappush(q, (min(abs(road[id][0] - roadx[nx][0]), abs(road[id][1] - roadx[nx][1])), town[roadx[nx]]))
                
                ny = roady_id[road[id]] + (-1) ** s #roadyにおけるid
                if 0 <= ny < N:
                    if not visited[town[roady[ny]]]: heapq.heappush(q, (min(abs(road[id][1] - roady[ny][1]), abs(road[id][1] - roady[ny][1])), town[roady[ny]]))
    
    print(cost)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
import heapq

def solve():
    input = sys.stdin.readline
    N = int(input())
    town = dict()
    road = [None] * N
    roadx, roady = [None] * N, [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        town[(x, y)] = i
        road[i] = (x, y)
        roadx[i] = (x, y)
        roady[i] = (x, y)
    roadx.sort()
    roadx_id = dict()
    roady.sort(key = itemgetter(1))
    roady_id = dict()
    for i in range(N):
        roadx_id[roadx[i]] = i
        roady_id[roady[i]] = i

    visited = [False] * N
    q = []
    heapq.heapify(q)
    heapq.heappush(q, (0, 0)) #(cost, town_id)
    cost = 0
    while q:
        add_cost, id = heapq.heappop(q)
        #print(add_cost, id, cost)
        #print(visited)
        if not visited[id]:
            cost += add_cost
            visited[id] = True
            for s in range(2):
                nx = roadx_id[road[id]] + (-1) ** s #roadxにおけるid
                if 0 <= nx < N:
                    if not visited[town[roadx[nx]]]: heapq.heappush(q, (abs(road[id][0] - roadx[nx][0]), town[roadx[nx]]))
                
                ny = roady_id[road[id]] + (-1) ** s #roadyにおけるid
                if 0 <= ny < N:
                    if not visited[town[roady[ny]]]: heapq.heappush(q, (abs(road[id][1] - roady[ny][1]), town[roady[ny]]))
    
    print(cost)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N=int(input())
x,y=map(list,zip(*[list(map(int,input().split())) for i in range(N)]))
x=sorted(zip(x,range(N)))
y=sorted(zip(y,range(N)))
from heapq import heappop,heappush
qx,qy=[(10**9+1,0,0)],[(10**9+1,0,0)]
for i in range(N-1):
    heappush(qx,(x[i+1][0]-x[i][0],x[i][1],x[i+1][1]))
    heappush(qy,(y[i+1][0]-y[i][0],y[i][1],y[i+1][1]))
r=0
s=set()
ss=0
while ss<N:
    d,i,j=heappop(qx) if qx[0]<qy[0] else heappop(qy)
    s.add(i)
    s.add(j)
    if ss<len(s):
        ss=len(s)
        r+=d
print(r)

Submission status: Wrong Answer

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 same(x, y):
        return find(x) == find(y)
    def unite(x, y):
        x = find(x)
        y = find(y)
        par[y] = x
        return True
    n = II()
    par = [i for i in range(n)]
    xy = [None] * n
    for i in range(n):
        xy[i] = LI()+[i]
    xy.sort(key=lambda x: x[0])
    edg = [None] * (2 * n - 2)
    a = 0
    print(xy)
    for i in range(n-1):
        edg[a + i] = [xy[i + 1][0] - xy[i][0], xy[i][2], xy[i + 1][2]]
    xy.sort(key=lambda x: x[1])
    a = n - 1
    for i in range(n-1):
        edg[a + i] = [xy[i + 1][1] - xy[i][1], xy[i][2], xy[i + 1][2]]
    ans = 0
    a = 0
    edg.sort(key=lambda x: x[0])
    for i in range(2 * n - 2):
        value, p0, p1 = edg[i]
        if a == n - 1:
            break
        if not same(p0, p1):
            unite(p0, p1)
            a += 1
            ans += value
    print(ans)
    return

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

Submission status: Wrong Answer

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 same(x, y):
        return find(x) == find(y)
    def unite(x, y):
        x = find(x)
        y = find(y)
        par[y] = x
        return True
    n = II()
    par = [i for i in range(n)]
    xy = [None] * n
    for i in range(n):
        xy[i] = LI()+[i]
    xy.sort(key=lambda x: x[0])
    edg = [None] * (2 * n - 2)
    a = 0
    print(xy)
    for i in range(n-1):
        edg[a + i] = [xy[i][0] - xy[i + 1][0], xy[i][2], xy[i + 1][2]]
    xy.sort(key=lambda x: x[1])
    a = n - 1
    for i in range(n-1):
        edg[a + i] = [xy[i][1] - xy[i + 1][1], xy[i][2], xy[i + 1][2]]
    ans = 0
    a = 0
    edg.sort(key=lambda x: x[0])
    for i in range(2 * n - 2):
        value, p0, p1 = edg[i]
        if a == n - 1:
            break
        if not same(p0, p1):
            unite(p0, p1)
            a += 1
            ans += value
    print(ans)
    return

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

Submission status: Wrong Answer

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 find(x):
    if x == par[x]:
        return x
    par[x] = find(par[x])
    return par[x]
def same(x, y):
    return find(x) == find(y)
def unite(x, y):
    x = find(x)
    y = find(y)
    par[y] = x
    return True
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(key=lambda x: x[0])
edg = [None] * (2 * n - 2)
a = 0
for i in range(n-1):
    edg[a + i] = [xy[i][0] - xy[i + 1][0], xy[i][2], xy[i + 1][2]]
xy.sort(key=lambda x: x[1])
a = n - 1
for i in range(n-1):
    edg[a + i] = [xy[i][1] - xy[i + 1][1], xy[i][2], xy[i + 1][2]]
ans = 0
a = 0
edg.sort(key=lambda x: x[0])
for i in range(2 * n - 2):
    value, p0, p1 = edg[i]
    if a == n - 1:
        break
    if not same(p0, p1):
        unite(p0, p1)
        a += 1
        ans += value
print(ans)

Submission status: Wrong Answer

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 same(x, y):
        return find(x) == find(y)
    def unite(x, y):
        x = find(x)
        y = find(y)
        par[y] = x
        return True
    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(key=lambda x: x[0])
    edg = [None] * (2 * n - 2)
    a = 0
    for i in range(n-1):
        edg[a + i] = [xy[i][0] - xy[i+1][0], xy[i][2], xy[i+1][2]]
    xy.sort(key=lambda x: x[1])
    a = n - 1
    for i in range(n-1):
        edg[a + i] = [xy[i][1] - xy[i+1][1], xy[i][2], xy[i+1][2]]
    ans = 0
    a = 0
    edg.sort(key=lambda x: x[0])
    for i in range(2 * n - 2):
        value, p0, p1 = edg[i]
        if a == n - 1:
            break
        if not same(p0, p1):
            unite(p0, p1)
            a += 1
            ans += value
    print(ans)
    return

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

Submission status: Wrong Answer

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 same(x, y):
        return find(x) == find(y)
    def unite(x, y):
        x = find(x)
        y = find(y)
        par[y] = x
        return True
    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(key=lambda x: x[0])
    edg = [None] * (2 * n - 2)
    a = 0
    for i in range(n-1):
        edg[a + i] = [xy[i][0] - xy[i+1][0], xy[i][2], xy[i][2]]
    xy.sort(key=lambda x: x[1])
    a = n - 1
    for i in range(n-1):
        edg[a + i] = [xy[i][1] - xy[i+1][1], xy[i][2], xy[i][2]]
    ans = 0
    a = 0
    edg.sort(key=lambda x: x[0])
    for i in range(2 * n - 2):
        value, p0, p1 = edg[i]
        if a == n - 1:
            break
        if not same(p0, p1):
            unite(p0, p1)
            a += 1
            ans += value
    print(ans)
    return

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

Submission status: Wrong Answer

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]
                z, v = min(z, v), max(z, v)
                edg[(z, v)] = min(abs(vx - x), abs(vy - y))
            elif i == n - 1:
                vx, vy, v = xy[i - 1]
                z, v = min(z, v), max(z, v)
                edg[(z, v)] = min(abs(vx - x), abs(vy - y))
            else:
                vx, vy, v = xy[i + 1]
                z, v = min(z, v), max(z, v)
                edg[(z, v)] = min(abs(vx - x), abs(vy - y))
                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: Wrong Answer

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


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


for index in range(1, 3):
    xy_list.sort(key=lambda i:i[index])
    for i in range(n-1):
        p = xy_list[i][0]
        q = xy_list[i+1][0]
        cost = xy_list[i + 1][index] - xy_list[i][index]
        graph[p][q] += [cost]
        graph[q][p] += [cost]



print(graph)



def prim(n, graph):
    mincost = [float("inf")] * n
    mincost[0] = 0
    used = [False] * n
    used[0] = True
    tmp = 0
    for i in range(n):
        v = tmp
        for j in range(n):
            k = float('inf')
            if not used[j] and graph[v][j]:
                mincost[j] = min(mincost[j], *graph[v][j])
                if k > mincost[j]:
                    k = mincost[j]
                tmp = j
            used[v] = True
    return sum(mincost)


print(prim(n, graph))

Submission status: Wrong Answer

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

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

P = []
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]
    P.append((min(abs(x1 - x0), abs(y1 - y0)), i0, i1))

d, i, j = zip(*P)
G = csr_matrix((d, (i, j)), shape=(N, N))
mst = minimum_spanning_tree(G)
print(int(mst.sum()))

Submission status: Wrong Answer

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

iXY.sort(key=lambda a: a[1])
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))

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [[int(i) for i in input().split()] for _ in range(N)]

M = 0

xy.sort()
xl, yl = xy[0]
xr, yr = xy[-1]
for i in range(N) :
    x, y = xy[i]
    M = max(M, min(abs(x-xl), abs(y-yl)))
    M = max(M, min(abs(xr-x), abs(yr-y)))

xy.sort(key=lambda x: x[1])
xb, yb = xy[0]
xt, yt = xy[-1]
for i in range(N) :
    x, y = xy[i]
    M = max(M, min(abs(x-xb), abs(y-yb)))
    M = max(M, min(abs(xt-x), abs(yt-y)))
    
print(M)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [[int(i) for i in input().split()] for _ in range(N)]

M = 0

xy.sort()
xl, yl = xy[0]
for i in range(1, N) :
    x, y = xy[i]
    M = max(M, min(x-xl, y-yl))

xy.sort(key=lambda x: x[1])
xb, yb = xy[0]
for i in range(1, N) :
    x, y = xy[i]
    M = max(M, min(x-xb, y-yb))
    
print(M)

Submission status: Wrong Answer

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

#時間計測テスト4

N = I()
x = []
y = []

for i in range(N):
  xtemp,ytemp = II()
  x.append([xtemp, i])
  y.append([ytemp, i])

x.sort(key = lambda a:a[0])
y.sort(key = lambda a:a[0])

Submission status: Wrong Answer

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

#時間計測テスト3

N = I()
x = []
y = []

for i in range(N):
  xtemp,ytemp = II()
  x.append([xtemp, i])
  y.append([ytemp, i])

x.sort()
y.sort()

Submission status: Wrong Answer

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

#時間計測テスト2

N = I()
x = []
y = []

for i in range(N):
  xtemp,ytemp = II()
  x.append([xtemp, i])
  y.append([ytemp, i])

xsort = sorted(x)
ysort = sorted(y)

Submission status: Wrong Answer

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

#時間計測テスト

N = I()
x = []
y = []

for i in range(N):
  xtemp,ytemp = II()
  x.append([xtemp, i])
  y.append([ytemp, i])

xsort = sorted(x,lambda a:a[0])
ysort = sorted(y,lambda a:a[0])

Submission status: Wrong Answer

Solution code:
def set(a, b):
  R[a].append(b)
  R[b].append(a)

N = int(input())
xy = [[i] + list(map(int, input().split())) for i in range(N)]
R = [[] for _ in range(N)]
xy.sort(key = lambda x: x[1])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  set(a[0], b[0])
xy.sort(key = lambda x: x[2])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  set(a[0], b[0])

xy.sort()
import heapq
q = [[0, 0]]
L = [True] * N
pop = heapq.heappop
push = heapq.heappush
ans = 0
exit()
for _ in range(N):
  k, t = pop(q)
  while not L[t]:
    k, t = pop(q)
  L[t] = False
  ans += k
  for i in R[t]:
    if L[i]:
      x = abs(xy[t][1] - xy[i][1])
      x = min(x, abs(xy[t][2] - xy[i][2]))
      push(q, [x, i])
print(ans)

Submission status: Wrong Answer

Solution code:
#test
def set(a, b, d):
  if D[a][b] == -1 or D[a][b] > d:
    D[a][b] = d
    R[a].append(b)
  if D[b][a] == -1 or D[b][a] > d:
    D[b][a] = d
    R[b].append(a)

N = int(input())
xy = [list(map(int, input().split())) for i in range(N)]
R = [[] for _ in range(N)]
D = [[-1] * N for _ in range(N)]
exit()
xy.sort(key = lambda x: x[1])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  d = abs(a[1] - b[1])
  set(a[0], b[0], d)
xy.sort(key = lambda x: x[2])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  d = abs(a[2] - b[2])
  set(a[0], b[0], d)

import heapq
q = [[0, 0]]
L = [True] * N
pop = heapq.heappop
push = heapq.heappush
ans = 0

for _ in range(N):
  k, t = pop(q)
  while not L[t]:
    k, t = pop(q)
  L[t] = False
  ans += k
  for i in R[t]:
    if L[i]:
      push(q, [D[t][i], i])
print(ans)

Submission status: Wrong Answer

Solution code:
#test
def set(a, b, d):
  if D[a][b] == -1 or D[a][b] > d:
    D[a][b] = d
    R[a].append(b)
  if D[b][a] == -1 or D[b][a] > d:
    D[b][a] = d
    R[b].append(a)

N = int(input())
xy = [[i] + list(map(int, input().split())) for i in range(N)]
R = [[] for _ in range(N)]
D = [[-1] * N for _ in range(N)]
exit()
xy.sort(key = lambda x: x[1])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  d = abs(a[1] - b[1])
  set(a[0], b[0], d)
xy.sort(key = lambda x: x[2])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  d = abs(a[2] - b[2])
  set(a[0], b[0], d)

import heapq
q = [[0, 0]]
L = [True] * N
pop = heapq.heappop
push = heapq.heappush
ans = 0

for _ in range(N):
  k, t = pop(q)
  while not L[t]:
    k, t = pop(q)
  L[t] = False
  ans += k
  for i in R[t]:
    if L[i]:
      push(q, [D[t][i], i])
print(ans)

Submission status: Wrong Answer

Solution code:
#test
def set(a, b, d):
  R[a].append(b)
  R[b].append(a)
  D[a][b] = min(D[a][b], d)
  D[b][a] = min(D[b][a], d)

N = int(input())
xy = [[i] + list(map(int, input().split())) for i in range(N)]
M = 10 ** 20
R = [[] for _ in range(N)]
D = [[M] * N for _ in range(N)]
xy.sort(key = lambda x: x[1])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  d = abs(a[1] - b[1])
  set(a[0], b[0], d)
xy.sort(key = lambda x: x[2])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  d = abs(a[2] - b[2])
  set(a[0], b[0], d)

import heapq
q = [[0, 0]]
L = [True] * N
pop = heapq.heappop
push = heapq.heappush
ans = 0
exit()

for _ in range(N):
  k, t = pop(q)
  while not L[t]:
    k, t = pop(q)
  L[t] = False
  ans += k
  for i in R[t]:
    if L[i]:
      push(q, [D[t][i], i])
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


def main():
    from collections import deque

    n = int(input())
    xy = list()

    for i in range(n):
        xi, yi = map(int, input().split())
        xy.append((i, xi, yi))

    x_asc = sorted(xy, key=lambda x: x[1])
    y_asc = sorted(xy, key=lambda x: x[2])
    g = [[] for _ in range(n)]

    for i in range(n - 1):
        diff = x_asc[i + 1][1] - x_asc[i][1]
        start = x_asc[i + 1][0]
        end = x_asc[i][0]
        g[start].append((end, diff))
        g[end].append((start, diff))

        diff = y_asc[i + 1][2] - y_asc[i][2]
        start = y_asc[i + 1][0]
        end = y_asc[i][0]
        g[start].append((end, diff))
        g[end].append((start, diff))

    visited = set()
    length = 0
    d = deque()
    i = 0
    d.append(i)
    ans = [10 ** 10 for _ in range(n)]

    while d and i < n:
        vi = d.popleft()
        shortest = 10 ** 10
        next_vi = -1

        for edge, dist in g[vi]:
            if dist < shortest:
                shortest = dist
                next_vi = edge

        visited.add((i, next_vi))
        visited.add((next_vi, i))
        m = len(visited)

        if m == length:
            continue

        length = m
        ans[i] = min(ans[i], shortest)
        i += 1
        d.append(i)

    print(sum(ans) - 10 ** 10)


if __name__ == '__main__':
    main()