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: Accepted

Solution code:
n, m = map(int,input().split())
if n-m == 1:
    print(0)
    exit()
a = list(map(int,input().split()))
way = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    way[x].append(y)
    way[y].append(x)

#グラフをグループ化するやつ
import queue
def grouping(n,arr):
    gr = []
    al = [-1 for i in range(n)]
    q = queue.Queue()
    for i in range(n):
        if al[i] == 0:
            continue
        else:
            gi = []
            q.put(i)
            al[i] = 0
            while not q.empty():
                qi = q.get()
                gi.append(qi)
                for ai in arr[qi]:
                    if al[ai] < 0:
                        q.put(ai)
                        al[ai] = 0
            gr.append(gi)
    return gr

grp = grouping(n,way)
if len(grp)-2 > n-len(grp):
    print("Impossible")
    exit()
o2 = [0 for i in range(n-len(grp))]
o1 = [0 for i in range(len(grp))]
i1 = 0

for j,gi in enumerate(grp):
    m = 10**10
    f = True
    for i in gi:
        if m > a[i]:
            if f:
                f = False
            else:
                o2[i1] = m
                i1 += 1
            m = a[i]
        else:
            o2[i1] = a[i]
            i1 += 1
    o1[j] = m

o2.sort()
ans = sum(o1)
for i in range(len(o1)-2):
    ans += o2[i]
print(ans)

Submission status: Accepted

Solution code:
# APC001D
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from collections import defaultdict
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
ns = defaultdict(set)
for _ in range(m):
    u,v = map(int, input().split())
    ns[u].add(v)
    ns[v].add(u)

score = 0
count = 0
others = []
seen = [False] * n
for start in range(n):
    if seen[start]:
        continue
    count += 1
    q = [start]
    s = [a[start]]
    seen[start] = True
    while q:
        u = q.pop()
        for v in ns[u]:
            if not seen[v]:
                heapq.heappush(s, a[v])
                q.append(v)
                seen[v] = True
    score += heapq.heappop(s)
    for item in s:
        heapq.heappush(others, item)

if n<2*(count-1):
    print("Impossible")
elif count==1:
    print(0)
else:
    for _ in range(2*(count-1)-count):
        score += heapq.heappop(others)
    else:
        print(score)

Submission status: Accepted

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

import sys,heapq

input=sys.stdin.readline

N,M=map(int,input().split())
a=list(map(int,input().split()))
uf=UnionFindVerSize(N)
for i in range(M):
    x,y=map(int,input().split())
    uf.unite(x,y)

dic={}
for i in range(0,N):
    if uf.find_root(i) not in dic:
        dic[uf.find_root(i)]=[]
        heapq.heapify(dic[uf.find_root(i)])
    heapq.heappush(dic[uf.find_root(i)],a[i])

m=len(dic)
if m==1:
    print(0)
    exit()
ans=0
for i in dic:
    ans+=heapq.heappop(dic[i])

data=[]
for i in dic:
    data+=dic[i]
data.sort()
if len(data)<m-2:
    print("Impossible")
else:
    print(ans+sum(data[:m-2]))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
XY=[list(map(int,input().split())) for i in range(M)]
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
u=UnionFind(N)
for x,y in XY:
    u.unite(x,y)
if u.size(0)==N:
    print(0);exit()
d={}
x=[]
for i,a in enumerate(A):
    r=u.root(i)
    if r not in d:
        d[r]=a
    elif a<d[r]:
        x.append(d[r])
        d[r]=a
    else:
        x.append(a)
rem=2*(N-1-M)-len(d)
print(sum([v for v in d.values()])+sum(sorted(x)[:rem]) if len(x)>=rem else "Impossible")

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
  def same(self, x, y):
    return self.find(x)==self.find(y)
  
N,M,*L = map(int, open(0).read().split())
A = L[:N]
U = UnionFind(N)
dic = defaultdict(list)
used = [False]*N
ans = 0
for x,y in zip(*[iter(L[N:])]*2):
  U.unit(x,y)
for i in range(N):
  dic[U.find(i)].append((A[i],i))
if len(dic.keys())==1:
  print(0)
  sys.exit()
for k in dic.keys():
  dic[k].sort()
  ans += dic[k][0][0]
  used[dic[k][0][1]] = True
