Problem p03682 (python)

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

Buggy submission (verdict: Runtime Error):
from collections import deque
import sys

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

Buggy submission (verdict: Runtime Error):
from collections import deque
import sys

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

Buggy submission (verdict: Runtime Error):
from collections import deque
import sys

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

Buggy submission (verdict: Runtime Error):
from collections import deque
import sys

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

Buggy submission (verdict: Runtime Error):
from collections import deque
 
 
n = int(input())
nodes = []
done = [0 for _ in range(n)]
par = {}
for _ in range(n):
    x, y = map(int,input().split())
    nodes.append((x,y))
    par[(x,y)]=(x,y)
nodesx = sorted(nodes)
nodesy = sorted(nodes,key=lambda z:z[1])
s = []
 
for i in range(n-1):
    xcost =nodesx[i+1][0]-nodesx[i][0]
    ycost =nodesy[i+1][1]-nodesy[i][1]
    s.append((xcost,(nodesx[i+1],nodesx[i])))
    s.append((ycost,(nodesy[i+1],nodesy[i])))
s.sort()
s = deque(s)
def root(node,par):
    if node == par[node]:
        return node
    else:
        par[node] =root(par[node],par)
        return par[node]
def unite(node1,node2,par):
    par[root(node1,par)] = root(node2,par)
ans = 0
count =0
while count < n-1 :
    cost,(node1,node2) = s.popleft()
    if root(node1,par) != root(node2,par):
        unite(node1,node2,par)
        ans +=cost
        count += 1
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq as hq


n = int(input())
nodes = []
done = [0 for _ in range(n)]
par = {}
for _ in range(n):
    x, y = map(int,input().split())
    nodes.append((x,y))
    par[(x,y)]=(x,y)
nodesx = sorted(nodes)
nodesy = sorted(nodes,key=lambda z:z[1])
s = []

for i in range(n-1):
    xcost =nodesx[i+1][0]-nodesx[i][0]
    ycost =nodesy[i+1][1]-nodesy[i][1]
    hq.heappush(s,(xcost,(nodesx[i+1],nodesx[i])))
    hq.heappush(s,(ycost,(nodesy[i+1],nodesy[i])))
def root(node,par):
    if node == par[node]:
        return node
    else:
        par[node] =root(par[node],par)
        return par[node]
def unite(node1,node2,par):
    par[root(node1,par)] = root(node2,par)
ans = 0
count =0
while count < n-1 :
    cost,(node1,node2) = hq.heappop(s)
    if root(node1,par) != root(node2,par):
        unite(node1,node2,par)
        ans +=cost
        count += 1
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq as hq


n = int(input())
nodes = []
done = [0 for _ in range(n)]
par = {}
for _ in range(n):
    x, y = map(int,input().split())
    nodes.append((x,y))
    par[(x,y)]=(x,y)
nodesx = sorted(nodes)
nodesy = sorted(nodes,key=lambda z:z[1])
s = []

for i in range(n-1):
    xcost =nodesx[i+1][0]-nodesx[i][0]
    ycost =nodesy[i+1][1]-nodesy[i][1]
    hq.heappush(s,(xcost,(nodesx[i+1],nodesx[i])))
    hq.heappush(s,(ycost,(nodesy[i+1],nodesy[i])))
def root(node,par):
    if node == par[node]:
        return node
    else:
        par[node] =root(par[node],par)
        return par[node]
def unite(node1,node2,par):
    par[root(node1,par)] = root(node2,par)
ans = 0
while s :
    cost,(node1,node2) = hq.heappop(s)
    if root(node1,par) != root(node2,par):
        unite(node1,node2,par)
        ans +=cost
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq as hq


n = int(input())
nodes = []
done = [0 for _ in range(n)]
par = {}
for _ in range(n):
    x, y = map(int,input().split())
    nodes.append((x,y))
    par[(x,y)]=(x,y)
nodesx = sorted(nodes)
nodesy = sorted(nodes,key=lambda z:z[1])
s = []

for i in range(n-1):
    xcost =nodesx[i+1][0]-nodesx[i][0]
    ycost =nodesy[i+1][1]-nodesy[i][1]
    hq.heappush(s,(xcost,(nodesx[i+1],nodesx[i])))
    hq.heappush(s,(ycost,(nodesy[i+1],nodesy[i])))
def root(node,par):
    if node == par[node]:
        return node
    else:
        par[node] =root(par[node],par)
        return par[node]
def unite(node1,node2,par):
    par[root(node1,par)] = root(node2,par)
ans = 0
while s :
    cost,(node1,node2) = hq.heappop(s)
    if root(node1,par) != root(node2,par):
        unite(node1,node2,par)
        ans +=cost
print(ans)

Buggy submission (verdict: Runtime Error):

n = int(input())
nords = []
done = [0 for _ in range(n)]
for _ in range(n):
    x, y = map(int,input().split())
    nords.append((x,y))

ans = 0
tree = [nords[0]]
done[0] = 1
count = 0
while count <n-1:
    cost = float("inf")
    merge = ()
    donei = 0
    for (xt, yt) in tree:
        for i,(xi,yi) in enumerate(nords):

            if not done[i]:
                if min(abs(xt-xi),abs(yt-yi)) <cost:
                    cost = min(abs(xt-xi),abs(yt-yi))
                    merge = (xi,yi)
                    donei = i
    ans += cost
    tree.append(merge)
    done[donei] =1 
    count +=1
print(ans) 
        
n = int(input())
nords = []
done = [0 for _ in range(n)]
for _ in range(n):
    x, y = map(int,input().split())
    nords.append((x,y))

ans = 0
tree = [nords[0]]
done[0] = 1
count = 0
while count <n-1:
    cost = float("inf")
    merge = ()
    donei = 0
    for (xt, yt) in tree:
        for i,(xi,yi) in enumerate(nords):

            if not done[i]:
                if min(abs(xt-xi),abs(yt-yi)) <cost:
                    cost = min(abs(xt-xi),abs(yt-yi))
                    merge = (xi,yi)
                    donei = i
    ans += cost
    tree.append(merge)
    done[donei] =1 
    count +=1
print(ans)