fork(4) 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. #include <iomanip>
  13. #define dibs reserve
  14. #define OVER9000 1234567890
  15. #define patkan 9
  16. #define tisic 47
  17. #define soclose 10e-7
  18. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  19. #define chocolate win
  20. #define ff first
  21. #define ss second
  22. #define abs(x) ((x < 0)?-(x):(x))
  23. // mylittlepony
  24. using namespace std;
  25.  
  26. struct infoE {
  27. 	int a,b,c;
  28.  
  29. 	bool operator<(const infoE &A) const {
  30. 		return c < A.c;}
  31. 	};
  32.  
  33. int main() {
  34. 	// freopen("road.in","r",stdin);
  35. 	int T;
  36. 	scanf(" %d",&T);
  37.  
  38.     for(int t =0; t < T; t++) {
  39.     	int N,M;
  40.     	scanf(" %d %d",&N,&M);
  41.     	vector<infoE> E(M);
  42.     	for(int i =0; i < M; i++) {
  43.     		scanf(" %d %d %d",&E[i].a,&E[i].b,&E[i].c);
  44.     		E[i].a--, E[i].b--;}
  45.     	sort(E.begin(),E.end());
  46.  
  47.     	vector< vector<int> > comp(N);
  48.     	vector<int> isC(N);
  49.     	for(int i =0; i < N; i++) {
  50.     		comp[i].push_back(i);
  51.     		isC[i] =i;}
  52. 		vector< vector< pair<int,int> > > upd(N);
  53. 		vector<int> ans(N,0);
  54.  
  55. 		for(int i =0; i < M; i++) {
  56. 			int x =isC[E[i].a], y =isC[E[i].b];
  57. 			if(x == y) continue;
  58. 			if(comp[x].size() < comp[y].size()) swap(x,y);
  59.  
  60. 			int S =0, a =upd[y].size()-1;
  61. 			for(int j =comp[y].size(); j >= 0; j--) {
  62. 				while(a >= 0 && upd[y][a].ff >= j) {
  63. 					S +=upd[y][a].ss;
  64. 					a--;}
  65. 				ans[comp[y][j]] +=S;}
  66.  
  67. 			upd[x].push_back(make_pair(comp[x].size()-1,comp[y].size()*E[i].c));
  68. 			int K =comp[x].size();
  69. 			for(int j =0; j < comp[y].size(); j++) {
  70. 				ans[comp[y][j]] +=K*E[i].c;
  71. 				comp[x].push_back(comp[y][j]);
  72. 				isC[comp[y][j]] =x;}
  73. 			}
  74. 		int S =0, a =upd[isC[0]].size()-1;
  75. 		for(int j =comp[isC[0]].size(); j >= 0; j--) {
  76. 			while(a >= 0 && upd[isC[0]][a].ff >= j) {
  77. 				S +=upd[isC[0]][a].ss;
  78. 				a--;}
  79. 			ans[comp[isC[0]][j]] +=S;}
  80.  
  81. 		printf("Case %d:\n",t+1);
  82. 		for(int i =0; i < N; i++) printf("%d\n",ans[i]);}
  83.     return 0;}
  84.  
  85. // look at my code
  86. // my code is amazing
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
2
5 7
1 2 2
1 4 5
2 3 14
2 4 5
2 5 4
3 5 34
4 5 58
7 11
1 2 40
1 3 8
1 4 11
2 3 29
2 6 17
3 4 3
3 6 31
4 5 46
5 6 40
5 7 15
6 7 53
stdout
copy 
Case 1:
25
25
56
29
27
Case 2:
154
184
149
149
215
184
215
https://ideone.com/hH0R8K
cf s01e10
language:
C++14 (gcc 8.3)
created:
11 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!