fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ; 
  3.  
  4.  
  5. #define ll long long 
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define fir first 
  8. #define sec second 
  9. #define piint pair < int , int >
  10. #define FOR( i , a , b ) for (int i = (a) , _b = (b) ; i <= _b ; i ++ )  
  11. #define pb push_back 
  12. #define str string 
  13. #define ALL(a) (a).begin() , (a).end() 
  14. #define rep( i , a , b) for (int i = (a) ; i < (b) ; i ++ )
  15. #define ld long double
  16. const int maxn = 4 * 1e5 ;
  17. #define debug 0
  18. #define oo (ll)(1e18)
  19.  
  20. // #define l9 18
  21.  
  22.  
  23.  
  24. void input(){
  25. }
  26.  
  27. ll f[maxn + 3] ;
  28. int n , m ;
  29.  
  30. ll find_root ( int u ) {
  31. 	return ( f[u] < 0  ) ? u : f[u] = find_root ( f[u] ) ;
  32. }
  33.  
  34. bool unit ( int x , int y ){
  35.  
  36.  
  37. 	x = find_root ( x ) ;
  38. 	y = find_root ( y ) ;
  39.  
  40. 	if ( x == y) return 0; 
  41. 	if ( f[x] > f[y]) swap ( x , y ) ;
  42. 	f[x ] += f[y] ;
  43. 	f[y ] = x ;
  44. 	return 1 ;
  45. }	
  46. struct ALMST{
  47. 	int u , v ;
  48. 	ll w ;
  49. 	int i ;
  50. 	bool in ;
  51.  
  52. } ;
  53. int up[maxn+3][20]; 
  54. ll maxx[maxn+3][20]; 
  55. vector < pair < int , ll >  > a[maxn+3];
  56. ll h[maxn+3] ;
  57. void dfs ( int u , int p ) {
  58.  
  59. 	FOR ( i , 1 , 19 ) {
  60. 		up[u][i] = up[up[u][i-1]][i-1] ;
  61. 		maxx[u][i] = max ( maxx[u][i-1] , maxx[up[u][i-1]][i-1] ) ;
  62. 	}
  63. 	for (auto [v  , w ] : a[u]){
  64. 		if ( v == p ) continue ;
  65. 		up[v][0] = u;
  66. 		maxx[v][0] = w ;
  67. 		h[v] = h[u] + 1;
  68. 		dfs ( v , u ) ;
  69.  
  70. 	}
  71. }
  72. ll get_max ( int u , int v ) {
  73. 	if ( h[u] < h[v]) swap ( u , v );
  74. 	int k = h[u] - h[v] ;
  75. 	ll res = -oo ;
  76. 	for (int j = 0 ; ( 1 << j ) <= k ; j ++ ) {
  77. 		if ( ( k >> j ) & 1 ) {
  78. 			res = max ( res , maxx[u][j] ) ;
  79. 			u = up[u][j] ;
  80. 		}
  81. 	}
  82.  
  83. 	if ( u == v ) return res ;
  84.  
  85. 	for (int i = 19 ; i>= 0 ; i -- ) {
  86. 		if ( up[u][i] != up[v][i]) {
  87. 			res = max ( { res , maxx[v][i] , maxx[u][i]} ) ;
  88. 			u = up[u][i] ;
  89. 			v = up[v][i] ;
  90. 		}
  91. 	}
  92. 	return max ( { res , maxx[u][0] , maxx[v][0]}) ;
  93. }
  94. vector < ALMST > edges ; 
  95. #define name "TASK" 
  96. int main(){
  97.     fast 
  98.     if(fopen(name".INP","r")) {
  99.         freopen (name".INP","r",stdin);
  100.         freopen (name".OUT","w",stdout);
  101.     }
  102.    	cin >> n >> m ;
  103.    	memset ( f , -1 , sizeof (f)) ;
  104.  
  105.    	FOR ( i , 1 , m ) {
  106.    		int u , v ;
  107.    		ll w ;
  108.  
  109.    		cin >> u >> v >> w ;
  110.    		edges.pb ( { u , v , w , i  , false }) ;
  111.  
  112.     }
  113.     sort ( ALL(edges) , [&] ( ALMST a , ALMST b ) {
  114.     	return a.w < b.w ;
  115.     }) ;
  116.     ll MINNEST = 0 ;
  117.     vector < ll > ans ( m + 1 , 0ll ); 
  118.     for (auto& e: edges ){
  119.     	if(unit ( e.u , e.v )) {
  120.  
  121.     		MINNEST += e.w ;
  122.     		e.in = 1 ;
  123.     		a[e.u].pb ( { e.v , e.w }) ;
  124.     		a[e.v].pb ( { e.u , e.w }) ;
  125.  
  126.     	}
  127.     }
  128.     maxx[1][0] = -oo;
  129.     dfs ( 1 , 0 ) ;
  130.     for (auto& e : edges){
  131.     	if(e.in){
  132.         ans[e.i] = MINNEST ;
  133.     } else {
  134.         ans[e.i] = e.w + MINNEST - get_max(e.u, e.v) ;
  135.     }
  136. }
  137.     FOR ( i , 1 , m ) cout << ans[i] << '\n';
  138.     cerr << "\nTIME: = " << (1.0*clock())/CLOCKS_PER_SEC << '\n';
  139.     return(0) ;
  140. }
Success #stdin #stdout #stderr 0.01s 19512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
TIME: = 0.009136
https://ideone.com/jd5JDN
language:
C++14 (gcc 8.3)
created:
6 days 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!