Advertisement
Guest User

Untitled

a guest
Nov 12th, 2019
110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.67 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int ll
  3.  
  4. typedef long long ll;
  5.  
  6. using namespace std;
  7.  
  8. vector<int> r;
  9. vector<int> ex;
  10. vector<int> par;
  11. vector<int> over;
  12. vector<int> adding;
  13. vector<vector<int>> sons;
  14.  
  15. int getPar(int x) {
  16. if (par[x] == x) {
  17. return x;
  18. }
  19. return getPar(par[x]);
  20. }
  21.  
  22. void join(int x, int y) {
  23. x = getPar(x);
  24. y = getPar(y);
  25. if (x == y) {
  26. return;
  27. }
  28. if (r[x] < r[y]) {
  29. swap(x, y);
  30. } else if (r[x] == r[y]) {
  31. r[x]++;
  32. }
  33. for (int i = 0; i < int(sons[y].size()); i++) {
  34. over[sons[y][i]] += adding[x];
  35. ex[sons[y][i]] += adding[y];
  36. sons[x].push_back(sons[y][i]);
  37. }
  38. par[y] = x;
  39. }
  40.  
  41. void add(int x, int ex) {
  42. adding[getPar(x)] += ex;
  43. }
  44.  
  45. int get(int x) {
  46. int parent = getPar(x);
  47. return ex[x] + adding[parent] - over[x];
  48. }
  49.  
  50.  
  51. signed main()
  52. {
  53. ios_base::sync_with_stdio(false);
  54. cin.tie(0);
  55. cout.tie(0);
  56. int n;
  57. cin >> n;
  58. r.resize(n + 1, 1);
  59. par.resize(n + 1);
  60. ex.resize(n + 1, 0);
  61. adding.resize(n + 1, 0);
  62. sons.resize(n + 1, vector<int>(0));
  63. for (int i = 0; i < n; i++) {
  64. par[i] = i;
  65. sons[i].push_back(i);
  66. }
  67. int m;
  68. cin >> m;
  69. string x;
  70. for (int i = 0; i < m; i++) {
  71. cin >> x;
  72. if (x == "add") {
  73. int a, b;
  74. cin >> a >> b;
  75. add(a - 1, b);
  76. } else if (x == "join") {
  77. int a, b;
  78. cin >> a >> b;
  79. join(a - 1, b - 1);
  80. } else {
  81. int a;
  82. cin >> a;
  83. cout << get(--a) << '\n';
  84. }
  85. }
  86. return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement