Problem:


Score : 600 points

Problem Statement

You are given a forest with N vertices and M edges. The vertices are numbered 0 through N-1.
The edges are given in the format (x_i,y_i), which means that Vertex x_i and y_i are connected by an edge.

Each vertex i has a value a_i.
You want to add edges in the given forest so that the forest becomes connected.
To add an edge, you choose two different vertices i and j, then span an edge between i and j.
This operation costs a_i + a_j dollars, and afterward neither Vertex i nor j can be selected again.

Find the minimum total cost required to make the forest connected, or print Impossible if it is impossible.

Constraints

1 ≤ N ≤ 100,000

0 ≤ M ≤ N-1

1 ≤ a_i ≤ 10^9

0 ≤ x_i,y_i ≤ N-1

The given graph is a forest.

All input values are integers.

Input

Input is given from Standard Input in the following format:

N M
a_0 a_1 .. a_{N-1}
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print the minimum total cost required to make the forest connected, or print Impossible if it is impossible.

Sample Input 1

7 5
1 2 3 4 5 6 7
3 0
4 0
1 2
1 3
5 6

Sample Output 1

7

If we connect vertices 0 and 5, the graph becomes connected, for the cost of 1 + 6 = 7 dollars.

Sample Input 2

5 0
3 1 4 1 5

Sample Output 2

Impossible

We can't make the graph connected.

Sample Input 3

1 0
5

Sample Output 3

0

The graph is already connected, so we do not need to add any edges.



Sample input:
7 5
1 2 3 4 5 6 7
3 0
4 0
1 2
1 3
5 6


Sample output:
7

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# UnionFind
class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x]=self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root


def main():
    N,M=MI()
    A=LI()

    uf=UnionFind(N)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes
    for _ in range(M):
        x,y = MI()
        unite(x,y)
    
    need = N-1-M #N-1本の辺が必要で、今M本の辺がある
    need *= 2 #辺の2倍の点を使う
    if need > N:
        print("Impossible")
        return 
    if need == 0:
        print(0)
        return

    root = defaultdict(list)
    for i,a in enumerate(A):
        root[get_root(i)].append(a)

    ans = 0
    whole = []
    for list_ in root.values():
        list_.sort()
        ans += list_[0]
        whole.extend(list_[1:])
        need-=1
    ans += sum(whole[:need])
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# UnionFind
class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x]=self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root


def main():
    N,M=MI()
    A=LI()

    uf=UnionFind(N)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes
    for _ in range(M):
        x,y = MI()
        unite(x,y)
    
    pri_queue = []

    need = N-1-M #N-1本の辺が必要で、今M本の辺がある
    need *= 2 #辺の2倍の点を使う
    if need > N:
        print("Impossible")
        return 

    root = defaultdict(list)
    for i,a in enumerate(A):
        root[get_root(i)].append(a)

    ans = 0
    whole = []
    for list_ in root.values():
        if need:
            list_.sort()
            ans += list_[0]
            whole.extend(list_[1:])
            need-=1
    ans += sum(whole[:need])
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# UnionFind
class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x]=self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root


def main():
    N,M=MI()
    A=LI()
    for i,a in enumerate(A):
        A[i] = (a,i)
    A.sort()

    uf=UnionFind(N)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes
    for _ in range(M):
        x,y = MI()
        unite(x,y)
    
    ans = 0
    j = 1
    i=0
    united = set()
    while i<N:
        a,idx_i = A[i]
        j=max(j,i+1)
        if idx_i in united:
            i+=1
            continue
        while j<N:
            # print(i,j)
            b,idx_j = A[j]
            if get_root(idx_i)!=get_root(idx_j):
                # print("unite",idx_i,idx_j)
                ans += a+b
                unite(idx_i,idx_j)
                united.add(idx_i)
                united.add(idx_j)
                j+=1
                break
            j+=1
        i += 1

    if nodes[get_root(0)] == -N:
        print(ans)
    else:
        print("Impossible")
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# UnionFind
class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x]=self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root


def main():
    N,M=MI()
    A=LI()
    for i,a in enumerate(A):
        A[i] = (a,i)
    A.sort()

    uf=UnionFind(N)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes
    for _ in range(M):
        x,y = MI()
        unite(x,y)
    
    ans = 0
    j = 1
    i=0
    united = set()
    while i<N:
        a,idx_i = A[i]
        j=max(j,i+1)
        while j<N:
            # print(i,j)
            b,idx_j = A[j]
            if idx_i in united:
                j+=1
                continue
            if get_root(idx_i)!=get_root(idx_j):
                # print("unite",idx_i,idx_j)
                ans += a+b
                unite(idx_i,idx_j)
                united.add(idx_i)
                united.add(idx_j)
                j+=1
                break
            j+=1
        i += 1

    if nodes[get_root(0)] == -N:
        print(ans)
    else:
        print("Impossible")
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# UnionFind
class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x]=self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root