B = sorted((c,i) for i,c in enumerate(A))
cnt = len(dic.keys())-2
for i in range(N):
  if cnt==0:
    break
  if used[B[i][1]]:
    continue
  ans += B[i][0]
  cnt -= 1
if cnt > 0:
  print('Impossible')
else:
  print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
n,m = map(int,input().split())
a = list(map(int,input().split()))
# edg = [[] for i in range(n)]
rank = [1] * n
par = [i for i in range(n)]
def root(x):
  if x == par[x]:
    return x
  par[x] = root(par[x])
  return par[x]
def union(a,b):
  a = root(a)
  b = root(b)
  if rank[a] < rank[b]:a,b = b,a
  if a == b: return False
  par[b] = a
  rank[a] += rank[b]
  return True
for _ in range(m):
  x,y = map(int, input().split())
  union(x,y)
d = defaultdict(list)
q = []
for i in range(n):
  ai = a[i]
  heappush(q,(ai,i))
  ri = root(i)
  heappush(d[ri],(ai,i))
if len(d.keys()) == 1:
  print(0)
else:
  ans = 0
  tmp = 0
  c = [0] * n

  for i in d.keys():
    tmp += 1
    t,p = heappop(d[i])
    c[p] = 1
    ans += t
  if 2*tmp-2 > n:
    print("Impossible")
  else:
    for _ in range(tmp-2):
      p,i = heappop(q)
      while c[i]:
        p,i = heappop(q)
      ans += p
    print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n=1):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.parent[y] = x
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, input().split())
A = list(map(int, input().split()))
uf = UnionFind(N)
for i in range(M):
  x, y = map(int, input().split())
  uf.union(x, y)

for i in range(N):
  uf.find(i)

par = [uf.find(i) for i in range(N)]
d = {}
for i, p in enumerate(par):
  if p in d:
    d[p].append(A[i])
  else:
    d[p] = [A[i]]

num = len(d)
if num == 1:
  print(0)
  quit()

a = []
ans = 0
for p in d:
  d[p].sort(reverse=True)
  ans += d[p].pop()
  a += d[p]

a.sort()
n = 2*(N - M - 1) - num
if len(a) < n:
  print('Impossible')
else:
  print(sum(a[:n]) + ans)

Submission status: Accepted

Solution code:
from collections import deque
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
G = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
F = []
hist = [0 for _ in range(N)]
for i in range(N):
    T = []
    if hist[i]==0:
        que = deque([i])
        hist[i]=1
        heapq.heappush(T,A[i])
        while que:
            x = que.popleft()
            for y in G[x]:
                if hist[y]==0:
                    que.append(y)
                    hist[y]=1
                    heapq.heappush(T,A[y])
        F.append(T)
K = len(F)
if K>N//2+1:        
    cnt = -1
elif K==1:
    cnt = 0
else:
    cnt = 0
    for i in range(K):
        cnt += heapq.heappop(F[i])
    F1 = []
    for T in F:
        F1 += T
    F1 = sorted(F1)
    for i in range(K-2):
        cnt += F1[i]
if cnt<0:
    print("Impossible")
else:
    print(cnt)

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)

from collections import defaultdict
N,M,*L = map(int, open(0).read().split())
A = L[:N]
U = UnionFind(N)
for x,y in zip(*[iter(L[N:])]*2):
  U.unit(x,y)
ans = 0
rest = []
dic = defaultdict(list)
for i in range(N):
  dic[U.find(i)].append(A[i])
for k in dic.keys():
  dic[k].sort()
  ans += dic[k][0]
  rest.extend(dic[k][1:])
if N-1==M:
  print(0)
  exit()
if N<2*(N-M-1):
  print('Impossible')
  exit()

rest.sort()
remain = 2*(N-M-1)-len(dic.keys())
ans += sum(rest[:remain])
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
import heapq

