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:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



def main():
    n,m = map(int, input().split())
    al = list(map(int, input().split()))    
    uf = UnionFind(n)
    for _ in range(m):
        x,y = map(int, input().split())
        uf.union(x,y)

    first_min = []
    second_min = []
    INF = 10**9
    roots = uf.roots()

    if len(roots) == 1:
        print(0)
        exit()

    one_cnts = 0
    for r in roots:
        c_first_min = INF
        c_second_min = INF
        members = uf.members(r)
        if len(members) == 1: one_cnts += 1
        for m in members:
            v = al[m]
            if v < c_first_min:
                c_second_min = c_first_min
                c_first_min = v
            elif v < c_second_min:
                c_second_min = v
        first_min.append(c_first_min)
        if c_second_min != INF:
            second_min.append(c_second_min)

    if one_cnts > 2:
        print('Impossible')
        exit()

    # print(first_min)
    # print(second_min)
    ans = sum(first_min)
    second_min.sort(reverse=True)
    ans += sum(second_min[2:])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
from collections import defaultdict

class MeldableHeap():
    def __init__(self):
        self.size = 0
        self.heap = list()
        self.added = 0

    def top(self):
        if not self.heap:
            return None
        return self.heap[0] + self.added

    def pop(self):
        if not self.heap:
            return None
        res = heappop(self.heap)
        self.size -= 1
        return res + self.added

    def push(self, x):
        heappush(self.heap, x - self.added)
        self.size += 1

    def add(self, x):
        self.added += x

    def meld(self, other): #破壊的
        res = MeldableHeap()
        if self.size < other.size:
            self, other = other, self
        res.heap = self.heap
        res.size = self.size
        for _ in range(other.size):
            res.push(other.pop() - self.added)
        return res

N, M = map(int, input().split())
A = list(map(int, input().split()))
edge = [tuple(map(int, input().split())) for _ in range(M)]

graph = [[] for _ in range(N)]

for x, y in edge:
    graph[x].append(y)
    graph[y].append(x)

used = [0 for _ in range(N)]
heap = defaultdict(MeldableHeap)
roots = []

for root in range(N):
    if used[root]:
        continue
    roots.append(root)
    heap[root].push(A[root])
    used[root] = 1
    stack = [root]
    while stack:
        node = stack.pop()
        for adj in graph[node]:
            if used[adj]:
                continue
            used[adj] = 1
            heap[root].push(A[adj])
            stack.append(adj)

single = set()

for k, v in heap.items():
    if v.size == 1:
        single.add(k)

roots.sort(key=lambda x: x in single)

res = 0
tmp = heap[roots[0]]

for i in range(1, len(roots)):
    v = heap[roots[i]]
    a = tmp.pop()
    b = v.pop()
    tmp = tmp.meld(v)
    if tmp.size == 0:
        print('Impossible')
        break
    res += a + b
else:
    print(res)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
from collections import defaultdict

class MeldableHeap():
    def __init__(self):
        self.size = 0
        self.heap = list()
        self.added = 0

    def top(self):
        if not self.heap:
            return None
        return self.heap[0] + self.added

    def pop(self):
        if not self.heap:
            return None
        res = heappop(self.heap)
        self.size -= 1
        return res + self.added

    def push(self, x):
        heappush(self.heap, x - self.added)
        self.size += 1

    def add(self, x):
        self.added += x

    def meld(self, other): #破壊的
        res = MeldableHeap()
        if self.size < other.size:
            self, other = other, self
        res.heap = self.heap
        res.size = self.size
        for _ in range(other.size):
            res.push(other.pop() - self.added)
        return res

N, M = map(int, input().split())
A = list(map(int, input().split()))
edge = [tuple(map(int, input().split())) for _ in range(M)]

graph = [[] for _ in range(N)]

for x, y in edge:
    graph[x].append(y)
    graph[y].append(x)

used = [0 for _ in range(N)]
heap = defaultdict(MeldableHeap)
roots = []

for root in range(N):
    if used[root]:
        continue
    heap[root].push(A[root])
    used[root] = 1
    roots.append(root)
    stack = [root]
    while stack:
        node = stack.pop()
        for adj in graph[node]:
            if used[adj]:
                continue
            used[adj] = 1
            heap[root].push(A[adj])
            stack.append(adj)

res = 0
tmp = heap[roots[0]]

for i in range(1, len(roots)):
    h = heap[roots[i]]
    a = tmp.pop()
    b = h.pop()
    tmp = tmp.meld(h)
    if tmp.size == 0:
        print('Impossible')
        break
    res += a + b
else:
    print(res)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
f=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  f[x].append(y)
  f[y].append(x)
if (n-m-1)*2>n:
  print('Impossible')
  exit()
from heapq import heappop,heappush,heapify
mi=set(list(range(n)))
ary=[]
dg1c=[]
while mi:
  gk=mi.pop()
  todo=[gk]
  while todo:
    v=todo.pop()
    ary.append([a[v],gk])
    for nv in f[v]:
      if nv in mi:
        todo.append(nv)
        mi.discard(nv)
# 連結成分の個数
ren=n-m
# 必要な辺をはるのに必要な頂点の数
ne=(n-m-1)*2
d={}
cnt=0
ans=0
ary.sort(key=lambda x:x[0],reverse=True)
#print(ary)
while cnt<ne and ary:
  c,gk=ary.pop()
  if gk in d:
    if d[gk]<ne//2:
      ans+=c
      d[gk]+=1
      cnt+=1
  else:
    ans+=c
    d[gk]=1
    cnt+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
f=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  f[x].append(y)
  f[y].append(x)
if m==n-1:
  print(0)
  exit()
if (n-m-1)*2>n:
  print('Impossible')
  exit()
from heapq import heappop,heappush,heapify
mi=set(list(range(n)))
dg={}
dg1c=[]
while mi:
  gk=mi.pop()
  if len(f[gk])==0:
    dg1c.append(a[gk])
    continue
  todo=[gk]
  dg[gk]=[]
  while todo:
    v=todo.pop()
    dg[gk].append(a[v])
    for nv in f[v]:
      if nv in mi:
        todo.append(nv)
        mi.discard(nv)
# 頂点が2以上ある連結成分の個数
ren=n-m-len(dg1c)
topheap=[]
ans=0
#print(dg)
#print(f)
#print(dg1c)
for k in dg.keys():
  dg[k].sort()
  heapify(dg[k])
  heappush(topheap,[heappop(dg[k]),k])
for _ in range(ren-1):
  c1,k1=heappop(topheap)
  c2,k2=heappop(topheap)
  ans+=c1+c2
  while dg[k1]:
    heappush(dg[k2],dg[k1].pop())
  dg.pop(k1)
  if dg[k2]:
    heappush(topheap,[heappop(dg[k2]),k2])
    if not dg[k2]:dg.pop(k2)
# 頂点2個以上の連結成分は一個だけになっている
# そのコストはtopheapに一個、のこりはdg[k]にある
if dg1c:
  ans+=heappop(topheap)[0]
if len(dg1c)>1:
  keys=set(dg.keys())
  k0=keys.pop()
  for i in range(len(dg1c)-1):
    c=heappop(dg[k0])
    ans+=c
#print(dg1c)
print(ans+sum(dg1c))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
f=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  f[x].append(y)
  f[y].append(x)
if m==n-1:
  print(0)
  exit()
from heapq import heappop,heappush
mi=set(list(range(n)))
dg={}
dg1c=[]
while mi:
  gk=mi.pop()
  if len(f[gk])==0:
    dg1c.append(a[gk])
    continue
  todo=[gk]
  dg[gk]=[]
  while todo:
    v=todo.pop()
    heappush(dg[gk],a[v])
    for nv in f[v]:
      if nv in mi:
        todo.append(nv)
        mi.discard(nv)
