Advertisement
javacppython

C. Experiece EDU DSU learning series Codeforces

Sep 29th, 2020
179
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
  3. #define FILE_READ_IN freopen("input.txt","r",stdin);
  4. #define FILE_READ_OUT freopen("output.txt","w",stdout);
  5. using namespace std;
  6. typedef long long ll;
  7. typedef long double ld;
  8. #define maxn 100
  9. int parent[maxn]; int SIZE[maxn];
  10. int points[maxn],extra[maxn];
  11. int get(int u){
  12.    if(parent[u]==u)
  13.       return u;
  14.  
  15.    return parent[u]=get(parent[u]);
  16. }
  17. void make_set(int n)
  18. {
  19.    for(int i=1;i<=n;i++)
  20.    {
  21.       parent[i]=i;
  22.       SIZE[i]=1;
  23.       points[i]=0;
  24.       extra[i]=0;
  25.    }
  26.  
  27. }
  28. void UNION(int u,int v)
  29. {
  30.    if(get(u)==get(v)) return;
  31.    u=get(u);
  32.    v=get(v);
  33.  
  34.    if(points[u]>points[v])
  35.    {
  36.       parent[u]=v;
  37.       //SIZE[v]+=SIZE[u];
  38.    }
  39.    else
  40.    {  
  41.       parent[v]=u;
  42.       SIZE[u]+=SIZE[v];
  43.       //extra[v]+=points[u];
  44.    }
  45. }
  46.  
  47. int main(){
  48.     FAST
  49.    #ifndef ONLINE_JUDGE
  50.    FILE_READ_IN
  51.    FILE_READ_OUT
  52.    #endif
  53.    int n,m; cin>>n>>m;
  54.    make_set(n);
  55.  
  56.    for(int i=0;i<m;i++)
  57.    {
  58.       string cmd; cin>>cmd;
  59.       if(cmd=="add")
  60.       {
  61.          int u,v; cin>>u>>v;
  62.          int p=get(u);
  63.          extra[u]+=points[p];
  64.          extra[v]+=points[u];
  65.          points[p]+=v+points[u];
  66.       }
  67.       else if(cmd=="join")
  68.       {
  69.          int u,v; cin>>u>>v;
  70.          UNION(u,v);
  71.       }
  72.       else
  73.       {
  74.          int x; cin>>x;
  75.          int p=get(x);
  76.          //cout<<extra[x]<<" "<<extra[p]<<"\n";
  77.          cout<<points[p]-extra[x]<<"\n";    // substract the points before union from the result
  78.       }
  79.    }
  80.    
  81.    return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement