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:
n=int(input())
xlist=[]
ylist=[]
rlist=[]
checked=[-1]*n
for i in range(n):
  x,y=map(int,input().split())
  xlist.append([x,i])
  ylist.append([y,i])
xlist=sorted(xlist,key=lambda x:x[0])
ylist=sorted(ylist,key=lambda x:x[0])
for i in range(1,n):
  cost=xlist[i][0]-xlist[i-1][0]
  rlist.append([cost,xlist[i][1],xlist[i-1][1]])
  cost=ylist[i][0]-ylist[i-1][0]
  rlist.append([cost,ylist[i][1],ylist[i-1][1]])
rlist=sorted(rlist,key=lambda x:x[0])
cnt=0
cost=0
groupn=0
groupc=0
pset=set()
for c,p1,p2 in rlist:
  if cnt==n and groupn-groupc==1:
    break
  if checked[p1]==-1 and checked[p2]==-1:
    checked[p1]=groupn
    checked[p2]=groupn
    cost+=c
    cnt+=2
    groupn+=1
  elif checked[p1]==-1:
    checked[p1]=checked[p2]
    cost+=c
    cnt+=1
  elif checked[p2]==-1:
    checked[p2]=checked[p1]
    cost+=c
    cnt+=1
  elif checked[p1]==checked[p2]:
    continue
  else:
    if (p1,p2) in pset:
      continue
    else:
      for i in range(groupn):
        if (p1,i) in pset and (i,p2) in pset:
          pset.add((p1,p2))
          pset.add((p1,p2))
          break
      if (p1,p2) not in pset:
        pset.add((p1,p2))
        pset.add((p2,p1))
        cost+=c
        groupc+=1
print(cost)

Submission status: Wrong Answer

Solution code:
n=int(input())
xlist=[]
ylist=[]
rlist=[]
checked=[-1]*n
for i in range(n):
  x,y=map(int,input().split())
  xlist.append([x,i])
  ylist.append([y,i])
xlist=sorted(xlist,key=lambda x:x[0])
ylist=sorted(ylist,key=lambda x:x[0])
for i in range(1,n):
  cost=xlist[i][0]-xlist[i-1][0]
  rlist.append([cost,xlist[i][1],xlist[i-1][1]])
  cost=ylist[i][0]-ylist[i-1][0]
  rlist.append([cost,ylist[i][1],ylist[i-1][1]])
rlist=sorted(rlist,key=lambda x:x[0])
cnt=0
cost=0
groupn=0
groupc=0
pset=set()
for c,p1,p2 in rlist:
  if cnt==n and groupn-groupc==1:
    break
  if checked[p1]==-1 and checked[p2]==-1:
    checked[p1]=groupn
    checked[p2]=groupn
    cost+=c
    cnt+=2
    groupn+=1
  elif checked[p1]==-1:
    checked[p1]=checked[p2]
    cost+=c
    cnt+=1
  elif checked[p2]==-1:
    checked[p2]=checked[p1]
    cost+=c
    cnt+=1
  elif checked[p1]==checked[p2]:
    continue
  else:
    tp1,tp2=min(p1,p2),max(p1,p2)
    if (tp1,tp2) not in pset:
      pset.add((tp1,tp2))
      cost+=c
      groupc+=1
print(cost)

Submission status: Wrong Answer

Solution code:
n=int(input())
xlist=[]
ylist=[]
rlist=[]
checked=[-1]*n
for i in range(n):
  x,y=map(int,input().split())
  xlist.append([x,i])
  ylist.append([y,i])
xlist=sorted(xlist,key=lambda x:x[0])
ylist=sorted(ylist,key=lambda x:x[0])
for i in range(1,n):
  cost=xlist[i][0]-xlist[i-1][0]
  rlist.append([cost,xlist[i][1],xlist[i-1][1]])
  cost=ylist[i][0]-ylist[i-1][0]
  rlist.append([cost,ylist[i][1],ylist[i-1][1]])
