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:
def main():
    import sys,heapq
    input = sys.stdin.readline

    n,m = map(int,input().split())
    a = tuple(map(int,input().split()))


    #Union Find
    par = [-1]*n
    #xの根を求める
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    #xとyの属する集合の併合
    def unite(x,y):
        x = find(x)
        y = find(y)

        if x == y:
            return False
        else:
            #sizeの大きいほうがx
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True

    #xとyが同じ集合に属するかの判定
    def same(x,y):
        return find(x) == find(y)

    #xが属する集合の個数
    def size(x):
        return -par[find(x)]


    for _ in [0]*m:
        x,y = map(int,input().split())
        unite(x,y)
    
    if m < (n-1)//2:
        print('Impossible')
        return
    
    h = [[] for _ in [0]*n]
    for i,e in enumerate(a):
        heapq.heappush(h[find(i)],e)
    
    root = []
    for i,e in enumerate(par):
        if e < 0:
            root.append(i)
    
    if len(root) == 1:
        print(0)
        return

    must = 0
    opt = []
    for i in root:
        must += heapq.heappop(h[i])
        for e in h[i]:
            opt.append(h[i].pop())


    print(must+sum(opt[:len(root)-2]))



if __name__ =='__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
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

#A
def A():

    return

#B
def B():

    return

#C
def C():

    return

#D
def D():
    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,m = LI()
    a = LI()
    rank = [0]*n
    par = [i for i in range(n)]
    for i in range(m):
        x,y = LI()
        if root(x) != root(y):
            unite(x,y)
    h = [[] for i in range(n)]
    l = []
    for i in range(n):
        ri = root(i)
        if ri == root(0):
            heappush(l,a[i])
        else:
            heappush(h[ri],a[i])

    ans = 0
    for i in range(n):
        ri = root(i)
        if ri != root(0):
            if not l or not h[ri]:
                print("Impossible")
                return
            x = heappop(l)
            y = heappop(h[ri])
            ans += x+y
            for y in h[ri]:
                heappush(l,y)
            unite(ri,0)
    print(ans)
    return

#E
def E():

    return

#F
def F():

    return

#G
def G():

    return

#H
def H():

    return

#I
def I_():

    return

#J
def J():

    return

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
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

#A
def A():

    return

#B
def B():

    return

#C
def C():

    return

#D
def D():
    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,m = LI()
    a = LI()
    rank = [0]*n
    par = [i for i in range(n)]
    for i in range(m):
        x,y = LI()
        if root(x) != root(y):
            unite(x,y)
    h = [[] for i in range(n)]
    l = []
    for i in range(n):
        ri = root(i)
        if ri == root(0):
            heappush(l,a[i])
        else:
            heappush(h[ri],a[i])
            
    ans = 0
    for i in range(n):
        ri = root(i)
        if ri != root(0):
            if not l or not h[ri]:
                print("Impossible")
                return
            unite(ri,0)
            x = heappop(l)
            y = heappop(h[ri])
            ans += x+y
            for y in h[ri]:
                heappush(l,y)
    print(ans)
    return

#E
def E():

    return

#F
def F():

    return

#G
def G():

    return

#H
def H():

    return

#I
def I_():

    return

#J
def J():

    return

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
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

#A
def A():

    return

#B
def B():

    return

#C
def C():

    return

#D
def D():
    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,m = LI()
    a = LI()
    rank = [0]*n
    par = [i for i in range(n)]
    for i in range(m):
        x,y = LI()
        if root(x) != root(y):
            unite(x,y)
    h = [[] for i in range(n)]
    l = []
    r = root(0)
    for i in range(n):
        ri = root(i)
        if ri == r:
            heappush(l,a[i])
        else:
            heappush(h[ri],a[i])
    ans = 0
    for i in range(n):
        ri = root(i)
        if ri != r:
            if not l or not h[ri]:
                print("Impossible")
                return
            unite(ri,r)
            x = heappop(l)
            y = heappop(h[ri])
            ans += x+y
            for y in h[ri]:
                heappush(l,y)
            r = root(r)
    print(ans)
    return

#E
def E():

    return

#F
def F():

    return

#G
def G():

    return

#H
def H():

    return

#I
def I_():

    return

#J
def J():

    return

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
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

#A
def A():

    return

#B
def B():

    return

#C
def C():

    return

