fork(1) download
copy 
  1. /*input
  2. 4 3 
  3. 1 2 10 
  4. 2 3 2 
  5. 3 4 5 
  6. */
  7. #include <bits/stdc++.h>
  8. #include<stdio.h>
  9. using namespace std;
  10. #define pii pair<long long,long long>
  11. #define F(i,a,b) for(ll i = (ll)(a); i <= (ll)(b); i++)
  12. #define RF(i,a,b) for(ll i = (ll)(a); i >= (ll)(b); i--)
  13. #define PI 3.14159265
  14. #define ll long long
  15. #define ff first
  16. #define ss second
  17. #define pb(x) push_back(x)
  18. #define mp(x,y) make_pair(x,y)
  19. #define INF 1000000009
  20. #define mod 1000000000
  21. ll id[200005];
  22. ll size[200005];
  23. vector <pii> g[200005];
  24. void initialise()
  25. {
  26. 	F(i,1,200000)
  27. 	{
  28. 		id[i]=i;
  29. 		size[i] = 1;
  30. 	}
  31. }
  32. ll root(ll x)
  33. {
  34. 	while(id[x]!=x)
  35. 	{
  36. 		id[x] = id[id[x]];
  37. 		x = id[x];
  38. 	}
  39. 	return x;
  40. }
  41. void Union(ll a,ll b)
  42. {
  43. 	ll p = root(a);
  44. 	ll q = root(b);
  45. 	if(size[p]<size[q])
  46. 	{
  47. 		id[p] = id[q];
  48. 		size[q] += size[p];
  49. 	}
  50. 	else
  51. 	{
  52. 		id[q] = id[p];
  53. 		size[p] += size[q];
  54. 	}
  55. }
  56. int main() 
  57. {
  58. 	std::ios::sync_with_stdio(false);
  59. 	initialise();
  60. 	ll n,m;
  61. 	cin>>n>>m;
  62. 	ll maxw = -1;
  63. 	F(i,1,m)
  64. 	{
  65. 		ll u,v,w;
  66. 		cin>>u>>v>>w;
  67. 		g[w].pb(mp(u,v));
  68. 		g[w].pb(mp(v,u));
  69. 		maxw = max(maxw,w);
  70. 	}
  71. 	ll t = 0;
  72. 	ll ans = 0;
  73. 	RF(i,maxw,1)
  74. 	{
  75. 		ll sz = g[i].size();
  76. 		if(sz>0)
  77. 		{
  78. 			ll u = g[i][0].ff;
  79. 			ll v = g[i][0].ss;
  80. 			//cout<<u<<" "<<v<<" "<<i<<endl;
  81. 			ll p,q;
  82. 			p = root(u);
  83. 			q = root(v);
  84. 			if(p!=q)
  85. 			{
  86. 				//cout<<size[p]<<" "<<size[q]<<" "<<t<<endl;
  87. 				ans = (ans%mod + (((size[p])*(size[q]) + t)*i)%mod)%mod;
  88. 				t = (((size[p])*(size[q]))%mod + t%mod)%mod;
  89. 				Union(u,v);
  90. 			}
  91. 			else
  92. 			{
  93. 				ans += t*i;
  94. 				ans%=mod;
  95. 			}
  96. 			/*F(i,1,n)
  97. 			{
  98. 				cout<<size[i]<<" ";
  99. 				//cout<<endl;
  100. 			}*/
  101. 			//cout<<endl;
  102. 		}
  103. 	}
  104. 	cout<<ans<<endl;
  105. 	return 0;
  106. }
Success #stdin #stdout 0.01s 8928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/OQtINb
problem KOICOST, based on SPOJ submission 16647806 (C++14), 2016-04-01 17:05:43
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!