def main():
    N,M = map(int,input().split())
    a = list(map(int,input().split()))
    d = defaultdict(list)
        
    I = [i for i in range(N)]
    rank = [1 for _ in range(N)]
    def root(a):
        if I[a] == a:
            return a
        else:
            I[a] = root(I[a])
            return I[a]
            
    def unite(a,b):
        pa,pb = root(a),root(b)
        ra,rb = rank[a],rank[b]
        if ra > rb:
            I[pb] = pa
        else:
            I[pa] = pb
            if ra == rb:
                rank[pb] += 1
    
    for _ in range(M):
        x,y = map(int,input().split())
        unite(x,y)
        parent = root(x)
    
    for i,num in enumerate(I):
        parent = root(num)
        heapq.heappush(d[parent],a[i])
        
    if M == N-1:
        print(0)
        exit()
    elif N < 2*(N-M-1):
        print("Impossible")
        exit()

    l = len(d.keys())
    ans = 0
    rest = []
    for use in d.values():
        ans += heapq.heappop(use)
        rest.extend(use)

    remain = 2*(N-M-1)-l
    rest.sort()
    ans += sum(rest[:remain])
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import *

class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        self.p = [-1] * n
        self.rank = [1]*n
    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[y] += 1
            self.p[x] = y
            return True
        else:
            return False

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

n,m = map(int,input().split())
a = list(map(int,input().split()))
uf = UnionFind(n)
ans = 0
for i in range(m):
    x,y = map(int,input().split())
    uf.unite(x, y)
if n < 2*(n-m-1):
    print('Impossible')
    exit(0)
if m == n-1:
    print(0)
    exit(0)
tree = {}
pq = []
heapify(pq)
for i in range(n):
    p = uf.find(i)
    if not p in tree.keys():
        ans += a[i]
        tree[p] = a[i]
    else:
        if tree[p] <= a[i]:
            heappush(pq, a[i])
        else:
            ans += a[i] - tree[p]
            heappush(pq, tree[p])
            tree[p] = a[i]
l = len(tree)

for _ in range(2*(n-m-1) - l):
    ans += heappop(pq)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# 各森の最小値を使う
# 後は全体から最小値を順に取ってくればよい

class UF(object):
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.size = [1]*n

    # x が属する集合の代表値を返す
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # x と y の集合を結合する
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

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

    # x が属する集合の要素数を返す
    def get_size(self,x):
        x = self.find(x)
        return self.size[x]

N,M = LI()
a = LI()
x,y = LIR(M,2)

uf = UF(N)
for i in range(M):
    uf.union(x[i],y[i])

d = defaultdict(list)
for i in range(N):
    d[uf.find(i)].append(a[i])

for g in d.values():
    g.sort(reverse=True)

if 2*(len(d)-1) > N:
    print('Impossible')
else:
    if len(d) == 1:
        print(0)
        exit()
    ans = 0
    num = 0
    for gr in d.values():
        ans += gr.pop()
        num += 1
    left = []
    for gr in d.values():
        left.extend(gr)
    left.sort()
    for i in range(2*(len(d)-1)-num):
        ans += left[i]
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
A = list(map(int,input().split()))
C = [list(map(int,input().split())) for i in range(m)]

V = [0] * (n)
# P = [-1] * (n+1)

M = [[] for i in range(n)]
for i in range(m):
    M[C[i][0]].append(C[i][1])
    M[C[i][1]].append(C[i][0])

# 1始まりの場合
BB = []
one = 0
for ii in range(n):
    B = []
    if V[ii] == 0:
        Q = [ii]
        s = 0
        V[ii] = 1
        onef = 1
        B.append([ii,A[ii]])
        while s < len(Q):
            i = Q[s]
            for x in M[i]:
                if V[x] == 0:
                    V[x] = 1
                    onef = 0
                    B.append([x,A[x]])
                    # P[x] = i
                    Q.append(x)
            s += 1
        if onef == 1:
            one += 1
        B.sort(key=lambda x:x[1])
        BB.append(B[0])

if len(BB) == 1:
    print(0)
elif (len(BB)-1)*2 > n:
    print("Impossible")
else:
    ans = sum([i[1] for i in BB])
    # print(ans)
    anoBind = [0] * n
    anoB = []
    for i in range(len(BB)):
        anoBind[BB[i][0]] = 1
    for i in range(n):
        if anoBind[i] == 0:
            anoB.append(A[i])
    anoB.sort()
    # print(anoB)
    ans += sum(anoB[:len(BB)-2])
    print(ans)

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

