fork(1) download
copy 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <string>
  9. #include <queue>
  10. #include <stack>
  11. #include <algorithm>
  12. #define dibs reserve
  13. #define OVER9000 1234567890
  14. #define tisic 47
  15. #define soclose 10e-7
  16. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  17. #define chocolate win
  18. #define ff first
  19. #define ss second
  20. #define uint unsigned int
  21. // mylittlepony
  22. using namespace std;
  23.  
  24. int main() {
  25.     int T,N,M,C;
  26.     cin >> T;
  27.     for(int t =0; t < T; t++) {
  28.     	cin >> N >> M >> C;
  29.     	vector< vector<int> > comp(N);
  30.     	vector<int> isC(N);
  31.     	for(int i =0; i < N; i++) {
  32.     		isC[i] =i;
  33.     		comp[i].push_back(i);}
  34.     	vector< pair<int, pair<int,int> > > E(M);
  35.     	for(int i =0; i < M; i++) cin >> E[i].ss.ff >> E[i].ss.ss >> E[i].ff;
  36.     	sort(E.begin(),E.end());
  37.     	vector<int> F;
  38.     	int comps =N;
  39.     	for(int i =M-1; i >= 0; i--) {
  40.     		int x =isC[--E[i].ss.ff], y =isC[--E[i].ss.ss];
  41.     		if(comp[x].size() > comp[y].size()) swap(x,y);
  42.     		if(x == y) {F.push_back(E[i].ff); continue;}
  43.     		comps--;
  44.     		ALL_THE(comp[x],it) {
  45.     			isC[*it] =y;
  46.     			comp[y].push_back(*it);}
  47.     		}
  48.  
  49.     	sort(F.begin(),F.end());
  50.     	while(!F.empty() && *F.rbegin() > C) F.pop_back();
  51.     	int cost =0, aut =0;
  52.     	for(int i =0; i < comps-1; i++) {
  53.     		if(i < F.size()) cost +=F[i];
  54.     		else {aut++; cost +=C;}}
  55.     	cout << aut << " " << comps-1-aut << " " << cost << "\n";}
  56.     return 0;}
  57.  
  58. // look at my code
  59. // my code is amazing
Success #stdin #stdout 0s 3484KB
comments (?)
stdin
copy 
1
6 6 1
1 2 1
2 3 2
1 3 2
4 5 2
5 6 2
4 6 2
stdout
copy 
0 1 1
https://ideone.com/83cQDl
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

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!