Problem p03440 (python)

Fixed submission:
# -*- coding: utf-8 -*-
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)] # [next, rank]
 
def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)
 
D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])
 
H = []
res = 0 

for k, v in D.items():
    v = sorted(v)
    res += v[0]
    H.extend(v[1:])
 
if N < 2*(N-M-1):
    print("Impossible")
elif M == N-1:
    print(0)
else:
    res += sum(sorted(H)[:2*(N-M-1) - len(D.keys())])
    print(res)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from collections import deque
from heapq import heappush, heappop, heapify, merge
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)] # [next, rank]
 
def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)
 
D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])
 
H = []
S = [] # single

for k, v in D.items():
    if len(v) == 1:
        S.append(v)
    else:
        H.append(sorted(v))
 
heapify(H)
heapify(S)
 
res = 0 
while True:
    if (len(H) == 0) or (len(S) + len(H) <= 1):
        break
    

    
    A = heappop(H)
    B = heappop(H)
    
    if len(S) > 0:
        D = heappop(S)    
        if D[0] < B[0]:
            heappush(H, B)
            B = D
        else:
            heappush(S, D)
 
    res += A[0] + B[0]
    C = list(merge(A[1:], B[1:]))
 
    if len(C) == 1:
        heappush(S, C)
    else:
        heappush(H, C)
 
ok = True
if len(S) > 2:
    print("Impossible")
    ok = False
elif len(S) == 2:
    res += S[0][0]+S[1][0]
elif len(S) == 1:
    A = S[0]
    if len(H) == 1:
        B = heappop(H)
        res += A[0] + B[0]
else:
    pass
if ok:
    print(res)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from collections import deque
from heapq import heappush, heappop, heapify, merge
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)] # [next, rank]
 
def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)
 
D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])
 
H = []
S = [] # single

for k, v in D.items():
    if len(v) == 1:
        S.append(v)
    else:
        H.append(sorted(v))
 
heapify(H)
heapify(S)
 
res = 0 
while True:
    if (len(H) == 0) or (len(S) + len(H) <= 1):
        break
    
    if len(S) > 0:
        D = heappop(S)
    
    A = heappop(H)
    B = heappop(H)
    
    if D[0] < B[0]:
        heappush(H, B)
        B = D
    else:
        heappush(S, D)
 
    res += A[0] + B[0]
    C = list(merge(A[1:], B[1:]))
 
    if len(C) == 1:
        heappush(S, C)
    else:
        heappush(H, C)
 
ok = True
if len(S) > 2:
    print("Impossible")
    ok = False
elif len(S) == 2:
    res += S[0][0]+S[1][0]
elif len(S) == 1:
    A = S[0]
    if len(H) == 1:
        B = heappop(H)
        res += A[0] + B[0]
else:
    pass
if ok:
    print(res)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from collections import deque
from heapq import heappush, heappop, heapify, merge
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)] # [next, rank]

def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)

D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])

H = []
S = deque([]) # single
for k, v in D.items():
    if len(v) == 1:
        S.append(v)
    else:
        H.append(sorted(v))

heapify(H)

res = 0 
while True:
    if (len(H) == 0) or (len(S) + len(H) <= 1):
        break
    
    if len(S) > 1:
        A = S.popleft()
    else:
        A = heappop(H)

    B = heappop(H)

    res += A[0] + B[0]
    C = list(merge(A[1:], B[1:]))[:len(H)+len(S)+3]

    if len(C) == 1:
        S.append(C)
    else:
        heappush(H, C)

ok = True
if len(S) > 2:
    print("Impossible")
    ok = False
elif len(S) == 2:
    res += S[0][0] + S[1][0]
elif len(S) == 1:
    A = S[0]
    if len(H) == 1:
        B = heappop(H)
        res += A[0] + B[0]
else:
    pass
if ok:
    print(res)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from collections import deque
from heapq import heappush, heappop, heapify, merge
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)] # [next, rank]

def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)

D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])

H = []
S = deque([]) # single
for k, v in D.items():
    if len(v) == 1:
        S.append(v)
    else:
        H.append(sorted(v))

heapify(H)

res = 0 
while True:
    if (len(H) == 0) or (len(S) + len(H) <= 1):
        break
    
    if len(S) > 1:
        A = S.popleft()
    else:
        if len(H) <= 1:
            break
        A = heappop(H)

    B = heappop(H)

    res += A[0] + B[0]
    C = list(merge(A[1:], B[1:]))

    if len(C) == 1:
        S.append(C)
    elif len(C) == 0: # ありえないはず
        pass
    else:
        heappush(H, C)