rlist=sorted(rlist,key=lambda x:x[0])
cnt=0
cost=0
groupn=0
groupc=0
for c,p1,p2 in rlist:
  if cnt==n and groupn-groupc==1:
    break
  if checked[p1]==-1 and checked[p2]==-1:
    checked[p1]=groupn
    checked[p2]=groupn
    cost+=c
    cnt+=2
    groupn+=1
  elif checked[p1]==-1:
    checked[p1]=checked[p2]
    cost+=c
    cnt+=1
  elif checked[p2]==-1:
    checked[p2]=checked[p1]
    cost+=c
    cnt+=1
  elif checked[p1]==checked[p2]:
    continue
  else:
    cost+=c
    groupc+=1
print(cost)

Submission status: Wrong Answer

Solution code:
n=int(input())
xlist=[]
ylist=[]
rlist=[]
checked=[0]*n
for i in range(n):
  x,y=map(int,input().split())
  xlist.append([x,i])
  ylist.append([y,i])
xlist=sorted(xlist,key=lambda x:x[0])
ylist=sorted(ylist,key=lambda x:x[0])
for i in range(1,n):
  cost=xlist[i][0]-xlist[i-1][0]
  rlist.append([cost,xlist[i][1],xlist[i-1][1]])
  cost=ylist[i][0]-ylist[i-1][0]
  rlist.append([cost,ylist[i][1],ylist[i-1][1]])
rlist=sorted(rlist,key=lambda x:x[0])
cnt=0
cost=0
for c,p1,p2 in rlist:
  if cnt>=n:
    break
  if checked[p1]==1 and checked[p2]==1:
    continue
  elif checked[p1]==1:
    checked[p2]=1
    cnt+=1
    cost+=c
  elif checked[p2]==1:
    checked[p1]=1
    cnt+=1
    cost+=c
  else:
    checked[p1]=1
    checked[p2]=1
    cnt+=2
    cost+=c
print(cost)

Submission status: Wrong Answer

Solution code:
def main():
    import sys 
    input = sys.stdin.readline
    from heapq import heappop,heappush
    from operator import itemgetter
    
    def prim():
        used = [True]*n
        edgelist = []
        for e in edge[0]:
            heappush(edgelist,e)
        used[0] = False
        res = 0
        while len(edgelist) != 0:
            short_edge = heappop(edgelist)
            if not used[short_edge[1]]:
                continue
            v = short_edge[1]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heappush(edgelist,e)
            res += short_edge[0]
        return res

    n = int(input())
    A = [list(map(int,input().split()))+[i] for i in range(n)]
    A.append([-10**12,-10**12,-1])
    A.append([10**12,10**12,-1])
    X = sorted(A)
    Y = sorted(A,key = itemgetter(1))
    d = []
    dapp = d.append
    for i in range(1,n+1):
        sx = X[i-1][0]
        sy = Y[i-1][1]
        mx = X[i][0]
        my = Y[i][1]
        lx = X[i+1][0]
        ly = Y[i+1][1]
        if mx-sx>=lx-mx:
            dapp((X[i][2],X[i+1][2],lx-mx))
        else:
            dapp((X[i-1][2],X[i][2],mx-sx))
        if my-sy<=ly-my:
            dapp((Y[i-1][2],Y[i][2],my-sy))
        else:
            dapp((Y[i][2],Y[i+1][2],ly-my))

    edge = [[] for i in range(n)]
    for x,y,z in d:
        if x==-1 or y==-1:
            continue
        edge[x].append([z,y])
        edge[y].append([z,x])

    print(prim()) 

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush

def prim():
    used = [True]*n
    edgelist = []
    for e in edge[0]:
        heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        short_edge = heappop(edgelist)
        if not used[short_edge[1]]:
            continue
        v = short_edge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heappush(edgelist,e)
        res += short_edge[0]
    return res

