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:
class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1

from itertools import chain
from bisect import bisect

N = int(input())
points = tuple(tuple(map(int,input().split())) for _ in range(N))
ds = DisjointSet(N)

x_i = sorted((x,i) for i,(x,y) in enumerate(points))
y_i = sorted((y,i) for i,(x,y) in enumerate(points))

xr = [x_i[0]]
yr = [y_i[0]]

for (x0,i0),(x1,i1) in zip(x_i,x_i[1:]):
    if x0 == x1:
        ds.union(i0,i1)
    else:
        xr.append((x1,i1))

for (y0,i0),(y1,i1) in zip(y_i,y_i[1:]):
    if y0 == y1:
        ds.union(i0,i1)
    else:
        yr.append((y1,i1))

print('test')

deltas = sorted(
        chain(
            ((x1-x0,i0,i1) for (x0,i0), (x1,i1) in zip(xr,xr[1:])),
            ((y1-y0,i0,i1) for (y0,i0), (y1,i1) in zip(yr,yr[1:])),
        )
    )


def it():
    for d,i0,i1 in deltas:
        if ds.find(i0) != ds.find(i1):
            ds.union(i0,i1)
            yield d
print(sum(it()))

Submission status: Wrong Answer

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

n = int(input()) 
ixy = [[i] + [int(x) for x in input().split()] for i in range(n)]

edge = []

for key in [itemgetter(1),itemgetter(2)]:
    ixy.sort(key = key)
    for i in range(n-1):
        i1, i2 = ixy[i][0], ixy[i+1][0]
        x1, x2 = ixy[i][1], ixy[i+1][1]
        y1, y2 = ixy[i][2], ixy[i+1][2]
        d = min(abs(x2-x1), abs(y2-y1))
        edge.append([i1,i2,d])
    
row,col,value = zip(*edge)
csr_ = csr_matrix((value, (row,col)), shape=(n, n))
mst = minimum_spanning_tree(csr_, overwrite=True).astype(int)
print(mst.sum())

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] + [int(x) for x in input().split()] for i in range(n)]

edge = []

ixy.sort(key=lambda x:x[1])
for i in range(n-1):
    i1, i2 = ixy[i][0], ixy[i+1][0]
    x1, x2 = ixy[i][1], ixy[i+1][1]
    y1, y2 = ixy[i][2], ixy[i+1][2]
    d = min(abs(x2-x1), abs(y2-y1))
    edge.append([i1,i2,d])
    
ixy.sort(key=lambda x:x[2])
for i in range(n-1):
    i1, i2 = ixy[i][0], ixy[i+1][0]
    x1, x2 = ixy[i][1], ixy[i+1][1]
    y1, y2 = ixy[i][2], ixy[i+1][2]
    d = min(abs(x2-x1), abs(y2-y1))
    edge.append([i1,i2,d])

row,col,value = zip(*edge)
csr_ = csr_matrix((value, (row,col)), shape=(n, n))
mst = minimum_spanning_tree(csr_, overwrite=True).astype(int)
print(mst.sum())

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] + [int(x) for x in input().split()] for i in range(n)]

f = []
t = []
d = []

ixy = sorted(ixy, key=lambda x:x[1])
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d.append(min(abs(ixy[i+1][1] - ixy[i][1]), abs(ixy[i+1][2] - ixy[i][2])))
    f.append(j)
    t.append(k)
    
ixy = sorted(ixy, key=lambda x:x[2])
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d.append(min(abs(ixy[i+1][1] - ixy[i][1]), abs(ixy[i+1][2] - ixy[i][2])))
    t.append(k)
    f.append(j)

csr_ = csr_matrix((d, (f, t)), shape=(n, n))
mst = minimum_spanning_tree(csr_, overwrite = True).astype(int)
print(mst.sum())

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] + [int(x) for x in input().split()] for i in range(n)]

f = []
t = []
d = []

ixy = sorted(ixy, key=lambda x:x[1])
print(ixy)
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d.append(min(abs(ixy[i+1][1] - ixy[i][1]), abs(ixy[i+1][2] - ixy[i][2])))
    f.append(j)
    t.append(k)
    
ixy = sorted(ixy, key=lambda x:x[2])
print(ixy)
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d.append(min(abs(ixy[i+1][1] - ixy[i][1]), abs(ixy[i+1][2] - ixy[i][2])))
    t.append(k)
    f.append(j)

csr_ = csr_matrix((d, (f, t)), shape=(n, n))
mst = minimum_spanning_tree(csr_, overwrite = True).astype(int)
print(mst.sum())

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] + [int(x) for x in input().split()] for i in range(n)]

f = []
t = []
d = []

ixy = sorted(ixy, key=lambda x:(x[1], x[2]))
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d.append(min(abs(ixy[i+1][1] - ixy[i][1]), abs(ixy[i+1][2] - ixy[i][2])))
    f.append(j)
    t.append(k)

ixy = sorted(ixy, key=lambda x:(x[2], x[1]))
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d.append(min(abs(ixy[i+1][1] - ixy[i][1]), abs(ixy[i+1][2] - ixy[i][2])))
    t.append(k)
    f.append(j)

csr_ = csr_matrix((d, (f, t)), shape=(n, n))
mst = minimum_spanning_tree(csr_).astype(int)
print(mst.sum())

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] + [int(x) for x in input().split()] for i in range(n)]
f = []
t = []
d = []

ixy = sorted(ixy, key=lambda x:(x[1], x[2]))
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d.append(ixy[i+1][1] - ixy[i][1])
    f.append(j)
    t.append(k)

ixy = sorted(ixy, key=lambda x:(x[2], x[1]))
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d.append(ixy[i+1][2] - ixy[i][2])
    t.append(k)
    f.append(j)

csr_ = csr_matrix((d, (f, t)), shape=(n, n))
mst = minimum_spanning_tree(csr_).astype(int)
print(mst.sum())

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] + [int(x) for x in input().split()] for i in range(n)]
f = []
t = []
d = []

ixy = sorted(ixy, key=lambda x:(x[1], x[2]))
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d.append(ixy[i+1][1] - ixy[i][1])
    t.append(k)
    f.append(j)

ixy = sorted(ixy, key=lambda x:(x[2], x[1]))
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d.append(ixy[i+1][2] - ixy[i][2])
    t.append(k)
    f.append(j)

csr_ = csr_matrix((d, (f, t)), shape=(n, n))
mst = minimum_spanning_tree(csr_)
print(int(mst.sum()))

Submission status: Wrong Answer

Solution code:
import heapq

def myprim_heap(graph, n):
    #始点sから各頂点への最短距離
    INF = 10**9
    d = [INF] * n
    used = [False] * n #True:未確定
    s = 0
    d[s] = 0
    used[s] = True
    res = 0
    edgelist = []
    for e in graph[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if used[minedge[1]]:
            continue
        res += minedge[0]
        v = minedge[1]
        used[v] = True
        for e in graph[v]:
            if not used[e[1]]:
                heapq.heappush(edgelist, e)
    return res


n = int(input()) 
graph = [[] for _ in range(n)]
ixy = [[i] + [int(x) for x in input().split()] for i in range(n)]

ixy = sorted(ixy, key=lambda x:(x[1], x[2]))
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d = ixy[i+1][1] - ixy[i+1][1]
    graph[j].append([d,k])
    graph[k].append([d,j])

ixy = sorted(ixy, key=lambda x:(x[2], x[1]))
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d = ixy[i+1][2] - ixy[i][2]
    graph[j].append([d,k])
    graph[k].append([d,j])

res = myprim_heap(graph, n)
print(res)

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
place = []
d = {}
j = 0
for i in range(N):
    x, y = map(int, input().split())
    place.append((x,y))
    if not (x,y) in d:
        d[(x,y)] = j
        j += 1
N = j

sort_x = sorted(place)
sort_y = sorted(place, key = lambda k:k[1])

edge=[[] for i in range(N)]
flag = False
for i in range(N-1):
    x,y = sort_x[i+1]
    now = d[(x,y)]
    before_x, before_y = sort_x[i]
    before = d[(before_x,before_y)]
    edge[before].append([x-before_x,now])
    edge[now].append([x-before_x,d[(before_x,before_y)]])

for i in range(N-1):
    x,y = sort_y[i+1]
    now = d[(x,y)]
    before_x, before_y = sort_y[i]
    before = d[(before_x,before_y)]
    edge[before].append([y-before_y,now])
    edge[now].append([y-before_y,before])

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]

print(res)

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
place = []
d = {}
for i in range(N):
    x, y = map(int, input().split())
    place.append((x,y))
    d[(x,y)] = i

sort_x = sorted(place)
sort_y = sorted(place, key = lambda k:k[1])

edge=[[] for i in range(N)]
flag = False
for x,y in sort_x:
    now = d[(x,y)]
    if flag:
        edge[before].append([x-before_x,now])
        edge[now].append([x-before_x,d[(before_x,before_y)]])
    else:
        flag = True
    before_x = x
    before_y = y
    before = now

flag = False
for x,y in sort_y:
    now = d[(x,y)]
    if flag:
        edge[before].append([y-before_y,now])
        edge[now].append([y-before_y,before])
    else:
        flag = True
    before_x = x
    before_y = y
    before = now

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]

print(res)

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
place = []
d = {}
for i in range(N):
    x, y = map(int, input().split())
    place.append((x,y))
    d[(x,y)] = i

sort_x = sorted(place)
sort_y = sorted(place, key = lambda k:k[1])

edge=[[] for i in range(N)]
flag = False
for x,y in sort_x:
    if flag:
        edge[d[(before_x,before_y)]].append([min(abs(x-before_x),abs(y-before_y)),d[(x,y)]])
        edge[d[(x,y)]].append([min(abs(x-before_x),abs(y-before_y)),d[(before_x,before_y)]])
    else:
        flag = True
    before_x = x
    before_y = y

for x,y in sort_y:
    if flag:
        edge[d[(before_x,before_y)]].append([min(abs(x-before_x),abs(y-before_y)),d[(x,y)]])
        edge[d[(x,y)]].append([min(abs(x-before_x),abs(y-before_y)),d[(before_x,before_y)]])
    else:
        flag = True
    before_x = x
    before_y = y

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]

print(res)

Submission status: Wrong Answer

Solution code:
# プリム法
import heapq
N = int(input())
town = []
for i in range(N):
    x,y = map(int,input().split())
    town.append((x-1,y-1))
q = []
used = [0]*N
ans = 0
# 頂点どれでもいいので根を0とする
# 全ての街に対して道があると考える
heapq.heappush(q, (0, 0))
while len(q)>0:
    price, nowTown = heapq.heappop(q)
    used[nowTown] = 1
    ans += price
    a,b = town[nowTown]
    for j in range(N):
        if used[j] == 0:
            c,d = town[j]
            minPrice = min(abs(a-c), abs(b-d))
            heapq.heappush(q, (minPrice, j))
print(price)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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


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

e = []
for i in range(N-1):
    e.append([abs(x[i][0]-x[i+1][0]), x[i][1], x[i+1][1]])
    e.append([abs(y[i][0]-y[i+1][0]), y[i][1], y[i+1][1]])

e.sort()

#uft = UnionFind(N)
v = {}
ans = 0
for w, s, t in e:
    if s not in v or t not in v:
        ans += w
        v[s] = 1
        v[t] = 1

print(ans)

Submission status: Wrong Answer

Solution code:

from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix

def resolve():
    N = int(input())
    X = []
    Y = []
    # 町のナンバーも付ける
    for i in range(N):
        x, y = map(int, input().split())
        X.append((i, x))
        Y.append((i, y))

    # 短い距離にある街をつなげば良いのでソートする
    X.sort(key=lambda x: x[1])
    Y.sort(key=lambda x: x[1])

    # コストを計算しグラフを作成
    G = []
    for i in range(1, N):
        a, x1 = X[i - 1]
        b, x2 = X[i]
        G.append((a, b, x2 - x1))
        a, y1 = Y[i - 1]
        b, y2 = Y[i]
        G.append((a, b, y2 - y1))

    G.sort(key=lambda x: x[2])
    A, B, W = zip(*G)
    csr = csr_matrix((W, (A, B)), shape=(N, N))
    mst = minimum_spanning_tree(csr).astype(int)
    print(mst.sum())

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:

from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix

def resolve():
    N = int(input())
    X = []
    Y = []
    # 町のナンバーも付ける
    for i in range(N):
        x, y = map(int, input().split())
        X.append((i, x))
        Y.append((i, y))

    # 短い距離にある街をつなげば良いのでソートする
    X.sort(key=lambda x: x[1])
    Y.sort(key=lambda x: x[1])

    # コストを計算しグラフを作成
    G = []
    for i in range(1, N):
        a, x1 = X[i - 1]
        b, x2 = X[i]
        G.append((a, b, x2 - x1))
        a, y1 = Y[i - 1]
        b, y2 = Y[i]
        G.append((a, b, y2 - y1))

    A, B, W = zip(*G)
    csr = csr_matrix((W, (A, B)), shape=(N, N))
    mst = minimum_spanning_tree(csr).astype(int)
    print(mst.sum())

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