#D
def D():
    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,m = LI()
    a = LI()
    rank = [0]*n
    par = [i for i in range(n)]
    for i in range(m):
        x,y = LI()
        if root(x) != root(y):
            unite(x,y)
    h = [[] for i in range(n)]
    for i in range(n):
        heappush(h[root(i)],a[i])
    ans = 0
    r = root(0)
    for i in range(n):
        ri = root(i)
        if ri != r:
            unite(ri,r)
            if not h[r] or not h[ri]:
                print("Impossible")
                return
            x = heappop(h[r])
            y = heappop(h[ri])
            ans += x+y
            for y in h[ri]:
                heappush(h[r],y)
    print(ans)
    return

#E
def E():

    return

#F
def F():

    return

#G
def G():

    return

#H
def H():

    return

#I
def I_():

    return

#J
def J():

    return

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

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


parent_data = []

def union(ind):
    global parent_data
    if parent_data[ind] != ind:
        parent_data[ind] = union(parent_data[ind])
    return parent_data[ind]


def main():
    node_num, edge_num = map(int, input().split())
    cost_data = list(map(int, input().split()))
    data = [list(map(int, input().split())) for i in range(edge_num)]

    global parent_data
    parent_data = [i for i in range(node_num)]

    for i in range(edge_num):
        a, b = data[i]
        parent_a = union(a)
        parent_b = union(b)
        parent_data[min(parent_a, parent_b)] = max(parent_a, parent_b)

    parent_count = defaultdict(int)
    cost_heap = defaultdict(list)
    for i in range(node_num):
        parent_i = union(i)
        parent_count[parent_i] += 1
        heapq.heappush(cost_heap[parent_i], (cost_data[i], parent_i))

    parent_count = list(sorted(parent_count.items(), key=lambda x:-x[1]))

    ans = 0
    ori_ind, ori_count = parent_count[0]
    for i in range(len(parent_count) - 1):
        now_ind, now_count = parent_count[i + 1]
        if len(cost_heap[ori_ind]) == 0:
            print('Impossible')
            sys.exit()
        ori_cost, o_ind = heapq.heappop(cost_heap[ori_ind])
        now_cost, n_ind = heapq.heappop(cost_heap[now_ind])
        ans += ori_cost + now_cost
        if len(cost_heap[o_ind]) > 0 and o_ind != ori_ind:
            heapq.heappush(cost_heap[ori_ind], (heapq.heappop(cost_heap[o_ind]), o_ind))

    print(ans)






if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


parent_data = []

def union(ind):
    global parent_data
    if parent_data[ind] != ind:
        parent_data[ind] = union(parent_data[ind])
    return parent_data[ind]


def main():
    node_num, edge_num = map(int, input().split())
    cost_data = list(map(int, input().split()))
    data = [list(map(int, input().split())) for i in range(edge_num)]

    global parent_data
    parent_data = [i for i in range(node_num)]

    for i in range(edge_num):
        a, b = data[i]
        parent_a = union(a)
        parent_b = union(b)
        parent_data[min(parent_a, parent_b)] = max(parent_a, parent_b)

    parent_count = defaultdict(int)
    cost_heap = defaultdict(list)
    for i in range(node_num):
        parent_i = union(i)
        parent_count[parent_i] += 1
        heapq.heappush(cost_heap[parent_i], cost_data[i])

    parent_count = list(sorted(parent_count.items(), key=lambda x:-x[1]))

    ans = 0
    ori_ind, ori_count = parent_count[0]
    for i in range(len(parent_count) - 1):
        now_ind, now_count = parent_count[i + 1]
        if len(cost_heap[ori_ind]) == 0:
            print('Impossible')
            sys.exit()
        ori_cost = heapq.heappop(cost_heap[ori_ind])
        now_cost = heapq.heappop(cost_heap[now_ind])
        ans += ori_cost + now_cost
        if len(cost_heap[now_ind]) > 0:
            heapq.heappushpop(cost_heap[ori_ind], heapq.heappop(cost_heap[now_ind]))

        # cost_heap[ori_ind] = list(heapq.merge(cost_heap[ori_ind], cost_heap[now_ind])

    print(ans)





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


parent_data = []

def union(ind):
    global parent_data
    if parent_data[ind] != ind:
        parent_data[ind] = union(parent_data[ind])
    return parent_data[ind]


