fork download 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <vector>
  4. using namespace std;
  5. typedef long long Int;
  6.  
  7. int groupid[100111];
  8. Int sum[100111];
  9. int sz[100111];
  10. int n,m;
  11.  
  12. vector<int> group[100111];
  13.  
  14. void Union(int a,int b) ///Operation 1
  15. {
  16.     int r1=groupid[a];
  17.     int r2=groupid[b];
  18.     int swp,i;
  19.  
  20.     if (r1==r2)
  21.     return;
  22.  
  23.     if (group[r2].size()>group[r1].size()) ///Make sure we're iterating the smaller group
  24.     {
  25.         swp=r1;
  26.         r1=r2;
  27.         r2=swp;
  28.     }
  29.  
  30.     for (i=0;i<group[r2].size();i++)
  31.     {
  32.         if ( groupid[ group[r2][i] ]==r2 ) ///Check whether the element is not a leftover
  33.         {
  34.             group[r1].push_back(group[r2][i]); ///Add it to the new group
  35.             groupid[ group[r2][i] ]=r1; ///Remember that it's in the new group
  36.         }
  37.     }
  38.  
  39.     sum[r1]+=sum[r2]; ///Update new group values
  40.     sz[r1]+=sz[r2];
  41.  
  42.     return;
  43. }
  44.  
  45. void Move(int a,int b) ///Operation 2
  46. {
  47.     int r1=groupid[a];
  48.     int r2=groupid[b];
  49.  
  50.     if (r1==r2)
  51.     return;
  52.  
  53.     sz[r1]--;
  54.     sum[r1]-=(Int)a; ///Update old group values
  55.  
  56.     sz[r2]++;
  57.     sum[r2]+=(Int)a; ///Update new group values
  58.  
  59.     group[r2].push_back(a); ///Add a to the new group
  60.  
  61.     groupid[a]=r2; ///Update a's group so that we don't mix it with the leftover
  62.  
  63.     return;
  64. }
  65.  
  66. int main()
  67. {
  68.     int i,j;
  69.     int cm,a,b;
  70.  
  71.     while(scanf("%d %d",&n,&m)==2)
  72.     {
  73.         for (i=1;i<=n;i++) ///Initialise every element to be in its own group
  74.         {
  75.             groupid[i]=i;
  76.             sz[i]=1;
  77.             sum[i]=i;
  78.  
  79.             group[i].clear();
  80.             group[i].push_back(i);
  81.         }
  82.  
  83.         for (i=1;i<=m;i++)
  84.         {
  85.             scanf("%d",&cm);
  86.  
  87.             if (cm==1)
  88.             {
  89.                 scanf("%d %d",&a,&b);
  90.  
  91.                 Union(a,b);
  92.             }
  93.             else if (cm==2)
  94.             {
  95.                 scanf("%d %d",&a,&b);
  96.  
  97.                 Move(a,b);
  98.             }
  99.             else
  100.             {
  101.                 scanf("%d",&a);
  102.  
  103.                 printf("%d %lld\n",sz[ groupid[a] ],sum[ groupid[a] ]);
  104.             }
  105.         }
  106.     }
  107.  
  108.     return 0;
  109. }
  110.  
Success #stdin #stdout 0s 6196KB
comments (?)
stdin 
5 7
1 1 2
2 3 4
1 3 5
3 4
2 4 1
3 4
3 3
stdout 
3 12
3 7
2 8
https://ideone.com/fFU3e3
language:
C++14 (gcc 8.3)
created:
8 years 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!