lx = sorted(l)
ly = sorted(l, key=lambda x: x[1])

e = []
for i in range(n-1):
    e.append([lx[i+1][0]-lx[i][0],lx[i+1][2],lx[i][2]])
    e.append([ly[i+1][1]-ly[i][1],ly[i+1][2],ly[i][2]])


class Unionfind:
    
    def __init__(self,n):
        self.uf = [-1]*n

    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]

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

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x

    def size(self,x):
        x = self.find(x)
        return -self.uf[x]
s = set()
u = Unionfind(n)
count = 0
e.sort()
for i in e:
    if u.find(i[1]) != u.find(i[2]):
        u.union(i[1],i[2])
        s.add(i[1])
        s.add(i[2])
        count += i[0]
    if len(s) == n:
        print(count)
        exit()

Submission status: Wrong Answer

Solution code:
n= int(input())
par = [-1]*n
grouping = [0]
#grouped = [False]*n
def find(x):
    if par[x]<0:return x
    else:
        par[x]=find(par[x])
        return par[x]

def unite(x,y):
    px,py=find(x),find(y)
    if px==py:return False
    else:
        if px<py:px,py=py,px
        par[px]+=par[py]
        par[py]=px
        grouping[0]+=1
        return True

xy=set()
for i in range(n):
    x,y= map(int,input().split())
    xy.add((x,y,i))
distdic = {}
xyx= sorted(xy, key=lambda x: x[0])
for i in range(n-1):
    lx,ln=xyx[i][0],  xyx[i][2]
    rx,rn=xyx[i+1][0],xyx[i+1][2]
    distdic[rx-lx] = distdic.get(rx-lx,[]) + [(ln,rn)]
xyy= sorted(xy, key=lambda x: x[1])
for i in range(len(xyy)-1):
    uy,un=xyy[i][1],  xyy[i][2]
    dy,dn=xyy[i+1][1],xyy[i+1][2]
    distdic[dy-uy] = distdic.get(dy-uy,[]) + [(un,dn)]

gcost=0
for adist in sorted(distdic.keys()):
    for case in distdic[adist]:
        (px,py) = case
        if unite(px,py):gcost += adist
        print(grouping,par)
        if grouping[0]==n-1:break
    if grouping[0]==n-1:break
print(gcost)

Submission status: Wrong Answer

Solution code:
# kotae mita
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
def main():
    N = int(input())
    l = []
    for i in range(N):
        x, y = map(int, input().split())
        l.append((x,y,i))
    X = sorted(l, key=lambda x:x[0])
    Y = sorted(l, key=lambda x:x[1])
    w = []
    p = []
    q = []
    for i in range(N-1):
        w.append(abs(X[i][0]-X[i+1][0]))
        p.append(X[i][2])
        q.append(X[i+1][2])
        w.append(abs(Y[i][1]-Y[i+1][1]))
        p.append(Y[i][2])
        q.append(Y[i+1][2])
    csr = csr_matrix((w, (p,q)), shape=(N,N))
    return int(minimum_spanning_tree(csr).sum())
print(main())

Submission status: Wrong Answer

Solution code:
import heapq
class Graph:
    def __init__(self,v,edgelist,w_v = None,directed = False):
        super().__init__()
        self.v = v
        self.w_e = [{} for _ in [0]*self.v]
        self.neighbor = [[] for _ in [0]*self.v]
        self.w_v = w_v
        self.directed = directed

        for i,j,w in edgelist:
            self.w_e[i][j] = w
            self.neighbor[i].append(j)

    def dijkstra(self,v_n):
        d = [float('inf')]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

    def warshallFloyd(self):
        d = [[10**18]*self.v for _ in [0]*self.v]
        for i in range(self.v):
            d[i][i] = 0
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
        
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    check = d[i][k] + d[k][j]
                    if d[i][j] > check:
                        d[i][j] = check
        return d

    def prim(self):
        gb = GraphBuilder(self.v,self.directed)

        queue = []
        for i,w in self.w_e[0].items(): heapq.heappush(queue,(w,0,i))
        rest = [True]*self.v
        rest[0] = False

        while len(queue)>0:
            w,i,j = heapq.heappop(queue)
            if rest[j]:
                gb.addEdge(i,j,w)
                rest[j] = False
                for k,w in self.w_e[j].items():
                    heapq.heappush(queue,(w,j,k))

        return gb

class Tree():
    def __init__(self,v,e):
        pass