n = int(input())
X = sorted([list(map(int,input().split()))+[i] for i in range(n)])
Y = sorted(X,key = lambda x:x[1])
dist_x = [[] for i in range(n)]
dist_y = [[] for i in range(n)]
for i in range(n-1):
    x_f,nx_f = X[i][0],X[i][2]
    x_s,nx_s = X[i+1][0],X[i+1][2]
    y_f,ny_f = Y[i][1],Y[i][2]
    y_s,ny_s = Y[i+1][1],Y[i+1][2]
    dist_x[nx_f].append((x_s-x_f,nx_s))
    dist_x[nx_s].append((x_s-x_f,nx_f))
    dist_y[ny_f].append((y_s-y_f,ny_s))
    dist_y[ny_s].append((y_s-y_f,ny_f))
distance = [[] for i in range(2*n)]
for i in range(n):
    dist_x[i].sort()
    dist_y[i].sort()
    dx = dist_x[i][0]
    dy = dist_y[i][0]
    distance[2*i] = (i,dx[1],dx[0])
    distance[2*i+1] = (i,dy[1],dy[0]) 

edge = [[] for i in range(n)]
for i in range(2*n):
    x,y,z = distance[i][0],distance[i][1],distance[i][2]
    edge[x].append([z,y])
    edge[y].append([z,x])
    
print(prim())

Submission status: Wrong Answer

Solution code:
class Kruskal_UnionFind():
    def __init__(self, N):
        self.edges = []
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

    def add(self, u, v, d):
        """
        u = from, v = to, d = cost
        """
        self.edges.append([u, v, d])

    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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def size(self, x):
        x = self.find(x)
        return self.counter[x]

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

    def Kruskal(self):
        """
        return: 最小全域木のコストの和
        """
        edges = sorted(self.edges, key=lambda x: x[2])  # costでself.edgesをソートする
        res = 0
        for e in edges:
            if not self.same(e[0], e[1]):
                self.unite(e[0], e[1])
                res += e[2]
        return res
N = int(input())
G = Kruskal_UnionFind(N)
x = []
y = []
for i in range(N):
    xx,yy = map(int,input().split())
    x.append([i,xx])
    y.append([i,yy])



for i in range(N-1):
    G.add(x[i][0],x[i+1][0],abs(x[i+1][1] - x[i][1]))
    G.add(y[i][0],y[i+1][0],abs(y[i+1][1] - y[i][1]))

print(G.Kruskal())

Submission status: Wrong Answer

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph)
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

class UNION_FIND(object):
    def __init__(self,n):
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])
            return self.parent[x]
 
    def size(self,x):
        return -self.parent[self.root(x)]
    def union(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]
        self.parent[y]=x
        return True

def compute_mst_kruskal(max_v, edges, flip):
    edges.sort(key=lambda x: x[2],reverse=flip)
    uf = UNION_FIND(max_v)
    mst = []
    for (a,b,c) in edges:
        if uf.root(a)!= uf.root(b):
            uf.union(a,b)
            mst.append(c)
    return mst


def main():
    n=int(input())
    inp=[[i]+list(map(int,input().split()))for i in range(n)]
    inpX=sorted(inp,key=lambda x:x[1])
    inpY=sorted(inp,key=lambda x:x[2])
    edges=[]
    for i in range(1,n):
        a,b,c=inpX[i]
        d,e,f=inpX[i-1]
        edges.append((a,d,min(abs(b-e),abs(c-f))))
        a,b,c=inpY[i]
        d,e,f=inpY[i-1]
        edges.append((a,d,min(abs(b-e),abs(c-f))))
    
    print(sum(compute_mst_kruskal(n, edges, 0)))

Submission status: Wrong Answer

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


class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)

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

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


n = int(input())
x_list = [(0, 0)] * n
y_list = [(0, 0)] * n
for i in range(n):
    x, y = map(int, input().split())
    x_list[i] = (x, i)
    y_list[i] = (y, i)
x_list.sort()
y_list.sort()
h = []
heapq.heapify(h)
for i in range(n - 1):
    x1, ix1 = x_list[i]
    x2, ix2 = x_list[i + 1]
    y1, iy1 = y_list[i]
    y2, iy2 = y_list[i + 1]
    heapq.heappush(h, (x2 - x1, ix1, ix2))
    heapq.heappush(h, (y2 - y1, iy1, iy2))

