Guest User

Untitled

a guest
Oct 22nd, 2021
200
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.22 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define mp make_pair
  3. #define mt make_tuple
  4. using namespace std;
  5. typedef long long ll;
  6. typedef pair<int,int> pii;
  7. typedef pair<ll,ll> pll;
  8. const ll INFL = (1LL<<62)-1;
  9. const int INF = (1<<30)-1;
  10. const int MAXN = 200001;
  11.  
  12. int pai[MAXN];
  13. int expp[MAXN];
  14.  
  15. int find(int in){
  16.     if(pai[in]==in)
  17.         return in;
  18.     int cur = find(pai[in]);
  19.     if(cur != pai[in]){
  20.         expp[in]+=expp[pai[in]];
  21.     }
  22.     return pai[in] = cur;
  23. }
  24.  
  25. void onion(int a, int b){
  26.     a = find(a);
  27.     b = find(b);
  28.     if(rand()&1)
  29.         swap(a,b);
  30.     if(a==b)
  31.         return;
  32.     pai[a] = b;
  33.     expp[a]-=expp[b];
  34. }
  35.  
  36. int main(){
  37.  
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(NULL);
  40.    
  41.     int n, m;
  42.     cin >> n >> m;
  43.     iota(pai,pai+n+1,0);
  44.     for(int i = 0; i < m; i++){
  45.         string s;
  46.         int a, b;
  47.         cin >> s;
  48.         if(s=="add"){
  49.             cin >> a >> b;
  50.             a = find(a);
  51.             expp[a]+=b;
  52.         } else if(s=="join"){
  53.             cin >> a >> b;
  54.             onion(a,b);
  55.         } else {
  56.             cin >> a;
  57.             find(a);
  58.             cout << expp[a] + (pai[a] == a ? 0 : expp[pai[a]]) << '\n';
  59.         }
  60.     }
  61.    
  62.     return 0;
  63.  
  64. }
Add Comment
Please, Sign In to add comment