Submission #53129885

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long int

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << " "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

template<class T> void _print(T &a){cerr << a;}
template<class T> void _print(vector<T> &a){cerr << "[ ";for(T i:a) cerr << i << " ";cerr << "]";}
template<class T> void _print(set<T> &a){cerr << "[ ";for(T i:a) cerr << i << " ";cerr << "]";}
template<class T,class V> void _print(map<T,V> &m){cerr << "[ ";for(auto &it:m) cerr << it.first << "--> " << it.second << ", ";cerr << "]";}
template<class T> void _print(multiset<T> &a){cerr << "[ ";for(T i:a) cerr << i << " ";cerr << "]";}
template<class T> void _print(vector<vector<T>> &fin){cerr << endl; for(auto i:fin){for(auto p:i) cerr << p << " "; cerr << endl;}}

class DSU{
	public:
		vector<int> parent, rank;
		DSU(int n){
			parent.resize(n+1);
			rank.resize(n+1,0);
			for(int i=0;i<=n;i++) parent[i] = i;
		}
		int findParent(int node){
			if(parent[node] == node) return node;
			return parent[node] = findParent(parent[node]);
		}
		bool unionByRank(int u,int v){
			int pu = findParent(u);
			int pv = findParent(v);
			if(pu == pv) return false;
			else if(rank[pu] > rank[pv]) parent[pv] = pu;
			else if(rank[pv] > rank[pu]) parent[pu] = pv;
			else{
				++rank[pu];
				parent[pv] = pu;
			}
			return true;
		}
};

void solve(){
	int n, m; cin >> n >> m;
	map<int,vector<int>> mp;
	while(m--){
		int k, c; cin >> k >> c;
		for(int i=0;i<k;i++){
			int x; cin >> x;
			mp[c].push_back(x);
		}
	}
	// select n nodes and n-1 edges.
	int ans = 0;
	DSU ds(n);
	for(auto &it:mp){
		for(int i=1;i<(int)it.second.size();i++){
			if(ds.unionByRank(it.second[0],it.second[i])) ans += it.first;
		}
	}
	int comp = 0;
	for(int i=1;i<=n;i++){
		if(ds.findParent(i) == i) ++comp;
	}
	if(comp != 1) cout << -1;
	else cout << ans;
}

signed main(){
	ios::sync_with_stdio(false);
  	cin.tie(0);
	#ifndef ONLINE_JUDGE
	freopen("error.txt","w",stderr);
	#endif
	
	int t = 1;
	while(t--)
		solve();
	return 0;
}

Submission Info

Judge Result