ans = 0
uf = UnionFind(n)
for i in range(n):
    w, s, t = heapq.heappop(h)
    if not uf.same_check(s, t):
        ans += w
        uf.union(s, t)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq


class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)

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

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


n = int(input())
x_list = [(0, 0)] * n
y_list = [(0, 0)] * n
for i in range(n):
    x, y = map(int, input().split())
    x_list[i] = (x, i)
    y_list[i] = (y, i)
x_list.sort()
y_list.sort()
h = []
heapq.heapify(h)
for i in range(n - 1):
    x1, ix1 = x_list[i]
    x2, ix2 = x_list[i + 1]
    y1, iy1 = y_list[i]
    y2, iy2 = y_list[i + 1]
    heapq.heappush(h, (x2 - x1, ix1, ix2))
    heapq.heappush(h, (y2 - y1, iy1, iy2))

ans = 0
uf = UnionFind(n)
for i in range(n):
    w, s, t = heapq.heappop(h)
    if not uf.same_check(s, t):
        ans += w
        uf.union(s, t)
print(ans)

Submission status: Wrong Answer

Solution code:
# sort 後のイメージがわからなかったので
# http://drken1215.hatenablog.com/entry/2019/02/14/124300 を愚直に実装
# 実装してみると，なるほどなあ感
N = int(input())
X, Y = list(zip(*[list(map(int, input().split())) for i in range(N)]))
index = [i for i in range(N)]

class UnionFind:
  def __init__(self, n=0):
    self.par = [-1] * n
    
  def root(self, x):
    if self.par[x] < 0:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  
  def is_same(self, x, y):
    return self.root(x) == self.root(y)
    
  def merge(self, x, y):
    x, y = self.root(x), self.root(y)
    if x == y:
      return None
    if self.par[x] > self.par[y]:
      x, y = y, x
    self.par[x] += self.par[y]
    self.par[y] = x
    

edges = []
X = sorted(zip(*[X, index]))
for i in range(N-1):
  edges.append([X[i+1][0]-X[i][0], (X[i][1], X[i+1][1])])
  
Y = sorted(zip(*[Y, index]))
for i in range(N-1):
  edges.append([Y[i+1][0]-Y[i][0], (Y[i][1], Y[i+1][1])])

res = 0
edges = sorted(edges)
uf = UnionFind(N)
used_ver = set()
for e in edges:
  u, v = e[1]
  cost = e[0]
  if uf.is_same(u, v):
    continue
  uf.merge(u, v)
  res += cost
  used_ver = used_ver | {u, v}
  if len(used_ver) == N:
    break
  
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
from scipy.sparse import lil_matrix

N = int(input())
#edge = lil_matrix((N,N))

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]
for key in [itemgetter(1), itemgetter(2)]:
  XY.sort(key = key)
  for i in range(N-1):
    i1,x1,y1 = XY[i]
    i2,x2,y2 = XY[i+1]
    d = min(abs(x1-x2),abs(y1-y2))
#    edge[i1,i2] = d

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
from scipy.sparse import lil_matrix

N = int(input())
edge = lil_matrix((N,N))

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]
for key in [itemgetter(1), itemgetter(2)]:
  XY.sort(key = key)
  for i in range(N-1):
    i1,x1,y1 = XY[i]
    i2,x2,y2 = XY[i+1]
    d = min(abs(x1-x2),abs(y1-y2))
    edge[i1,i2] = d

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
from scipy.sparse import lil_matrix

N = int(input())
edge = lil_matrix((N,N))

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]
for key in [itemgetter(1), itemgetter(2)]:
  XY.sort(key = key)
  for i in range(N-1):
    i1,x1,y1 = XY[i]
    i2,x2,y2 = XY[i+1]
    d = min(abs(x1-x2),abs(y1-y2))
    edge[i1,i2] = d

edge = edge.tocsr()

Submission status: Wrong Answer

Solution code:
N = int(input())
city =[[i]+list(map(int, input().split())) for i in range(1, N+1)]
def func1(l):
    i, x, y = l
    return x
