fork(1) download
copy 
  1. #include <iostream>
  2. #include <utility>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <numeric>
  6. #include <map>
  7. #include <unordered_set>
  8. #include <unordered_map>
  9. #include <queue>
  10. #include <set>
  11. #include <stack>
  12. #include <fstream>
  13. #include <ext/pb_ds/assoc_container.hpp>
  14. #include <ext/pb_ds/tree_policy.hpp>
  15. #include <bitset>
  16. #include <sstream>
  17.  
  18. using namespace std;
  19. using namespace __gnu_pbds;
  20.  
  21. /* clang-format off */
  22.  
  23. /* TYPES  */
  24. #define ll long long
  25. #define pii pair<int, int>
  26. #define pll pair<long long, long long>
  27. #define vi vector<int>
  28. #define vll vector<long long>
  29. #define vvi vector<vector<int>>
  30. #define vvll vector<vector<long long>>
  31. #define mii map<int, int>
  32. #define si set<int>
  33. #define sc set<char>
  34.  
  35. #define sz(x) (x).size()
  36.  
  37. /* FUNCTIONS */
  38. #define feach(el, v) for(auto &el: v)
  39. #define rep(i, n) for(int i=0;i<n;i++)
  40. #define reprv(i, n) for(int i=n-1;i>=0;i--)
  41. #define reps(i, s, e) for(int i=s;i<e;i++)
  42. #define reprve(i, e, s) for(int i=e;i>=s;i--)
  43.  
  44. #define pb push_back
  45. #define eb emplace_back
  46.  
  47. #define dec(zz) int (zz); cin >> zz;
  48. #define decv(zz, n) vector<int> zz(n); for(int i=0;i<n;++i) cin >> zz[i];
  49. #define decvn(zz, n) int n; cin >> n; vector<int> zz(n); for(int i=0;i<n;++i) cin >> zz[i];
  50.  
  51. typedef tree<int, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update> oSet;
  52.  
  53. const int MAXN = 200020;
  54. vector<int> parent(MAXN), rnk(MAXN);
  55.  
  56. void makeSets(int n) {
  57.     rep(i, n) {
  58.         parent[i] = i;
  59.         rnk[i] = 0;
  60.     }
  61. }
  62.  
  63. int findSet(int v) {
  64.     if (v == parent[v]) return v;
  65.     return parent[v] = findSet(parent[v]);
  66. }
  67.  
  68. void unionSets(int a, int b) {
  69.     a = findSet(a), b = findSet(b);
  70.     if (a != b) {
  71.         if (rnk[a] < rnk[b]) swap(a, b);
  72.         parent[b] = a;
  73.         if (rnk[a] == rnk[b]) ++rnk[a];
  74.     }
  75. }
  76.  
  77. int main() {
  78.     int n, q; cin >> n >> q;
  79.  
  80.     makeSets(n);
  81.  
  82.     map<ll, vector<int>> edges;
  83.     rep(i, q) {
  84.         ll compSz, cost; cin >> compSz >> cost;
  85.  
  86.         int vrt;
  87.         rep(j, compSz) {
  88.             cin >> vrt;
  89.             edges[cost].push_back(vrt - 1);
  90.         }
  91.     }
  92.  
  93.     ll totalCost = 0;
  94.     for (auto &[compCost, conComp]: edges) {
  95.         int first = conComp[0];
  96.         for (auto &vComp: conComp) {
  97.             if (findSet(first) != findSet(vComp)) {
  98.                 totalCost += compCost;
  99.                 unionSets(first, vComp);
  100.             }
  101.         }
  102.     }
  103.  
  104.     rep(i, n) {
  105.         if (findSet(i) != findSet(0)) {
  106.             cout << "-1";
  107.             return 0;
  108.         }
  109.     }
  110.     cout << totalCost;
  111.     return 0;
  112. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
4 2
2 1 2 5
2 3 4 5
stdout
copy 
-1
https://ideone.com/pnCDk1
language:
C++14 (gcc 8.3)
created:
204 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!