fork(1) download
  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
stdin
4 2
2 1 2 5
2 3 4 5
stdout
-1