# # # # unionfind.py # # # #

# usage: uf = Unionfind(n) ; x = uf.root(y); uf.conn(a,b)

class Unionfind:

  def __init__(s,n):
    s.sz = [1] * n
    s.ances = [i for i in range(n)]

  def root(s,x):
    a = []
    y = x
    while s.ances[y] != y:
      a.append(y)
      y = s.ances[y]
    for z in a:
      s.ances[z] = y
    return y

  def conn(s,x,y):
    i = s.root(x)
    j = s.root(y)
    if i==j:
      return
    #k  = [i,j].min
    k  = j if (s.sz[i]<s.sz[j]) else i
    if k==j:
      s.ances[i] = j
    else:
      s.ances[j] = i
    s.sz[k] = s.sz[i] + s.sz[j]

# # # # end unionfind.py # # # #

n,m = inm()
a = inl()
nouse = 2*m-n+2
if n-m==1:
    print('0')
    exit()
if nouse<0:
    print('Impossible')
    exit()
uf = Unionfind(n)
for i in range(m):
    x,y = inm()
    uf.conn(x,y)
g = {}
for i in range(n):
    r = uf.root(i)
    if r not in g:
        g[r] = []
    g[r].append((a[i],i))

import heapq
h = []
for r in g:
    if len(g[r])<=1:
        continue
    g[r].sort()
    x,i = g[r].pop()
    heapq.heappush(h,(-x,r))
sm = 0
for i in range(nouse):
    xm,r = heapq.heappop(h)
    sm -= xm
    if len(g[r])>1:
        y,j = g[r].pop()
        heapq.heappush(h,(-y,r))
print(sum(a)-sm)

Submission status: Accepted

Solution code:
n,m,*L=map(int,open(0).read().split())
a=L[:n];b=L[n:]
if n//2+m<n-1:
	print('Impossible')
	exit()
if n-1==m:
	print(0)
	exit()
con=[[] for _ in range(n)]
vis=[0]*n
for x,y in zip(*[iter(b)]*2):
	con[x].append(y)
	con[y].append(x)
least=[]
rest=[]
cnt=0
for i in range(n):
	if not vis[i]:
		cnt+=1
		q=[i]
		es=[a[i]]
		vis[i]=1
		while q:
			cur=q.pop()
			for nxt in con[cur]:
				if not vis[nxt]:
					q.append(nxt)
					es.append(a[nxt])
					vis[nxt]=1
		mi=min(es)
		es.remove(mi)
		least.append(mi)
		rest+=es
# print(least,rest)
print(sum(least+sorted(rest)[:2*(n-1-m)-cnt]))

Submission status: Accepted

Solution code:
import sys
from collections import deque, defaultdict
import heapq

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = lr()

# Aでxの根を求める
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

# Aでxとyの属する集合の併合
def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    # 根をbxに統一
    A[by] = bx

edges = [[] for _ in range(N)]
V = [i for i in range(N)]
for _ in range(M):
    x, y = lr()
    if find(V, x) != find(V, y):
        union(V, x, y)
    edges[x].append(y)
    edges[y].append(x)

for i in range(N):
    V[i] = find(V, i)

if M == N - 1:
    print(0); exit()
elif N < 2 * (N-M-1):
    print('Impossible'); exit()

root_point = defaultdict(list)
for i in range(N):
    r = V[i]
    heapq.heappush(root_point[r], A[i])

#各グループの最小値以外で使うコストの数
answer = 0
candidates = []
for p_list in root_point:
    answer += heapq.heappop(root_point[p_list])
    candidates.extend(root_point[p_list])

remain = 2 * (N-M-1) - len(set(V))
candidates.sort()
answer += sum(candidates[:remain])
print(answer)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)  # -1ならそのノードが根,で絶対値が木の要素数
        self.rank = [0] * (n + 1)

    def find(self, x):  # xの根となる要素番号を返す
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def getNodeLen(self, x):
        return -self.root[self.find(x)]


