fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long sum[100001];
  5. int freq[100001];
  6. int ingroup[100001];
  7.  
  8.  
  9. int main()
  10. {
  11.     int m,n,temp;
  12.     while(scanf("%d",&m)!=EOF)
  13.     {
  14.         scanf("%d",&n);
  15.         set<int> s[n+1];
  16.         for(temp=1;temp<=m;temp++)
  17.         {
  18.         	ingroup[temp]=temp;
  19.             sum[temp]=temp;
  20.             freq[temp]=1;
  21.             s[temp].insert(temp);
  22.         }
  23.         for(temp=0;temp<n;temp++)
  24.         {
  25.             int key;
  26.             scanf("%d",&key);
  27.             int a,b;
  28.             if(key==1)
  29.             {
  30.                 scanf("%d %d",&a,&b);
  31.                 int x=ingroup[a],y=ingroup[b]; 
  32.                 if(x==y)	continue;
  33.                 if(s[x].size()<s[y].size())	swap(x,y);
  34.  
  35.                 sum[x]+=sum[y];
  36.                 freq[x]+=freq[y];
  37.                 while(!s[y].empty())
  38.                 {
  39.                 	auto it=s[y].begin();
  40.                 	int element=*it;
  41.                 	ingroup[element]=x;
  42.                 	s[x].insert(element);
  43.                 	s[y].erase(element);
  44. 				}
  45.             }
  46.             if(key==2)
  47.             {
  48.                 scanf("%d %d",&a,&b);
  49.                 int x=ingroup[a],y=ingroup[b];
  50.                 if(x==y)	continue;
  51.  
  52.                 sum[x]-=a;
  53.                 freq[x]--;
  54.  
  55.                 sum[y]+=a;
  56.                 freq[y]++;
  57.  
  58.                 ingroup[a]=y;
  59.  
  60.                 s[x].erase(a);
  61.                 s[y].insert(a);
  62.  
  63.             }
  64.             if(key==3)
  65.             {
  66.                 scanf("%d",&a);
  67.                 int x=ingroup[a];
  68.  
  69.                 printf("%d %lld\n",freq[x],sum[x]);
  70.             }
  71.         }
  72.     }
  73. }
Success #stdin #stdout 0s 5024KB
comments (?)
stdin
copy 
5 7
1 1 2
2 3 4
1 3 5
3 4
2 4 1
3 4
3 3
stdout
copy 
3 12
3 7
2 8
https://ideone.com/c8agkn
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!