def main():
    N,M=MI()
    A=LI()
    for i,a in enumerate(A):
        A[i] = (a,i)
    A.sort()

    uf=UnionFind(N)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes
    for _ in range(M):
        x,y = MI()
        unite(x,y)
    
    ans = 0
    j = 1
    i=0
    while i<N:
        a,idx_i = A[i]
        j=max(j,i+1)
        while j<N:
            b,idx_j = A[j]
            if get_root(idx_i)!=get_root(idx_j):
                ans += a+b
                unite(idx_i,idx_j)
                break
            j+=1
        i = j+1

    if nodes[get_root(0)] == -N:
        print(ans)
    else:
        print("Impossible")
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class UnionFind():
   # 作りたい要素数nで初期化
   # 使用するインスタンス変数の初期化
   def __init__(self, n):
       self.n = n
       # root[x]<0ならそのノードが根かつその値が木の要素数
       # rootノードでその木の要素数を記録する
       self.root = [-1]*(n+1)
       # 木をくっつける時にアンバランスにならないように調整する
       self.rnk = [0]*(n+1)
   # ノードxのrootノードを見つける
   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):
       # 入力ノードのrootノードを見つける
       x = self.Find_Root(x)
       y = self.Find_Root(y)
       # すでに同じ木に属していた場合
       if(x == y):
           return
       # 違う木に属していた場合rnkを見てくっつける方を決める
       elif(self.rnk[x] > self.rnk[y]):
           self.root[x] += self.root[y]
           self.root[y] = x
       else:
           self.root[y] += self.root[x]
           self.root[x] = y
           # rnkが同じ（深さに差がない場合）は1増やす
           if(self.rnk[x] == self.rnk[y]):
               self.rnk[y] += 1
   # xとyが同じグループに属するか判断
   def isSameGroup(self, x, y):
       return self.Find_Root(x) == self.Find_Root(y)
   # ノードxが属する木のサイズを返す
   def Count(self, x):
       return -self.root[self.Find_Root(x)]
n,m=map(int,input().split())
a=list(map(int,input().split()))
h=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    h.Unite(x,y)
dic={}
k=0
for i in range(n):
    x=h.Find_Root(i)
    if x in dic:
        dic[x].add(i)
    else:
        dic[x]={i}
        k+=1
b=[sorted([a[j] for j in dic[i]]) for i in dic]
ans=0
c=[]
cnt=0
if k==1:
    print(0)
    exit()
for i in range(k):
    ans+=b[i][0]
    if len(b[i])>1:
        for j in b[i][1:]:
            c.append(j)
    else:
        cnt+=1
if cnt>2:
    print("Impossible")
    exit()
else:
    c.sort()
    ans+=sum(c[:k-2])
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind():
   # 作りたい要素数nで初期化
   # 使用するインスタンス変数の初期化
   def __init__(self, n):
       self.n = n
       # root[x]<0ならそのノードが根かつその値が木の要素数
       # rootノードでその木の要素数を記録する
       self.root = [-1]*(n+1)
       # 木をくっつける時にアンバランスにならないように調整する
       self.rnk = [0]*(n+1)
   # ノードxのrootノードを見つける
   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):
       # 入力ノードのrootノードを見つける
       x = self.Find_Root(x)
       y = self.Find_Root(y)
       # すでに同じ木に属していた場合
       if(x == y):
           return
       # 違う木に属していた場合rnkを見てくっつける方を決める
       elif(self.rnk[x] > self.rnk[y]):
           self.root[x] += self.root[y]
           self.root[y] = x
       else:
           self.root[y] += self.root[x]
           self.root[x] = y
           # rnkが同じ（深さに差がない場合）は1増やす
           if(self.rnk[x] == self.rnk[y]):
               self.rnk[y] += 1
   # xとyが同じグループに属するか判断
   def isSameGroup(self, x, y):
       return self.Find_Root(x) == self.Find_Root(y)
   # ノードxが属する木のサイズを返す
   def Count(self, x):
       return -self.root[self.Find_Root(x)]
n,m=map(int,input().split())
a=list(map(int,input().split()))
h=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    h.Unite(x,y)
dic={}
k=0
for i in range(n):
    x=h.Find_Root(i)
    if x in dic:
        dic[x].add(i)
    else:
        dic[x]={i}
        k+=1
b=[sorted([a[j] for j in dic[i]]) for i in dic]
ans=0
c=[]
cnt=0
if k==1:
    print(0)
    exit()
for i in range(k):
    ans+=b[i][0]
    if len(b[i])>1:
        for j in b[i][1:]:
            c.append(j)
    else:
        cnt+=1