def func2(l):
    i, x, y = l
    return y
city1 = sorted(city, key = func1)+[[0, 10**10, 10**10]]
city2 = sorted(city, key = func2)+[[0, 10**10, 10**10]]
costs =[[0, 0, 10**9] for _ in range(N+1)]
for j in range(N):
    i11, x11, y11 = city1[j]
    i12, x12, y12 = city1[j-1]
    i13, x13, y13 = city1[j+1]
    prv11x, prv11y, cost11 = costs[i11]
    prv12x, prv12y, cost12 = costs[i12]
    prv13x, prv13y, cost13 = costs[i13]
    if i11 != N:
        if cost11 >= abs(x11-x12) >= abs(x11-x13):
            if prv13x != i11:
                costs[i11] = [i13, prv11y, abs(x11-x13)]
                costs[i13][0] = i11
            else:
                costs[i11] = [i12, prv11y, abs(x11-x12)]
                costs[i12][0] = i11
        elif cost11 >= abs(x11-x13) >= abs(x11-x12):
            if prv12x != i11:
                costs[i11] = [i12, prv11y, abs(x11-x12)]
                costs[i12][0] = i11
            else:
                costs[i11] = [i13, prv11y, abs(x11-x13)]
                costs[i13][0] = i11
        elif cost11 >= abs(x11-x12):
            if prv12x != i11:
                costs[i11] = [i12, prv11y, abs(x11-x12)]
                costs[i12][0] = i11
        elif cost11 >= abs(x11-x13):
            if prv13x != i11:
                costs[i11] = [i13, prv11y, abs(x11-x13)]
                costs[i13][0] = i11
    i21, x21, y21 = city2[j]
    i22, x22, y22 = city2[j-1]
    i23, x23, y23 = city2[j+1]
    prv21x, prv21y, cost21 = costs[i21]
    prv22x, prv22y, cost22 = costs[i22]
    prv23x, prv23y, cost23 = costs[i23]
    if i21 != N:
        if cost21 >= abs(y21-y22) >= abs(y21-y23):
            if prv23y != i21:
                costs[i21] = [prv21x, i23, abs(y21-y23)]
                costs[i23][1] = i21
            else:
                costs[i21] = [prv21x, i22, abs(y21-y22)]
                costs[i22][1] = i21
        elif cost21 >= abs(y21-y23) >= abs(y21-y22):
            if prv22y != i21:
                costs[i21] = [prv21x, i22, abs(y21-y22)]
                costs[i22][1] = i21
            else:
                costs[i21] = [prv21x, i23, abs(y21-y23)]
                costs[i23][1] = i21
        elif cost21 >= abs(y21-y22):
            if prv22y != i21:
                costs[i21] = [prv21x, i22, abs(y21-y22)]
                costs[i22][1] = i21
        elif cost21 >= abs(y21-y23):
            if prv23y != i21:
                costs[i21] = [prv21x, i23, abs(y21-y23)]
                costs[i23][1] = i21
