fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define ull unsigned long long
  5. #define iiii tuple<int,int,int,ll>
  6. #define iii tuple<int,int,ll>
  7. #define ii pair<int,int>
  8. #define fi first
  9. #define se second
  10. using namespace std;
  11. const ll INF=0x3f3f3f3f3f3f3f3fLL;
  12. const ll MOD=1e9+7;
  13. const int MAXN=1e5+5;
  14. int n, q;
  15. int root[MAXN], sz[MAXN], val[MAXN];
  16. int getroot(int s){
  17.     if (s==root[s]) return s;
  18.     int p=root[s];
  19.     int r=getroot(p);
  20.     val[s]+=val[p];
  21.     return root[s]=r;
  22. }
  23. void uni(int a, int b){
  24.     int rx=getroot(a); int ry=getroot(b);
  25.     if (rx==ry) return;
  26.     if (sz[rx]<sz[ry]) swap(rx,ry);
  27.     sz[rx]+=sz[ry];
  28.     root[ry]=rx;
  29.     val[ry]-=val[rx];
  30. }
  31. int main(){
  32.     ios_base::sync_with_stdio(false);
  33.     cin.tie(NULL); cout.tie(NULL);
  34.     cin >> n >> q;
  35.     for (int i=1;i<=n;i++){
  36.         sz[i]=1;
  37.         root[i]=i;
  38.     }
  39.     for (int i=0;i<q;i++){
  40.         string a;
  41.         cin >> a;
  42.         if (a=="join"){
  43.             int b, c;
  44.             cin >> b >> c;
  45.             uni(b,c);
  46.         }
  47.         if (a=="get"){
  48.             int b;
  49.             cin >> b;
  50.             getroot(b);
  51.             cout << val[b] << '\n';
  52.         }
  53.         if (a=="add"){
  54.             int b,c;
  55.             cin >> b >> c;
  56.             val[getroot(b)]+=c;
  57.         }
  58.     }
  59. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/juBwyE
language:
C++ (gcc 8.3)
created:
8 hours 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!