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
Task D - Forest
User TAB
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1345 Byte
Status
Exec Time 108 ms
Memory 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