if k==2:
    print(ans)
    exit()
if cnt>2:
    print("Impossible")
    exit()
else:
    c.sort()
    ans+=sum(c[:k-2])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heapify, heappop, heappush

class UFT(): #Union-find tree class
    def __init__(self, N): 
        self.tree = [int(i) for i in range(N)] 
        self.rank = [0 for i in range(N)]

    def find(self, a):
        if self.tree[a] == a: return a
        else:
            self.tree[a] = self.find(self.tree[a])
            return self.tree[a]

    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b: return
        if self.rank[a] < self.rank[b]: 
            self.tree[a] = b
        else:
            self.tree[b] = a
            if self.rank[a] == self.rank[b]: self.rank[a] += 1

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    parent = UFT(N)
    for i in range(M):
        x, y = map(int, input().split())
        parent.unite(x, y)
    for i in range(N): parent.find(i)
    
    minCost = dict()
    Node = []
    totalNode = 0
    for i in range(N):
        p = parent.find(i)
        if p not in minCost: 
            minCost[p] = []
            heapify(minCost[p])
            Node.append(p)
            totalNode += 1
        heappush(minCost[p], A[i])

    par = Node[0]
    q = []
    heapify(q)
    for i in range(1, totalNode):
        ccost = heappop(minCost[Node[i]])
        heappush(q, (ccost, Node[i]))

    ans = 0
    while q:
        if not minCost[par]: 
            print("Impossible")
            break
        parCost = heappop(minCost[par])
        addCost, addNode = heappop(q)
        ans += parCost + addCost
        while minCost[addNode]: heappush(minCost[par], heappop(minCost[addNode]))
    else: print(ans)

    #for i in range(N): print((i, parent.find(i)))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heapify, heappop, heappush

class UFT(): #Union-find tree class
    def __init__(self, N): 
        self.tree = [int(i) for i in range(N)] 
        self.rank = [0 for i in range(N)]

    def find(self, a):
        if self.tree[a] == a: return a
        else:
            self.tree[a] = self.find(self.tree[a])
            return self.tree[a]

    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b: return
        if self.rank[a] < self.rank[b]: 
            self.tree[a] = b
        else:
            self.tree[b] = a
            if self.rank[a] == self.rank[b]: self.rank[a] += 1

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    parent = UFT(N)
    for i in range(M):
        x, y = map(int, input().split())
        parent.unite(x, y)
    
    minCost = dict()
    Node = []
    totalNode = 0
    for i in range(N):
        p = parent.find(i)
        if p not in minCost: 
            minCost[p] = []
            heapify(minCost[p])
            Node.append(p)
            totalNode += 1
        heappush(minCost[p], A[i])

    parq = []
    heapify(parq)
    for cost in minCost[Node[0]]: heappush(parq, cost)
    q = []
    heapify(q)
    for i in range(1, totalNode):
        ccost = heappop(minCost[Node[i]])
        heappush(q, (ccost, Node[i]))

    ans = 0
    while q:
        if not parq: 
            print("Impossible")
            break
        parCost = heappop(parq)
        addCost, addNode = heappop(q)
        ans += parCost + addCost
        while minCost[addNode]: heappush(parq, heappop(minCost[addNode]))
    else: print(ans)

    #for i in range(N): print((i, parent.find(i)))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
A = [int(a) for a in input().split()]

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
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]


uf = UnionFind(N)
for _ in range(M):
    x,y = map(int, input().split())
    uf.unite(x+1, y+1)

import heapq
h1 = []
h2 = []
for i in range(1, N+1):
    if uf.isSameGroup(1, i):
        heapq.heappush(h1, ((A[i-1], i)))
    else:
        heapq.heappush(h2, ((A[i-1], i)))

ans = 0
while len(h1) > 0 and len(h2) > 0:
    t1 = heapq.heappop(h1)
    t2 = heapq.heappop(h2)
    if uf.isSameGroup(t1[1], t2[1]):
        continue
    uf.unite(t1[1], t2[1])
    ans += t1[0]+t2[0]
    while len(h2) > 0 and uf.isSameGroup(1, h2[0][1]):
        temp = heapq.heappop(h2)
        heapq.heappush(h1, temp)

flag = True
for i in range(1, N+1):
    if uf.isSameGroup(1, i):
        continue
    flag = False
    break