# 頂点が2以上ある連結成分の個数
ren=n-m-len(dg1c)
topheap=[]
ans=0
#print(dg)
#print(f)
#print(dg1c)
for k in dg.keys():
  heappush(topheap,[heappop(dg[k]),k])
for _ in range(ren-1):
  if not topheap:
    print('Impossible')
    exit()
  c1,k1=heappop(topheap)
  if not topheap:
    print('Impossible')
    exit()
  c2,k2=heappop(topheap)
  ans+=c1+c2
  for c in dg[k1]:
    heappush(dg[k2],c)
  if dg[k2]:heappush(topheap,[heappop(dg[k2]),k2])
for c1 in dg1c:
  ans+=c1
  if not topheap:
    print('Impossible')
    exit()
  c,k=heappop(topheap)
  ans+=c
  if dg[k]:heappush(topheap,[heappop(dg[k]),k])
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
f=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  f[x].append(y)
  f[y].append(x)
if m==n-1:
  print(0)
  exit()
from heapq import heappop,heappush
mi=set(list(range(n)))
dg={}
dg1c=[]
while mi:
  gk=mi.pop()
  if len(f[gk])==0:
    dg1c.append(a[gk])
    continue
  todo=[gk]
  dg[gk]=[]
  while todo:
    v=todo.pop()
    heappush(dg[gk],a[v])
    for nv in f[v]:
      if nv in mi:
        todo.append(nv)
        mi.discard(nv)
# 頂点が2以上ある連結成分の個数
ren=n-m-len(dg1c)
topheap=[]
ans=0
#print(dg)
#print(f)
#print(dg1c)
for k in dg.keys():
  heappush(topheap,[heappop(dg[k]),k])
for _ in range(ren-1):
  if not topheap:
    print('Impossible')
    exit()
  c1,k1=heappop(topheap)
  if not topheap:
    print('Impossible')
    exit()
  c2,k2=heappop(topheap)
  ans+=c1+c2
  for c in dg[k1]:
    heappush(dg[k2],c)
  if dg[k2]:heappush(topheap,[heappop(dg[k2]),k2])
for c1 in dg1c:
  ans+=c1
  if not topheap:
    print('Impossible')
  exit()
  c,k=heappop(topheap)
  ans+=c
  if dg[k]:heappush(topheap,[heappop(dg[k]),k])
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
if N-1==M or N==1:
  print(0)
  exit()
A=list(map(int,input().split()))
belong=list()
group=list()

def init(X):
  global belong
  global group
  belong=list(range(X))
  group=[[i] for i in range(X)]

def unite(x,y):
  if len(group[belong[x]])<len(group[belong[y]]):
    x,y=y,x
  if belong[x]==belong[y]:
    return True
  z=belong[y]
  for i in range(len(group[z])):
    belong[group[z][-1]]=belong[x]
    group[belong[x]].append(group[z][-1])
    del group[z][-1]
  return False

init(N)
x,y=0,0
for i in range(M):
  x,y=map(int,input().split())
  unite(x,y)
x=0
for i in range(N):
  if len(group[i])==1:
    x+=1
if x>=3:
  print('Impossible')
  exit()
P=0
Z=[]
for i in range(N):
  if len(group[i]):
    Z.append([])
    for j in range(len(group[i])):
      Z[-1].append(A[group[i][j]])
    Z[-1].sort()
    Z[-1]=Z[-1][:2]
P=sum([sum(Z[i]) for i in range(len(Z))])
B=[]
for i in range(len(Z)):
  if len(Z[i])==2:
    B.append(Z[i][1])
B.sort(reverse=True)
x=2-x
if len(B)<x:
  print('Impossible')
  exit()
P-=sum(B[:x])
print(P)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


class UnionFind:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            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:
            # 高い方をxとする。
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            # 同じ高さの時は高さ+1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # yの親をxとし、xのサイズにyのサイズを加える
            self.par[x] += self.par[y]
            self.par[y] = x

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]

n,m = readints()

a = readints()