def main():
    node_num, edge_num = map(int, input().split())
    cost_data = list(map(int, input().split()))
    data = [list(map(int, input().split())) for i in range(edge_num)]

    global parent_data
    parent_data = [i for i in range(node_num)]

    for i in range(edge_num):
        a, b = data[i]
        parent_a = union(a)
        parent_b = union(b)
        parent_data[min(parent_a, parent_b)] = max(parent_a, parent_b)

    parent_count = defaultdict(int)
    cost_heap = defaultdict(list)
    for i in range(node_num):
        parent_i = union(i)
        parent_count[parent_i] += 1
        heapq.heappush(cost_heap[parent_i], cost_data[i])

    parent_count = list(sorted(parent_count.items(), key=lambda x:-x[1]))

    ans = 0
    ori_ind, ori_count = parent_count[0]
    for i in range(len(parent_count) - 1):
        now_ind, now_count = parent_count[i + 1]
        if len(cost_heap[ori_ind]) == 0:
            print('Impossible')
            sys.exit()
        ori_cost = heapq.heappop(cost_heap[ori_ind])
        now_cost = heapq.heappop(cost_heap[now_ind])
        ans += ori_cost + now_cost

    print(ans)





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(R, i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R, R[i])
    return R[i]
def union(i, j):
  Ri = root(R, i)
  Rj = root(R, j)
  if A[Ri] <= A[Rj]:
    R[Rj] = i
  else:
    R[Ri] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  R[i] = root(R, i)
if M < N // 2 - 1:
  print('Impossible')
elif M == N - 1:
  print(0)
else:
  cnt= 0
  E = N - M - 2
  C = [0] * N
  F = sorted([[a, R[i]] for i, a in enumerate(A)])
  for a, r in F:
    if C[r] == 0:
      C[r] = a
      cnt += a
    elif E > 0:
      cnt += a
      E -= 1
  print(cnt)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(R, i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R, R[i])
    return R[i]
