fork download
copy 
  1. /* Author : Nguyen Thanh Tung */
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define endl                 '\n'
  6. #define int                  long long
  7.  
  8. using namespace              std;
  9.  
  10. typedef pair<int, int>       ii;
  11.  
  12. const int       N            = 1e6 + 7;
  13. const long long oo           = 1e18 + 7;
  14. const long long MOD          = 1e9 + 7;
  15.  
  16. int n, a[N];
  17. ii node[N];
  18. int par[N];
  19.  
  20. struct edge {
  21. 	int u, v, w;
  22. };
  23.  
  24. vector<edge> canh;
  25.  
  26. bool cmp(edge a, edge b) {
  27. 	return a.w < b.w;
  28. }
  29.  
  30. int find_set(int u) {
  31. 	if(u == par[u]) {
  32. 		return u;
  33. 	}
  34. 	return par[u] = find_set(par[u]);
  35. }
  36.  
  37. void union_sets(int u, int v) {
  38. 	u = find_set(u);
  39. 	v = find_set(v);
  40. 	par[v] = u;
  41. }
  42.  
  43. void solve() {
  44. 	cin >> n;
  45. 	for(int i = 1; i <= n; ++i) {
  46. 		cin >> a[i];
  47. 		node[i] = {a[i], i};
  48. 		par[i] = i;
  49. 	}
  50. 	sort(node + 1, node + n + 1);
  51. 	for(int i = 2; i <= n; ++i) {
  52. 		int u = node[i].first;
  53. 		int v = node[i - 1].second;
  54. 		int w = abs(node[i].second - node[i - 1].second);
  55. 		canh.push_back({u, v, w});
  56. 	}
  57. 	int s = 0, d = 0;
  58. 	sort(canh.begin(), canh.end(), cmp);
  59. 	for(auto i : canh) {
  60. 		int u = i.u, v = i.v, w = i.w;
  61. 		if(find_set(u) != find_set(v)) {
  62. 			union_sets(u, v);
  63. 			s += w;
  64. 			d++;
  65. 			if(d == n - 1) {
  66. 				break;
  67. 			}
  68. 		}
  69. 	}
  70. 	cout << s;
  71. }
  72.  
  73. #define TASK "code"
  74.  
  75. signed main () {
  76.     ios_base::sync_with_stdio (false);
  77.     cin.tie(nullptr), cout.tie(nullptr);
  78.     if (fopen(TASK".inp", "r")) {
  79.        freopen(TASK".inp", "r", stdin);
  80.        freopen(TASK".out", "w", stdout);
  81.     }
  82.     int T = 1;
  83.     //cin >> T;
  84.     while(T--) {
  85.         solve();    
  86.     }
  87.     return 0;
  88. }
  89.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CXtwUx
language:
C++14 (gcc 8.3)
created:
1 day 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!