u = UnionFind(n)
for i in range(m):
    x,y = readints()
    u.unite(x,y)

for i in range(n):
    u.find(i)

b = {}
for i in range(n):
    if u.par[i]<0:
        b[i] = (a[i],i)

for i,p in enumerate(u.par):    
    if p>=0 and b[p][0]>a[i]:
        b[p] = (a[i],i)

for v in b.values():
    a[v[1]]==10**10

a.sort()
if n < len(b)*2-2:
    print('Impossible')
elif len(b)==1:
    print(0)
else:
    print(sum([x[0] for x in b.values()]) + sum(a[:len(b)-2]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


class UnionFind:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            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:
            # 高い方をxとする。
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            # 同じ高さの時は高さ+1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # yの親をxとし、xのサイズにyのサイズを加える
            self.par[x] += self.par[y]
            self.par[y] = x

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]

n,m = readints()

a = readints()

u = UnionFind(n)
for i in range(m):
    x,y = readints()
    u.unite(x,y)

for i in range(n):
    u.find(i)

b = {}
for i in range(n):
    if u.par[i]<0:
        b[i] = a[i]

for i,p in enumerate(u.par):    
    if p>=0:
        b[p] = min(b[p],a[i])

for k in b.keys():
    a[k]==10**10

a.sort()
if n < len(b)*2-2:
    print('Impossible')
elif len(b)==1:
    print(0)
else:
    print(sum(b.values()) + sum(a[:len(b)-2]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


class UnionFind:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            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:
            # 高い方をxとする。
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            # 同じ高さの時は高さ+1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # yの親をxとし、xのサイズにyのサイズを加える
            self.par[x] += self.par[y]
            self.par[y] = x

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]

n,m = readints()

a = readints()

u = UnionFind(n)
for i in range(m):
    x,y = readints()
    u.unite(x,y)

for i in range(n):
    u.find(i)

b = {}
for i in range(n):
    if u.par[i]<0:
        b[i] = a[i]

for i,p in enumerate(u.par):    
    if p>=0:
        b[p] = min(b[p],a[i])

for k in b.keys():
    a[k]==10**10

a.sort()
if n < len(b)*2-2:
    print('Impossible')
elif n==1:
    print(0)
else:
    print(sum(b.values()) + sum(a[:len(b)-2]))

Submission status: Wrong Answer

Solution code:
class UF:
    def __init__(self, N):
        self.uf = [-1]*N
        self.n = N

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

    def size(self, x):
        return -self.uf[self.find(x)]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size(x) > self.size(y): x, y = y, x
        self.uf[y] += self.uf[x]
        self.uf[x] = y
        self.n -= 1
        
N, M = map(int, input().split())
A = list(map(int, input().split()))
uf = UF(N)
for _ in range(M):
    x, y = map(int, input().split())
    uf.union(x,y)

D = {}
for x, a in enumerate(A):
    c = uf.find(x)
    if c not in D: D[c]=[]
    D[c].append(a)

ans = 0
L = []
for d in D.values():
    d.sort()
    ans += d[0]
    L += d[1:]
    print(d[0])

print(L, ans)
L.sort()

P = len(D)-2

if len(D)==1:
    ans = 0
elif len(L)>=P:
    ans += sum(L[:len(D)-2])
else:
    ans = 'Impossible'

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush

n,m = map(int,readline().split())
a = list(map(int,readline().split()))
xy = list(map(int,read().split()))

if(n==1):
    print(0)
    exit()

sys.setrecursionlimit(10**9)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def size(self, x):
        return self.parents[ self.find(x) ] * -1

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

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if(x_root == y_root):
            return

        if( self.parents[x_root] <= self.parents[y_root] ):
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def members(self,x):
        root = self.find(x)
        ret = [ i for i in range(self.n) if self.find(i) == root ]
        return ret

    def roots(self):
        ret = [ i for i in range(self.n) if self.parents[i] < 0]
        return ret

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(n)
hqs = [[] for _ in range(n)]
hq_min = []
one_edge = []

it = iter(xy)
for x,y in zip(it,it):
    uf.union(x,y)

inf = 10**10
cnt_1 = 0
for i in range(n):
    add = 0
    root = uf.find(i)
    if(uf.size(i) == 1):
        add = inf
        cnt_1 += 1
    heappush(hqs[root], (a[i]+add, i))

for i in range(n):
    if(hqs[i]):
        min_i = heappop(hqs[i])
        heappush(hq_min, min_i)

ans = 0
while(uf.size(0) < n):
    if(len(hq_min) < 2):
        print('Impossible')
        exit()
    i = heappop(hq_min)
    j = heappop(hq_min)
    ans += i[0]+j[0]
    i_root = uf.find(i[1])
    j_root = uf.find(j[1])
    uf.union(i[1],j[1])
    root = uf.find(i[1])
    if(root == i_root):
        child = j_root
    else:
        child = i_root
    while(hqs[child]):
        k = hqs[child].pop()
        heappush(hqs[root], k)

    if(hqs[root]):
        k = heappop(hqs[root])
        heappush(hq_min,k)

ans -= inf * cnt_1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush

n,m = map(int,readline().split())
a = list(map(int,readline().split()))
xy = list(map(int,read().split()))

sys.setrecursionlimit(10**9)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def size(self, x):
        return self.parents[ self.find(x) ] * -1

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

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if(x_root == y_root):
            return

        if( self.parents[x_root] <= self.parents[y_root] ):
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def members(self,x):
        root = self.find(x)
        ret = [ i for i in range(self.n) if self.find(i) == root ]
        return ret

    def roots(self):
        ret = [ i for i in range(self.n) if self.parents[i] < 0]
        return ret

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(n)
hqs = [[] for _ in range(n)]
hq_min = []

it = iter(xy)
for x,y in zip(it,it):
    uf.union(x,y)

for i in range(n):
    root = uf.find(i)
    heappush(hqs[root], (a[i], i))

for i in range(n):
    if(hqs[i]):
        min_i = heappop(hqs[i])
        heappush(hq_min, min_i)

ans = 0
while(uf.size(0) < n):
    if(len(hq_min) < 2):
        print('Impossible')
        exit()
    i = heappop(hq_min)
    j = heappop(hq_min)
    ans += i[0]+j[0]
    i_root = uf.find(i[1])
    j_root = uf.find(j[1])
    uf.union(i[1],j[1])
    root = uf.find(i[1])
    if(root == i_root):
        child = j_root
    else:
        child = i_root
    while(hqs[child]):
        k = hqs[child].pop()
        heappush(hqs[root], k)

    if(hqs[root]):
        k = heappop(hqs[root])
        heappush(hq_min,k)

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [-1]*n

    def find(self,x): #根を見つける、繋ぎ直す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def unite(self,x,y): #x,yの含むグループを併合する
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x,y = y,x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def same(self,x,y):#xとyが同じグループにいるか判定
        return self.find(x) == self.find(y)
    
    def members(self,x):#xと同じグループのメンバーを列挙
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def size(self,x):#xが属するグループのメンバーの数
        return -self.parents[self.find(x)]
    
    def roots(self):#ufの根を列挙
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):#グループの数を数える
        return len(self.roots())

    def all_group_members(self):#根:メンバの辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):#print()での表示用
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
from heapq import heapify,heappop,heappush

def main():
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    uf = UnionFind(N)
    for _ in range(M):
        a,b = map(int,input().split())
        uf.unite(a,b)
    A = list(enumerate(A))
    A.sort(key = lambda x:x[1])
    q = []
    ans = 0
    for i,a in A:
        if len(q) == 0:
            heappush(q,(a,i))
        elif uf.same(i,q[0][1]):
            heappush(q,(a,i))
        else:
            p,j = heappop(q)
            uf.unite(j,i)
            ans += p + a
    if len(uf.roots()) == 1:
        print(ans)
    else:
        print('Impossible')
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from heapq import heapify,heappop,heappush
def main():
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    cnt = N - M - 1
    G = [[] for _ in range(N)]
    for _ in range(M):
        x,y = map(int,input().split())
        G[x].append(y)
        G[y].append(x)
    
    unite = []
    min_val = []
    visited = [-1] * N
    for i in range(N):
        if visited[i] < 0:
            q = [A[i]]
            visited[i] = 1
            stack = [i]
            while stack:
                v = stack.pop()
                for e in G[v]:
                    if visited[e] >= 0:
                        continue
                    visited[e] = 1
                    heappush(q,A[e])
                    stack.append(e)
            unite.append(q)
            heappush(min_val,(q[0],len(min_val)))
    
    ans = 0
    for _ in range(cnt):
        if len(min_val) <= 1:
            ans = -1
            break
        m1,i1 = heappop(min_val)
        m2,i2 = heappop(min_val)
        ans += m1 + m2
        heappop(unite[i1])
        heappop(unite[i2])
        if len(unite[i1]) > len(unite[i2]):
            while len(unite[i2]):
                v = heappop(unite[i2])
                heappush(unite[i1],v)
            if len(unite[i1]):
                heappush(min_val,(unite[i1][0],i1))
        else:
            while len(unite[i1]):
                v = heappop(unite[i1])
                heappush(unite[i2],v)
            if len(unite[i2]):
                heappush(min_val,(unite[i2][0],i2))
    print(ans if ans >= 0 else 'Impossible')
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from heapq import heapify,heappop,heappush
def main():
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    cnt = N - M - 1
    G = [[] for _ in range(N)]
    for _ in range(M):
        x,y = map(int,input().split())
        G[x].append(y)
        G[y].append(x)
    
    unite = []
    min_val = []
    visited = [-1] * N
    for i in range(N):
        if visited[i] < 0:
            q = [A[i]]
            visited[i] = 1
            stack = [i]
            while stack:
                v = stack.pop()
                for e in G[v]:
                    if visited[e] >= 0:
                        continue
                    visited[e] = 1
                    heappush(q,A[e])
                    stack.append(e)
            unite.append(q)
            heappush(min_val,(q[0],len(min_val)))
    
    ans = 0
    for _ in range(cnt):
        if len(min_val) <= 1:
            ans = -1
            break
        m1,i1 = heappop(min_val)
        m2,i2 = heappop(min_val)
        ans += m1 + m2
        heappop(unite[i1])
        heappop(unite[i2])
        if len(unite[i1]) > 0:
            heappush(min_val,(unite[i1][0],i1))
        if len(unite[i2]) > 0:
            heappush(min_val,(unite[i2][0],i2))
    print(ans if ans >= 0 else 'Impossible')
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())

a=list(map(int,input().split()))

union=[-1]*n

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

cnt=-1
for i in range(n):
    if union[i]==-1:
        stack=[i]
        cnt+=1
        while len(stack)>0:
            tmp=stack.pop()
            union[tmp]=cnt
            for item in tree[tmp]:
                if union[item]==-1:
                    union[item]=cnt
                    stack.append(item)

if cnt==0:
    print(0)
    exit()

cost=[[] for _ in range(cnt+1)]
#print(union)
for i,aa in enumerate(a):
    cost[union[i]].append(aa)

import heapq

del_list=[]
kouho_list=[]

ans=0

#print(cost)
for i in range(cnt+1):
    tmp=min(cost[i])
    ans+=tmp
    del_list.append(tmp)
    kouho_list+=cost[i]
    #print(cost)


heapq.heapify(kouho_list)
heapq.heapify(del_list)

for _ in range(2*(n-m-1)-(cnt+1)):

    while 1:
        if len(kouho_list)>0:
            tmp=heapq.heappop(kouho_list)
        else:
            print("Impossible")
            exit()
        
        if len(del_list)>0:
            if del_list[0]!=tmp:
                break
            else:
                heapq.heappop(del_list)
    ans+=tmp

print(ans)