fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define TASK "test"
  5.  
  6. #define int long long
  7. #define ii pair <int, int>
  8. #define fi first
  9. #define sc second
  10.  
  11. #define rep(i, s, e) for (int _s = (s), _e = (e), i = _s; i <= _e; i++)
  12. #define reo(i, s, e) for (int _s = (s), _e = (e), i = _s; i >= _e; i--)
  13.  
  14. const int maxn = (int)1e5 + 5;
  15.  
  16. int n, k;
  17. int par[maxn], sz[maxn];
  18. int sum[maxn], dist[maxn];
  19.  
  20. ii find (int u) {
  21. 	if (u == par[u]) return {u, 0};
  22. 	ii x = find(par[u]);
  23.  
  24. 	par[u] = x.fi, dist[u] += x.sc;
  25. 	return {par[u], dist[u]};
  26. }
  27.  
  28. void uniset (int u, int v) {
  29. 	u = find(u).fi, v = find(v).fi;
  30.  
  31. 	if (u == v) return ;
  32. 	if (sz[u] < sz[v]) swap(u, v);
  33.  
  34. 	par[v] = u;
  35. 	sz[u] += sz[v];
  36.  
  37. 	dist[v] += sum[v] - sum[u];
  38. }
  39.  
  40. signed main () {
  41. 	cin.tie(0)->sync_with_stdio(false);
  42.  
  43. 	#ifndef ONLINE_JUDGE
  44. 	freopen(TASK".inp","r",stdin);
  45. 	freopen(TASK".out","w",stdout);
  46. 	#endif
  47.  
  48. 	cin >> n >> k;
  49.  
  50. 	rep (u, 1, n) {
  51. 		par[u] = u;
  52. 		sz[u] = 1;
  53. 	}	
  54.  
  55. 	while (k--) {
  56. 		string s; cin >> s;
  57. 		int u, v; cin >> u;
  58. 		if (s[0] == 'g') {
  59. 			ii x = find(u);
  60. 			cout << sum[x.fi] + x.sc << '\n';
  61. 		}
  62. 		else {
  63. 			cin >> v;
  64. 			if (s[0] == 'j') uniset(u, v);
  65. 			else sum[find(u).fi] += v;
  66. 		}
  67. 	}
  68.  
  69. 	return 0;
  70. }
  71.  
Success #stdin #stdout 0s 5272KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cd0X8N
language:
C++14 (gcc 8.3)
created:
4 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!