ans = 0
for i in range(1, N):
    ans += costs[i][2]
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    heapq.heappush(path,(abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    heapq.heappush(path,(abs(y-y2),i,j))
union = [[i] for i in range(N)]
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = heapq.heappop(path)
    if union[i] is union[j]:continue
    while union[j]:
        heapq.heappush(union[i],heapq.heappop(union[j]))
    union[j] = union[i]
    ans += c
    cnt += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
def bin_search_in(n,a):
    l = 0
    r = len(a)-1
    while l+1<r:
        i = (l+r)//2
        if a[i] <= n:
            l = i
        else:
            r = i
    return a[l]==n or a[r]==n
xy.sort()
path = []
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    heapq.heappush(path,(abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    heapq.heappush(path,(abs(y-y2),i,j))
union = [[i] for i in range(N)]
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = heapq.heappop(path)
    if bin_search_in(j,union[i]):continue
    union[i] = list(heapq.merge(union[i],union[j]))
    union[j] = union[i]
    ans += c
    cnt += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
def bin_search_in(n,a):
    l = 0
    r = len(a)-1
    while l+1<r:
        i = (l+r)//2
        if a[i] <= n:
            l = i
        else:
            r = i
    return a[l]==n
xy.sort()
path = []
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    heapq.heappush(path,(abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    heapq.heappush(path,(abs(y-y2),i,j))
union = [[i] for i in range(N)]
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = heapq.heappop(path)
    if bin_search_in(j,union[i]):continue
    union[i] = list(heapq.merge(union[i],union[j]))
    union[j] = union[i]
    ans += c
    cnt += 1
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.size_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.size_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        parent = self.root()
        return parent.group_id_

    def size(self):
        parent = self.root()
        return parent.size_

    def unite(self, unite_node):
        parent = self.root()
        unite_parent = unite_node.root()

        if parent.group_id_ != unite_parent.group_id_:
            if parent.size() > unite_parent.size():
                unite_parent.parent_ = parent
                parent.size_ = parent.size_ + unite_parent.size_
            else:
                parent.parent_ = unite_parent
                unite_parent.size_ = parent.size_ + unite_parent.size_
    def is_group(self,other):#selfとotherが同じグループに属するか
        return self.root()==other.root()

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 = sorted(X,key=lambda x:x[1])
Y = sorted(Y,key=lambda x:x[1])
print(X)
Xe = [[X[i][0], X[i+1][0], abs(X[i][1]-X[i+1][1])] for i in range(N-1)]
Ye = [[Y[i][0], Y[i+1][0], abs(Y[i][1]-Y[i+1][1])] for i in range(N-1)]
E = sorted(Xe + Ye, key=lambda e: e[2])
print(E)
U=[UnionFindNode(i) for i in range(N)]
i=0
ans=0
count=1
while(count<N):
    v1,v2,cost=E[i]
    if not U[v1].is_group(U[v2]):
        U[v1].unite(U[v2])
        ans+=cost
        count+=1
    i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n=int(input())
t=[[]]*n
g=[[] for _ in range(n)]
for i in range(n):
    t[i]=[i]+list(map(int,input().split()))
x=sorted(t,key=itemgetter(1))
y=sorted(t,key=itemgetter(2))
print(x)
print(y)

k=1
for i in range(n-1):
    g[x[i][0]].append([x[i+1][0],x[i+1][k]-x[i][k]])
k=2
for i in range(n-1):
    g[y[i][0]].append([y[i+1][0],y[i+1][k]-y[i][k]])

print(g)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

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

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

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()
v = LIR(n)
l = []
par = [i for i in range(n)]
rank = [0 for i in range(n)]
v.sort(key = lambda x:x[0])
for i in range(n-1):
    l.append([i,i+1,v[i+1][0]-v[i][0]])
v.sort(key = lambda x:x[1])
for i in range(n-1):
    l.append([i,i+1,v[i+1][1]-v[i][1]])
l.sort(key = lambda x:x[2])
k = 0
ans = 0
while k != n-1:
    x,y,c = l.pop(0)
    if not same(x,y):
        k += 1
        ans += c
        unite(x,y)
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
import numpy as np

roads = {}


def buildroad(coord1, coord2):
  temp_cost = min(abs(coord1[0]-coord2[0]), abs(coord1[1]-coord2[1]))
  #print temp_cost
  # get existing
  try:
    cost = roads['{}'.format(coord1[0], coord1[0], coord1[1], coord2[1])]
    #print cost
    #if cost > temp_cost:
    #  buildroad(coord1, coord2)
    #else:
    #  roads['{}'.format(coord1[0], coord1[0], coord1[1], coord2[1])] = cost

  # deal with first entry
  except KeyError:
    roads['{}'.format(coord1[0], coord1[0], coord1[1], coord2[1])] = temp_cost
        

    
# prob: recursive?
  
n = input()
arrin = []
for i in range(n):
  x,y = map(int, raw_input().split())
  arrin.append((x,y))
arrin = sorted(arrin)


for i in range(len(arrin)):
  for j in range(len(arrin)):
    buildroad(arrin[i], arrin[j])

                          
print sum(roads.values())/2

Submission status: Wrong Answer

Solution code:
s=input()
l=[]
 
p=s[0]
seq=1
 
for c in s[1:]:
  if c==p:
    seq+=1
  else:
    l.append(seq)
    seq=1
    p=c
l.append(seq)
ans=float("inf")
 
if len(l)>=3:
  d1=max([a+b for a,b in zip(l[0::2],l[1::2])])
  d2=max([a+b for a, b in zip(l[1::2],l[2::2])])
  print(max(d1,d2))
else:
  if s[0]=="1":
    print(sum(l)-l[0])
  else:
    print(l[0])

Submission status: Wrong Answer

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

inf = 1e+10
temp = 0
dist = [[inf,inf] for i in range(n)] #自分から矢印が出ている方だけ記録
data.sort(key = lambda x : x[0])
for i in range(n-1): #左から右
    dist[data[i][2]][0] = min(abs(data[i+1][0]-data[i][0]),abs(data[i+1][1]-data[i][1]))

data.sort(key = lambda x:x[1])
for i in range(n-1):
    dist[data[i][2]][1] = min(abs(data[i+1][0]-data[i][0]),abs(data[i+1][1]-data[i][1]))

ans = 0
temp = []
for i in range(n):
    if inf not in dist[i]:
        ans += min(dist[i])
    else:
        temp.append(min(dist[i]))
print(ans + min(temp))

Submission status: Wrong Answer

Solution code:
N = input()

data = [map(int,raw_input().split()) for i in range(N)]

def hoge(x,y):
    return x[1]-y[1]

data.sort()

for i in range(1,N-1):
    data[i].append(min(data[i+1][0]-data[i][0],data[i][0]-data[i-1][0]))
data[0].append(data[1][0]-data[0][0])
data[N-1].append(data[N-1][0]-data[N-2][0])


data.sort(hoge)
for i in range(1,N-1):
    data[i].append(min(data[i+1][1]-data[i][1],data[i][1]-data[i-1][1]))
data[0].append(data[1][1]-data[0][1])
data[N-1].append(data[N-1][1]-data[N-2][1])

ans = 0
minimam = 10000000000
for i in range(N):
    ans += min(data[i][2],data[i][3])
    minimam = min(minimam,min(data[i][2],data[i][3]))

print ans-minimam

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import heapq
N = int(input())
X = []
Y = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((x, i))
    Y.append((y, i))
X.sort(key=itemgetter(0))
Y.sort(key=itemgetter(0))

import sys
sys.setrecursionlimit(10**6)


class UnionFind(object):

    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        else:
            return False
u = UnionFind(N)
q = []
for i in range(N-1):
    q.append((X[i+1][0]-X[i][0], X[i+1][1], X[i][1]))
    q.append((Y[i+1][0]-Y[i][0], Y[i+1][1], Y[i][1]))
q.sort(key=itemgetter(0))
ans = 0
for elem in q:
    cost, a, b = elem
    if u.table[a]==-1 or u.table[b]==-1:
        u.union(a, b)
        ans += cost
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
C = [[] for i in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  C[i] = [x, y, i]
Cx = sorted(C, key=lambda c: c[0])
Cy = sorted(C, key=lambda c: c[1])
Qx = sorted([[Cx[i + 1][0] - Cx[i][0], Cx[i][2], Cx[i + 1][2]] for i in range(N - 1)])
Qy = sorted([[Cy[i + 1][1] - Cy[i][1], Cy[i][2], Cy[i + 1][2]] for i in range(N - 1)])
R = [i for i in range(N)]
def root(n):
  if R[n] == n:
    return n
  else:
    R[n] = root(R[n])
    return R[n]
cnt = 0
cost = 0
x = 0
y = 0
while cnt < N - 1:
  if Qx[x][0] <= Qy[y][0]:
    q = Qx[x]
    x += 1
  else:
    q = Qy[y]
    y += 1
  if root(q[1]) != root(q[2]):
    R[q[2]] = q[1]
    cost += q[0]
    cnt += 1
print(cost)