ok = True
if len(S) > 2:
    print("Impossible")
    ok = False
elif len(S) == 2:
    res += S[0]+S[1]
elif len(S) == 1:
    A = S[0]
    if len(H) == 1:
        B = heappop(H)
        res += A[0] + B[0]
else:
    pass
if ok:
    print(res)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from collections import deque
from heapq import heappush, heappop, heapify, merge
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)] # [next, rank]

def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)

D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])

H = []
S = deque([]) # single
for k, v in D.items():
    if len(v) == 1:
        S.append(v)
    else:
        H.append(sorted(v))

heapify(H)

res = 0 
while True:
    if (len(H) == 0) or (len(S) + len(H) <= 1):
        break
    
    if len(S) > 1:
        A = S.leftpop()
    else:
        if len(H) <= 1:
            break
        A = heappop(H)

    B = heappop(H)

    res += A[0] + B[0]
    C = list(merge(A[1:], B[1:]))

    if len(C) == 1:
        S.append(C)
    elif len(C) == 0: # ありえないはず
        pass
    else:
        heappush(H, C)

ok = True
if len(S) > 2:
    print("Impossible")
    ok = False
elif len(S) == 2:
    res += S[0]+S[1]
elif len(S) == 1:
    A = S[0]
    if len(H) == 1:
        B = heappop(H)
        res += A[0] + B[0]
else:
    pass
if ok:
    print(res)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from collections import deque
from heapq import heappush, heappop, heapify, merge
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)]# [next, rank]

def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)

D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])

H = []
S = deque([]) # single
for k, v in D.items():
    if len(v) == 1:
        S.append(v)
    else:
        H.append(sorted(v))

heapify(H)

res = 0 
while True:
    if (len(H) == 0) or (len(S) + len(H) <= 1):
        break
    
    if len(S) > 1:
        A = S.leftpop()
    else:
        if len(H) <= 1:
            break
        A = heappop(H)

    B = heappop(H)

    res += A[0] + B[0]
    C = list(merge(A[1:], B[1:]))

    if len(C) == 1:
        S.append(C)
    elif len(C) == 0: # ありえないはず
        pass
    else:
        heappush(H, C)

ok = True
if len(S) > 2:
    print("Impossible")
    ok = False
elif len(S) == 2:
    res += S[0]+S[1]
elif len(S) == 1:
    A = S[0]
    if len(H) == 1:
        B = heappop(H)
        res += A[0] + B[0]
else:
    pass
if ok:
    print(res)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from collections import  deque
from heapq import heappush, heappop, heapify, merge
from collections import defaultdict
import sys
sys.setrecursionlimit(10**10)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)]# [next, rank]

def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)

D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])

H = []
S = deque([]) # single
for k, v in D.items():
    if len(v) == 1:
        S.append(v)
    else:
        H.append(sorted(v))
heapify(H)

res = 0 
while True:
    if len(H) == 0 or len(S) + len(H) <= 1:
        break   
    if S:
        A = S.leftpop()
    else:
        A = heappop(H)
    B = heappop(H)
    res += A[0] + B[0]
    C = list(merge(A[1:], B[1:]))
    if len(C) == 1:
        S.append(C)
    else:
        heappush(H, C)

if len(S) > 2:
    print("Impossible")
    exit()
elif len(S) == 2:
    res += S[0]+S[1]
elif len(S) == 1:
    A = S[0]
    if len(H) == 1:
        B = heappop(H)
        res += A[0] + B[0]
else:
    pass
print(res)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from collections import  deque
from heapq import heappush, heappop, heapify, merge
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)]# [next, rank]

def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)

D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])

H = []
S = deque([]) # single
for k, v in D.items():
    if len(v) == 1:
        S.append(v)
    else:
        H.append(sorted(v))
heapify(H)

res = 0 
while len(H) > 1:
    if S:
        A = S.leftpop()
    else:
        A = heappop(H)
    B = heappop(H)
    res += A[0] + B[0]
    C = list(merge(A[1:], B[1:]))
    if len(C) == 1:
        S.append(C)
    else:
        heappush(H, C)

if len(S) > 1:
    print("Impossible")
    exit()
elif len(S) == 1:
    A = S[0]
    if len(H) == 1:
        B = heappop(H)
        res += A[0] + B[0]
else:
    pass
print(res)