if not flag:
    ans = "Impossible"
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind():
   # 作りたい要素数nで初期化
   # 使用するインスタンス変数の初期化
   def __init__(self, n):
       self.n = n
       # root[x]<0ならそのノードが根かつその値が木の要素数
       # rootノードでその木の要素数を記録する
       self.root = [-1]*(n+1)
       # 木をくっつける時にアンバランスにならないように調整する
       self.rnk = [0]*(n+1)
   # ノードxのrootノードを見つける
   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):
       # 入力ノードのrootノードを見つける
       x = self.Find_Root(x)
       y = self.Find_Root(y)
       # すでに同じ木に属していた場合
       if(x == y):
           return
       # 違う木に属していた場合rnkを見てくっつける方を決める
       elif(self.rnk[x] > self.rnk[y]):
           self.root[x] += self.root[y]
           self.root[y] = x
       else:
           self.root[y] += self.root[x]
           self.root[x] = y
           # rnkが同じ（深さに差がない場合）は1増やす
           if(self.rnk[x] == self.rnk[y]):
               self.rnk[y] += 1
   # xとyが同じグループに属するか判断
   def isSameGroup(self, x, y):
       return self.Find_Root(x) == self.Find_Root(y)
   # ノードxが属する木のサイズを返す
   def Count(self, x):
       return -self.root[self.Find_Root(x)]
import heapq as hq
n,m=map(int,input().split())
a=list(map(int,input().split()))
h=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    h.Unite(x,y)
dic={}
k=0
for i in range(n):
    x=h.Find_Root(i)
    if x in dic:
        dic[x].add(i)
    else:
        dic[x]={i}
        k+=1
b=[sorted([a[j] for j in dic[i]]) for i in dic]
ans=0
c=[]
cnt=0
if k==1:
    print(0)
    exit()
for i in range(k):
    ans+=b[i][0]
    if len(b[i])>1:
        c.append(b[i][1])
    else:
        cnt+=1
if k==2:
    print(ans)
    exit()
if cnt>2:
    print("Impossible")
    exit()
else:
    ans+=sum(c)
    if cnt==0:
        c.sort()
        ans-=c[-1]+c[-2]
    elif cnt==1:
        ans-=max(c)
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind():
   # 作りたい要素数nで初期化
   # 使用するインスタンス変数の初期化
   def __init__(self, n):
       self.n = n
       # root[x]<0ならそのノードが根かつその値が木の要素数
       # rootノードでその木の要素数を記録する
       self.root = [-1]*(n+1)
       # 木をくっつける時にアンバランスにならないように調整する
       self.rnk = [0]*(n+1)
   # ノードxのrootノードを見つける
   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):
       # 入力ノードのrootノードを見つける
       x = self.Find_Root(x)
       y = self.Find_Root(y)
       # すでに同じ木に属していた場合
       if(x == y):
           return
       # 違う木に属していた場合rnkを見てくっつける方を決める
       elif(self.rnk[x] > self.rnk[y]):
           self.root[x] += self.root[y]
           self.root[y] = x
       else:
           self.root[y] += self.root[x]
           self.root[x] = y
           # rnkが同じ（深さに差がない場合）は1増やす
           if(self.rnk[x] == self.rnk[y]):
               self.rnk[y] += 1
   # xとyが同じグループに属するか判断
   def isSameGroup(self, x, y):
       return self.Find_Root(x) == self.Find_Root(y)
   # ノードxが属する木のサイズを返す
   def Count(self, x):
       return -self.root[self.Find_Root(x)]
import heapq as hq
n,m=map(int,input().split())
a=list(map(int,input().split()))
h=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    h.Unite(x,y)
dic={}
k=0
for i in range(n):
    x=h.Find_Root(i)
    if x in dic:
        dic[x].add(i)
    else:
        dic[x]={i}
        k+=1
b=[sorted([a[j] for j in dic[i]]) for i in dic]
ans=0
c=[]
cnt=0
if k==1:
    print(0)
    exit()
for i in range(k):
    ans+=b[i][0]
    if len(b[i])>1:
        c.append(b[i][1])
    else:
        cnt+=1
if k==2:
    print(ans)
    exit()
if cnt>2:
    print("Impossible")
    exit()
else:
    ans+=sum(c)
    if cnt==2:
        c.sort()
        ans-=c[-1]+c[-2]
    elif cnt==1:
        ans-=min(c)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
res = 0
if M == 0:
  if N == 1:
    print(0)
  elif N == 2:
    print(sum(a))
  else: print("Impossible")
  exit(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 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]

uf = UnionFind(N - 1)
for _ in range(M):
  u, v = map(int, input().split())
  uf.Unite(u, v)
hs = [[] for _ in range(N + 1)]
for x in range(N):
  y = uf.Find_Root(x)
  heapq.heappush(hs[y], a[x])
#print(hs)
c = 0
t = []
for x in range(N):
  if len(hs[x]):
    c += 1
    res += heapq.heappop(hs[x])
    if len(hs[x]): t.append(heapq.heappop(hs[x]))
t.sort()
#print(c, t, hs)
if len(t) < c - 2:
  print("Impossible")
  exit(0)
for i in range(max(0, c - 2)): res += t[i]
print(res)