def union(i, j):
  Ri = root(R, i)
  Rj = root(R, j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  R[i] = root(R, i)
f = len(list(set(R)))
if f > N // 2 + 1:
  print('Impossible')
elif f == 1:
  print(0)
else:
  cnt= 0
  _f = f - 2
  C = [0] * N
  Q = []
  F = sorted([[a, i] for i, a in enumerate(A)])
  for a, i in F:
    if C[R[i]] == 0:
      C[R[i]] = A[i]
      cnt += A[i]
    elif _f > 0:
      cnt += A[i]
      _f -= 1
  print(cnt)

Submission status: Wrong Answer

Solution code:
import heapq
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(R, i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R, R[i])
    return R[i]
def union(i, j):
  Ri = root(R, i)
  Rj = root(R, j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  R[i] = root(R, i)
f = len(list(set(R)))
if f > N // 2 + 1:
  print('Impossible')
elif f == 1:
  print(0)
else:
  cnt= 0
  _f = f - 2
  C = [0] * N
  Q = []
  F = sorted([[a, i] for i, a in enumerate(A)])
  for a, i in F:
    if C[R[i]] == 0:
      C[R[i]] = A[i]
      cnt += A[i]
    elif _f:
      cnt += A[i]
      f -= 1
  print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

N,M = map(int,input().split())
A = np.array(input().split(),dtype=np.int64)
XY = [[int(x) for x in input().split()] for _ in range(M)]

if M>0:
    X,Y = zip(*XY)
else:
    X,Y = [],[]
n_comp,comp = connected_components(csr_matrix(([1]*M,(X,Y)),(N,N)))

i = np.lexsort((A,comp))
A = A[i]; comp = comp[i]

i = np.concatenate([[0],np.where(comp[1:] != comp[:-1])[0]+1])

cost = A[i].sum()
A = np.delete(A,i)
rest = 2 * (n_comp-1) - len(i)
if n_comp == 1:
    print(0)
elif rest > len(A):
    print('Impossible')
else:
    cost += A[:rest].sum()
    print(cost)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
AA=[]
D=dict()
for i in range(n):
  AA.append((A[i],i))
  D[i]=A[i]
AA.sort(key=lambda x:(x[0],x[1]))
par=[-1]*n

def find(x):
  if par[x]<0:
    return x
  else:
    par[x]=find(par[x])
    return par[x]

def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return False
  else:
    if par[x]>par[y]:
      x,y=y,x
    par[x]+=par[y]
    par[y]=x
    return True

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

def size(x):
  return -par[find(x)]
Edge=[[] for _ in range(n)]
for i in range(m):
  x,y=map(int,input().split())
  unite(x,y)
  Edge[x].append(y)
  Edge[y].append(x)
ans=0
Used=[False]*n
import heapq
Q=[]
chk=True
cur_a,cur_v=AA[0]
Used[0]=True
Stack=Edge[0]
while Stack:
  e=Stack.pop()
  if not Used[e]:
    heapq.heappush(Q,(D[e],e))
    Used[e]=True
  for ee in Edge[e]:
    if not Used[ee]:
      Stack.append(ee)
for i in range(1,n):
  a,v=AA[i]
  if same(cur_v,v):
    continue
  else:
    ans+=cur_a+a
    unite(cur_v,v)
    Used[v]=True
    Stack=Edge[v]
    while Stack:
      e=Stack.pop()
      if not Used[e]:
        heapq.heappush(Q,(D[e],e))
        Used[e]=True
      for ee in Edge[e]:
        if not Used[ee]:
          Stack.append(ee)
    if size(cur_v)==n:
      break
    elif Q:
      cur_a,cur_v=heapq.heappop(Q)
    else:
      chk=False
print(ans if chk==True else "Impossible")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
AA=[]
D=dict()
for i in range(n):
  AA.append((A[i],i))
  D[i]=A[i]
AA.sort(key=lambda x:(x[0],x[1]))
par=[-1]*n

def find(x):
  if par[x]<0:
    return x
  else:
    par[x]=find(par[x])
    return par[x]

def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return False
  else:
    if par[x]>par[y]:
      x,y=y,x
    par[x]+=par[y]
    par[y]=x
    return True

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

def size(x):
  return -par[find(x)]
Edge=[[] for _ in range(n)]
for i in range(m):
  x,y=map(int,input().split())
  unite(x,y)
  Edge[x].append(y)
  Edge[y].append(x)
ans=0
Used=[False]*n
import heapq
Q=[]
chk1,chk2=True,True
cur_a,cur_v=AA[0]
Used[0]=True
while Edge[0]:
  e=Edge[0].pop()
  heapq.heappush(Q,(D[e],e))
  Used[e]=True
for i in range(1,n):
  a,v=AA[i]
  if same(cur_v,v):
    continue
  else:
    if not chk1:
      chk2=False
    else:
      ans+=cur_a+a
      unite(cur_v,v)
      Used[v]=True
      while Edge[v]:
        e=Edge[v].pop()
        if not Used[e]:
          heapq.heappush(Q,(D[e],e))
          Used[e]=True
      if Q:
        cur_a,cur_v=heapq.heappop(Q)
      else:
        chk1=False
print(ans if chk2==True else "Impossible")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
AA=[]
D=dict()
for i in range(n):
  AA.append((A[i],i))
  D[i]=A[i]
AA.sort(key=lambda x:(x[0],x[1]))
par=[-1]*n

def find(x):
  if par[x]<0:
    return x
  else:
    par[x]=find(par[x])
    return par[x]

def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return False
  else:
    if par[x]>par[y]:
      x,y=y,x
    par[x]+=par[y]
    par[y]=x
    return True

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

def size(x):
  return -par[find(x)]
Edge=[[] for _ in range(n)]
for i in range(m):
  x,y=map(int,input().split())
  unite(x,y)
  Edge[x].append(y)
  Edge[y].append(x)
ans=0
Used=[False]*n
import heapq
Q=[]
chk=True
cur_a,cur_v=AA[0]
Used[0]=True
while Edge[0]:
  e=Edge[0].pop()
  heapq.heappush(Q,(D[e],e))
  Used[e]=True
for i in range(1,n):
  a,v=AA[i]
  if same(cur_v,v):
    continue
  else:
    ans+=cur_a+a
    unite(cur_v,v)
    Used[v]=True
    while Edge[v]:
      e=Edge[v].pop()
      if not Used[e]:
        heapq.heappush(Q,(D[e],e))
        Used[e]=True
    if Q:
      cur_a,cur_v=heapq.heappop(Q)
    else:
      chk=False
print(ans if chk==True else "Impossible")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
AA=[]
D=dict()
for i in range(n):
  AA.append((A[i],i))
  D[i]=A[i]
AA.sort(key=lambda x:(x[0],x[1]))
par=[-1]*n

def find(x):
  if par[x]<0:
    return x
  else:
    par[x]=find(par[x])
    return par[x]

def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return False
  else:
    if par[x]>par[y]:
      x,y=y,x
    par[x]+=par[y]
    par[y]=x
    return True

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

def size(x):
  return -par[find(x)]
Edge=[[] for _ in range(n)]
for i in range(m):
  x,y=map(int,input().split())
  unite(x,y)
  Edge[x].append(y)
  Edge[y].append(x)
ans=0
Used=[False]*n
import heapq
Q=[]
chk=True
cur_a,cur_v=AA[0]
Used[0]=True
while Edge[0]:
  e=Edge[0].pop()
  heapq.heappush(Q,(D[e],e))
for i in range(1,n):
  a,v=AA[i]
  if same(cur_v,v):
    continue
  else:
    ans+=cur_a+a
    unite(cur_v,v)
    Used[cur_v]=True
    Used[v]=True
    while Edge[v]:
      e=Edge[v].pop()
      if not Used[e]:
        heapq.heappush(Q,(D[e],e))
    if Q:
      cur_a,cur_v=heapq.heappop(Q)
    else:
      chk=False
print(ans if chk==True else "Impossible")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
AA=[]
D=dict()
for i in range(n):
  AA.append((A[i],i))
  D[i]=A[i]
AA.sort(key=lambda x:(x[0],x[1]))
par=[-1]*n

def find(x):
  if par[x]<0:
    return x
  else:
    par[x]=find(par[x])
    return par[x]

def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return False
  else:
    if par[x]>par[y]:
      x,y=y,x
    par[x]+=par[y]
    par[y]=x
    return True

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

def size(x):
  return -par[find(x)]
Edge=[[] for _ in range(n)]
for i in range(m):
  x,y=map(int,input().split())
  unite(x,y)
  Edge[x].append(y)
  Edge[y].append(x)
ans=0
Used=[False]*n
import heapq
Q=[]
chk=True
cur_a,cur_v=AA[0]
Used[0]=True
while Edge[0]:
  e=Edge[0].pop()
  heapq.heappush(Q,(D[e],e))
for i in range(1,n):
  a,v=AA[i]
  if same(cur_v,v):
    continue
  else:
    ans+=cur_a+a
    unite(cur_v,v)
    Used[v]=True
    while Edge[v]:
      e=Edge[v].pop()
      if not Used[e]:
        heapq.heappush(Q,(D[e],e))
    if Q:
      cur_a,cur_v=heapq.heappop(Q)
    else:
      chk=False
print(ans if chk==True else "Impossible")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
AA=[]
for i in range(n):
  AA.append((A[i],i))
AA.sort(key=lambda x:(x[0],x[1]))
par=[-1]*n

def find(x):
  if par[x]<0:
    return x
  else:
    par[x]=find(par[x])
    return par[x]

def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return False
  else:
    if par[x]>par[y]:
      x,y=y,x
    par[x]+=par[y]
    par[y]=x
    return True

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

def size(x):
  return -par[find(x)]

for i in range(m):
  x,y=map(int,input().split())
  unite(x,y)
ans=0
import heapq
Q=[]
chk=True
cur_a,cur_v=AA[0]
for i in range(1,n):
  a,v=AA[i]
  if same(cur_v,v):
    heapq.heappush(Q,(a,v))
  else:
    ans+=cur_a+a
    unite(cur_v,v)
    if Q:
      cur_a,cur_v=heapq.heappop(Q)
    else:
      chk=False
print(ans if chk==True else "Impossible")

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def root(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.root(x)]


def argsort(li):
    return [i for _, i in sorted([(a, i) for i, a in enumerate(li)])]

N, M = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
XY = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

uf = UnionFind(size=N)
for x, y in XY:
    uf.unite(x, y)

ans = 0
idx = argsort(A)
used = [0] * N
l = 0
r = 1
while l < N:
    while r < N and (used[idx[r]] or uf.root(idx[l]) == uf.root(idx[r])):
        r += 1
    if r >= N:
        break
    ans += A[idx[l]] + A[idx[r]]
    uf.unite(idx[l], idx[r])
    used[idx[l]] = True
    used[idx[r]] = True
    while l < N and used[idx[l]]:
        l += 1
    r = l + 1

if uf.size(0) == N:
    print(ans)
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def root(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.root(x)]


N, M = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
XY = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

uf = UnionFind(size=N)
for x, y in XY:
    uf.unite(x, y)

ans = 0
A = np.array(A, dtype=int)
idx = A.argsort()
used = [0] * N
l = 0
r = 1
while l < N:
    while r < N and (used[idx[r]] or uf.root(idx[l]) == uf.root(idx[r])):
        r += 1
    if r >= N:
        break
    ans += A[idx[l]] + A[idx[r]]
    uf.unite(idx[l], idx[r])
    used[idx[l]] = True
    used[idx[r]] = True
    while l < N and used[idx[l]]:
        l += 1
    r = l + 1

if uf.size(0) == N:
    print(ans)
else:
    print('Impossible')