class GraphBuilder():
    def __init__(self,v,directed = False):
        self.v = v
        self.directed = directed
        self.edge = []

    def addEdge(self,i,j,w=1):
        if not self.directed:
            self.edge.append((j,i,w))
        self.edge.append((i,j,w))

    def addEdges(self,edgelist,weight = True):
        if weight:
            if self.directed:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
            else:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
                    self.edge.append((j,i,w))
        else:
            if self.directed:
                for i,j,w in edgelist:
                    self.edge.append((i,j,1))
            else:
                for i,j,w in edgelist:
                    self.edge.append((i,j,1))
                    self.edge.append((j,i,1))
            

    def addAdjMat(self, mat):
        for i,mat_i in enumerate(mat):
            for j,w in enumerate(mat_i):
                self.edge.append((i,j,w))

    def buildTree(self):
        pass

    def buildGraph(self):
        return Graph(self.v,self.edge,directed=self.directed)

def main():

    n= int(input())
    edge = []
    for i in range(n):
      x,y = list(map(int,input().split()))
      edge.append((x,y,i))
    
    xs = sorted(edge,key=lambda a:a[0])
    ys = sorted(edge,key=lambda a:a[1])

    edge = []
    
    for i in range(n-1):
      x1,y1,p1 = xs[i]
      x2,y2,p2 = xs[i+1]
      edge.append((p1,p2,min(x2-x1,y2-y1)))
      
      x1,y1,p1 = ys[i]
      x2,y2,p2 = ys[i+1]
      edge.append((p1,p2,y2-y1))
      
      
    gb = GraphBuilder(n)
    gb.addEdges(edge)

    mint = gb.buildGraph().prim()
    print(mint.edge)
    ans = 0
    for a in mint.edge:
      ans+=a[2]
    print(ans//2)
      
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import coo_matrix

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

row = []
col = []
cost = []

for key in (itemgetter(0), itemgetter(1)):
    xy.sort(key=key)
    for (x1, y1, i1), (x2, y2, i2) in zip(xy, xy[1:]):
        row.append(i1)
        col.append(i2)
        cost.append(min(abs(x1 - x2), abs(y1 - y2)))

graph = coo_matrix((cost, (row, col)), shape=(n, n))
mst = minimum_spanning_tree(graph, overwrite=True).astype(int)
ans = mst.sum()
print(ans)

Submission status: Wrong Answer

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

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

xyi = [[x, y, i] for i, (x, y) in enumerate(xy)]
row = []
col = []
cost = []

xyi.sort()
for (x1, y1, i1), (x2, y2, i2) in zip(xyi, xyi[1:]):
    row.append(i1)
    col.append(i2)
    cost.append(min(abs(x1 - x2), abs(y1 - y2)))

xyi.sort(key=itemgetter(1))
for (x1, y1, i1), (x2, y2, i2) in zip(xyi, xyi[1:]):
    row.append(i1)
    col.append(i2)
    cost.append(min(abs(x1 - x2), abs(y1 - y2)))

graph = csr_matrix((cost, (row, col)), shape=(n, n))
mst = minimum_spanning_tree(graph, overwrite=True).astype(int)
ans = mst.sum()
print(ans)

Submission status: Wrong Answer

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

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

xyi = [[x, y, i] for i, (x, y) in enumerate(xy)]
row = []
col = []
cost = []

xyi.sort()
for (x1, y1, i1), (x2, y2, i2) in zip(xyi, xyi[1:]):
    row.append(i1)
    col.append(i2)
    cost.append(min(abs(x1 - x2), abs(y1 - y2)))

xyi.sort(key=itemgetter(1))
for (x1, y1, i1), (x2, y2, i2) in zip(xyi, xyi[1:]):
    row.append(i1)
    col.append(i2)
    cost.append(min(abs(x1 - x2), abs(y1 - y2)))

graph = csr_matrix((cost, (row, col)), shape=(n, n))
mst = minimum_spanning_tree(graph).astype(int)
ans = mst.sum()
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
di = {(xy[i][0], xy[i][1]):i for i in range(n)}
xy = sorted(xy, key=lambda x:x[0])
graph = [[] for _ in range(n)]
for i in range(n-1):
  graph[di[(xy[i][0], xy[i][1])]] += [[abs(xy[i][0]-xy[i+1][0]), di[(xy[i+1][0], xy[i+1][1])] ]]
  graph[di[(xy[i+1][0], xy[i+1][1])]] += [[abs(xy[i][0]-xy[i+1][0]), di[(xy[i][0], xy[i][1])]]]

xy = sorted(xy, key=lambda x:x[1])
for i in range(n-1):
  graph[di[(xy[i][0], xy[i][1])]] += [[abs(xy[i][1]-xy[i+1][1]), di[(xy[i+1][0], xy[i+1][1])] ]]
  graph[di[(xy[i+1][0], xy[i+1][1])]] += [[abs(xy[i][1]-xy[i+1][1]), di[(xy[i][0], xy[i][1])]]]


def prim():
  # graph[i]は第一要素が重み、第二要素が頂点になるように
  # graph[s] += [[w, t]], w:重み, s,t:頂点
  used = [-1]*n
  edgelist = []
  for e in graph[0]:
    heapq.heappush(edgelist, e)
  used[0] = 1
  res = 0
  while edgelist:
    minedge = heapq.heappop(edgelist)
    if used[minedge[1]] == 1:
      continue 
    v = minedge[1]
    used[v] = 1
    for e in graph[v]:
      if used[e[1]] == -1:
        heapq.heappush(edgelist, e)
    res += minedge[0]
  return res

t = prim()
print(t)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    cost = []
    for _ in range(N):
        x,y = map(int,input().split())
        cost.append((x,y))
    dist = [2**60 for _ in range(N)]
    cost.sort()
    dist[0] = 0
    for i in range(1,N):
        dist[i] = min(dist[i],dist[i-1]+min(abs(cost[i][0]-cost[i-1][0]),abs(cost[i][1]-cost[i-1][1])))
        dist[i] = min(dist[i],min(abs(cost[0][0]-cost[i][0]),abs(cost[0][1]-cost[i][1])))
    ans = max(dist)
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
import math
import sys
input = sys.stdin.readline
#文字列のときはうまく行かないのでコメントアウトすること
sys.setrecursionlimit(2147483647)

def main():
  n = int(input())
  x = [0]*n
  y = [0]*n
  for i in range(n):
    x[i], y[i] = map(int, input().split())
  cost = [[0 for i in range(n)] for j in range(n)]
  for i in range(n):
    cost[i][i] = 0
    for j in range(i+1, n):
      cost[i][j] = min(abs(x[i]-x[j]),abs(y[i]-y[j]))
      cost[j][i] = cost[i][j]
  csr = csr_matrix(cost)
  mst = minimum_spanning_tree(csr, overwrite=True)
  print(mst.astype(int).sum())
  
  
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
n = int(input())
stw = []
x_list = []
y_list = []
for i in range(n):
  x, y = map(int, input().split())
  x_list += [[x, i]]
  y_list += [[y, i]]
x_list.sort()
y_list.sort()
"""
for i in range(n-1):
  xs = x_list[i][1]
  xt = x_list[i+1][1]
  ys = y_list[i][1]
  yt = y_list[i+1][1]
  dis_x = abs(x_list[i][0]-x_list[i+1][0])
  dis_y = abs(y_list[i][0]-y_list[i+1][0])
  stw += [[dis_x, xs, xt]]
  #stw += [[dis_x, xt, xs]]
  stw += [[dis_y, ys, yt]]
  #stw += [[dis_y, yt, ys]]
"""
for [u, fr], [v, to] in zip(x_list, x_list[1:]):
  stw += [[abs(u-v), fr, to]]
for [u, fr], [v, to] in zip(y_list, y_list[1:]):
  stw += [[abs(u-v), fr, to]]
  
#print(stw)
#heapq.heapify(stw)
stw = sorted(stw, key=lambda x:x[0])

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())


def kruskal():
  # stw = [[s0, t0, w0], [s1, t1, w1], ..., [sn, tn, wn]]
  # stw: s: 始点, t: 終点, w: st間の重み
  # stwはwを小さい順にソートされたものとする
  res = 0
  uf = UnionFind(n)
  #while stw:
  for i in range(n):
    #w, s, t = heapq.heappop(stw)
    w, s, t = stw[i]
    if not uf.isSameGroup(s, t):
      uf.Unite(s, t)
      res += w
  return res

print(kruskal())

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n = I()
    p = LIR(n)
    p.sort()
    v = []
    for i in range(n-1):
        x,y = p[i]
        a,b = p[i+1]
        v.append((min(abs(x-a),abs(y-b)),i,i+1))
    v.sort()
    par = [i for i in range(n)]
    rank = [0]*n
    ans = 0
    for c,a,b in v:
        if root(a) != root(b):
            ans += c
            unite(a,b)
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()