fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define sz 201000
  5.  
  6. ll par[sz];
  7. ll rnk[sz];
  8. ll add[sz];
  9. ll val[sz];
  10.  
  11. ll getp(ll x)
  12. {
  13. 	if (par[x] == x)
  14. 		return x;
  15. 	return getp(par[x]);
  16. }
  17.  
  18. ll getpolls(ll x)
  19. {
  20. 	if (par[x] == x)
  21. 		return add[x];
  22. 	return add[x] + getpolls(par[x]);
  23. }
  24.  
  25. void uni(ll x, ll y)
  26. {
  27. 	ll u = getp(x);
  28. 	ll v = getp(y);
  29. 	if (u == v)
  30. 		return;
  31. 	if (rnk[u] < rnk[v])
  32. 		swap(u, v);
  33. 	par[v] = u;
  34. 	add[v] -= add[u];
  35. 	if (rnk[u] == rnk[v])
  36. 		rnk[u]++;
  37. }
  38.  
  39. int main()
  40. {
  41. 	ios::sync_with_stdio(0);
  42. 	cin.tie(0); cout.tie(0);
  43.  
  44. 	ll n, q; cin >> n >> q;
  45.  
  46. 	for (ll i = 1; i <= n; i++)
  47. 	{
  48. 		par[i] = i;
  49. 		rnk[i] = 1;
  50. 	}
  51.  
  52. 	while (q--)
  53. 	{
  54. 		string s; cin >> s;
  55. 		if (s == "add")
  56. 		{
  57. 			ll a, b; cin >> a >> b;
  58. 			add[getp(a)] += b;
  59. 		}
  60. 		else if (s == "join")
  61. 		{
  62. 			ll a, b; cin >> a >> b;
  63. 			uni(a, b);
  64. 		}
  65. 		else
  66. 		{
  67. 			ll a; cin >> a;
  68. 			cout << getpolls(a) << "\n";
  69. 		}
  70. 	}
  71.  
  72. 	return 0;
  73. }
Success #stdin #stdout 0s 7560KB
comments (?)
stdin
copy 
3 6
add 1 100
join 1 3
add 1 50
get 1
get 2
get 3
stdout
copy 
150
0
50
https://ideone.com/9rf6sP
language:
C++14 (gcc 8.3)
created:
32 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!