if __name__ == "__main__":
    N, M = map(int, input().split())

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

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

    d = defaultdict(list)
    for i in range(N):
        heapq.heappush(d[uf.find(i)], A[i])

    if M == N - 1:
        print(0)
        exit()
    elif N < 2 * (N - M - 1):
        print("Impossible")
        exit()

    nodes = 2 * (N - M - 1)
    ans = 0
    tmp = []
    for k, v in d.items():
        ans += heapq.heappop(v)
        tmp.extend(v)
        nodes -= 1

    tmp.sort()
    ans += sum(tmp[:nodes])
    print(ans)

Submission status: Accepted

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():
    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)
    totalForest = 0
    minCost = 0
    minF = dict()
    for i in range(N):
        a = parent.find(i)
        if a in minF: heappush(minF[a], A[i])
        else: 
            minF[a] = []
            heapify(minF[a])
            heappush(minF[a], A[i])
            totalForest += 1

    f = []
    heapify(f)
    sonNode = []
    heapify(sonNode) 
    if totalForest > 1:
        for key in minF: 
            minCost += heappop(minF[key])
            while minF[key]: heappush(sonNode, heappop(minF[key]))
   
    for _ in range(max(totalForest - 2, 0)):
        if not sonNode: 
            print("Impossible")
            break
        minCost += heappop(sonNode)
    else: print(minCost)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
 
class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        p = x
        
        while not self.par[p]<0:
            p = self.par[p]
        
        while x!=p:
            tmp = x
            x = self.par[x]
            self.par[tmp] = p
        
        return p
    
    def unite(self, x, y):
        rx, ry = self.root(x), self.root(y)
        
        if rx==ry: return False
        
        if self.rank[rx]<self.rank[ry]:
            rx, ry = ry, rx
        
        self.par[rx] += self.par[ry]
        self.par[ry] = rx
    
        if self.rank[rx]==self.rank[ry]:
            self.rank[rx] += 1
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

N, M = map(int, input().split())
a = list(map(int, input().split()))
uf = Unionfind(N)

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

d = defaultdict(list)

for i in range(N):
    d[uf.root(i)].append(a[i])

keys = list(d.keys())

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

if N<2*(len(keys)-1):
    print('Impossible')
    exit()
    
for k in keys:
    d[k].sort()

ans = 0
l = []

for k in keys:
    ans += d[k][0]
    l += d[k][1:]

l.sort()
ans += sum(l[:len(keys)-2])

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
XY = [tuple(map(int,input().split())) for i in range(M)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf = UnionFind(N)
for x,y in XY:
    if uf.is_same(x,y): continue
    uf.unite(x,y)
for i in range(N):
    uf.root(i)

c = N - uf.count
if c==1:
    print(0)
    exit()
ex = c-2
if c+ex > N:
    print('Impossible')
    exit()

from collections import defaultdict
d = defaultdict(lambda: [])
for i,a in enumerate(A):
    r = uf.root(i)
    d[r].append(a)

ans = 0
hq = []
for k in d.keys():
    s = sorted(d[k])
    ans += s[0]
    for v in s[1:]:
        hq.append(v)

import heapq
heapq.heapify(hq)
for _ in range(ex):
    v = heapq.heappop(hq)
    ans += v
print(ans)

Submission status: Accepted

Solution code:
import collections
import heapq
N, M = map(int, input().split())
a = list(map(int, input().split()))


class unionFind:
    parent = []
    count = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.count = [1 for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.count[y] += self.count[x]
            self.count[x] = self.count[y]
            return

    def getCount(self, x):
        self.count[x] = self.count[self.root(x)]
        return(self.count[x])


G = unionFind(N)
for i in range(M):
    x, y = map(int, input().split())
    G.unite(x+1, y+1)
A = [(a[i], i) for i in range(N)]


A.sort(key=lambda x: (-G.getCount(x[1]), G.parent[x[1]], x[0]))
a1 = 0
x = 0
ans = 0
t = []
for a, x in A:
    x = G.root(x)
    if len(t) > 0:
        if G.root(t[0][1]) == x:
            heapq.heappush(t, (a, x))
        else:
            a1, y = heapq.heappop(t)
            y = G.root(y)
            ans += (a + a1)
            G.unite(x+1, y+1)
    else:
        heapq.heappush(t, (a, x))

s = set()
for i in range(N):
    s.add(G.root(i))
if len(s) == 1:
    print(ans)
else:
    print("Impossible")
    # print(ans)
    # print(s)