Advertisement
cosenza987

Untitled

Apr 13th, 2022
1,163
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.64 KB | None | 0 0
  1. // Problem: C. Experience
  2. // Contest: Codeforces - ITMO Academy: pilot course - Disjoint Sets Union - Step 1
  3. // Memory Limit: 64 MB
  4. // Time Limit: 2000 ms
  5. // Date / Time: 2022-04-13 18:26:09
  6. // Author: cosenza
  7. // всё что ни делается - всё к лучшему
  8. // check list -> long long, special cases, array size, mod (a*b%p*c%p not a*b*c%p  ,  (a-b+p)%p not a-b )
  9. //
  10. // Powered by CP Editor (https://cpeditor.org)
  11.  
  12. //Слава Україні, Героям слава 🇺🇦
  13.  
  14. #include <bits/stdc++.h>
  15.  
  16. using namespace std;
  17.  
  18. const int N = 2e5 + 7;
  19.  
  20. int par[N], sz[N], ex[N];
  21.  
  22. int find(int a) {
  23.     return par[a] == a ? a : find(par[a]);
  24. }
  25.  
  26. void unite(int a, int b) {
  27.     if((a = find(a)) == (b = find(b))) {
  28.         return;
  29.     }
  30.     if(sz[a] < sz[b]) {
  31.         swap(a, b);
  32.     }
  33.     par[b] = a;
  34.     sz[a] += sz[b];
  35.     ex[b] -= ex[a];
  36. }
  37.  
  38. int sum(int a) {
  39.     if(par[a] == a) {
  40.         return ex[a];
  41.     } else {
  42.         return ex[a] + sum(par[a]);
  43.     }
  44. }
  45.  
  46. void add(int a, int x) {
  47.     a = find(a);
  48.     ex[a] += x;
  49. }
  50.  
  51. int main() {
  52.     ios_base::sync_with_stdio(false);
  53.     cin.tie(0);
  54.     for(int i = 0; i < N; i++) {
  55.         par[i] = i;
  56.         sz[i] = 1;
  57.     }
  58.     int n, q;
  59.     cin >> n >> q;
  60.     while(q--) {
  61.         string s;
  62.         cin >> s;
  63.         if(s == "add") {
  64.             int x, y;
  65.             cin >> x >> y;
  66.             add(x, y);
  67.         } else if(s == "join") {
  68.             int x, y;
  69.             cin >> x >> y;
  70.             unite(x, y);
  71.         } else {
  72.             int x;
  73.             cin >> x;
  74.             cout << sum(x) << "\n";
  75.         }
  76.     }
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement