Submission #2054772

Source Code Expand

Copy
```#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
using namespace std;

struct UnionFind{
vector<int> data;
UnionFind(int n) : data(n, -1) {}
bool unite(int x, int y){
x = find(x);
y = find(y);
if(x != y){
if(data[y] < data[x]) swap(x,y);
data[x] += data[y];//高さを更新
data[y] = x;//親を更新
}
return x != y;
}
bool same(int x, int y){ return find(x) == find(y); }
int find(int x){
if(data[x] < 0) return x;
return data[x] = find(data[x]);
}
};

int main(){
int N, M;
cin >> N >> M;
vector< pair<int,int> > A;
int a;
for(int i = 0; i < N; ++i){
cin >> a;
A.emplace_back(a,i);
}
UnionFind uf(N);
int x, y;
for(int i = 0; i < M; ++i){
cin >> x >> y;
uf.unite(x,y);
}
map< int,vector<int> > mp;
set<int> s;
for(int i = 0; i < N; ++i) s.insert(uf.find(i));
int k = s.size(), e = 2*(k-1);
vector<int> C(N,0);
sort(A.begin(),A.end());
long long int ans = 0;
for(int i = 0; i < N; ++i){
if(e == 0) break;
a = A[i].first;
int v = A[i].second;
if(C[uf.find(v)] < k-1){
--e;
ans += a;
++C[uf.find(v)];
}
}
if(e > 0) cout << "impossible" << endl;
else cout << ans << endl;
return 0;
}
```

#### Submission Info

Submission Time 2018-02-03 23:58:55+0900 D - Forest TAB C++14 (GCC 5.4.1) 0 1345 Byte WA 108 ms 6516 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 0_000.txt, 0_001.txt, 0_002.txt
All 0 / 600 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt, 1_048.txt, 1_049.txt, 1_050.txt, 1_051.txt
Case Name Status Exec Time Memory
0_000.txt 1 ms 256 KB
0_001.txt 1 ms 256 KB
0_002.txt 1 ms 256 KB
1_003.txt 1 ms 256 KB
1_004.txt 72 ms 6388 KB
1_005.txt 66 ms 6388 KB
1_006.txt 63 ms 6388 KB
1_007.txt 62 ms 6388 KB
1_008.txt 71 ms 6004 KB
1_009.txt 95 ms 4084 KB
1_010.txt 99 ms 3316 KB
1_011.txt 100 ms 2932 KB
1_012.txt 107 ms 1780 KB
1_013.txt 105 ms 1780 KB
1_014.txt 105 ms 1780 KB
1_015.txt 73 ms 6516 KB
1_016.txt 67 ms 6516 KB
1_017.txt 63 ms 6516 KB
1_018.txt 63 ms 6516 KB
1_019.txt 72 ms 6004 KB
1_020.txt 96 ms 4212 KB
1_021.txt 99 ms 3316 KB
1_022.txt 101 ms 2932 KB
1_023.txt 108 ms 1780 KB
1_024.txt 106 ms 1780 KB
1_025.txt 106 ms 1780 KB
1_026.txt 22 ms 3320 KB
1_027.txt 21 ms 3320 KB
1_028.txt 20 ms 3320 KB
1_029.txt 20 ms 3192 KB
1_030.txt 24 ms 3064 KB
1_031.txt 35 ms 2168 KB
1_032.txt 36 ms 1784 KB
1_033.txt 37 ms 1528 KB
1_034.txt 41 ms 1016 KB
1_035.txt 41 ms 1016 KB
1_036.txt 40 ms 1016 KB
1_037.txt 51 ms 6516 KB
1_038.txt 46 ms 6516 KB
1_039.txt 42 ms 6516 KB
1_040.txt 41 ms 6388 KB
1_041.txt 49 ms 6004 KB
1_042.txt 74 ms 4212 KB
1_043.txt 76 ms 3316 KB
1_044.txt 78 ms 2932 KB
1_045.txt 85 ms 1780 KB
1_046.txt 85 ms 1780 KB
1_047.txt 84 ms 1780 KB
1_048.txt 100 ms 4212 KB
1_049.txt 96 ms 4212 KB
1_050.txt 98 ms 4212 KB
1_051.txt 96 ms 4212 KB