fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define gc getchar_unlocked
  4. #define fo(i,n) for(int i=0;i<n;i++)
  5. #define Fo(i,k,n) for(int i = k ;i<=n;i++)
  6. #define FO(i,n,k) for(int i = n;i>=k;i--)
  7. #define ll long long
  8. #define si(x)   scanf("%d",&x)
  9. #define sl(x)   scanf("%lld",&x)
  10. #define ss(s)   scanf("%s",s)
  11. #define pi(x)   printf("%d\n",x)
  12. #define pl(x)   printf("%lld\n",x)
  13. #define ps(s)   printf("%s\n",s)
  14. #define deb(x) cout << #x << "=" << x << endl
  15. #define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
  16. #define pb push_back
  17. #define mp make_pair
  18. #define F first
  19. #define S second
  20. #define all(x) x.begin(), x.end()
  21. #define clr(x) memset(x, 0, sizeof(x))
  22. #define mems(a,x) memset(a,x,sizeof(a))
  23. #define sortall(x) sort(all(x))
  24. #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
  25. #define PI 3.1415926535897932384626
  26. typedef pair<int, int>  pii;
  27. typedef pair<ll, ll>    pl;
  28. typedef vector<int>     vi;
  29. typedef vector<ll>      vl;
  30. typedef vector<pii>     vpii;
  31. typedef vector<pl>      vpl;
  32. typedef vector<vi>      vvi;
  33. typedef vector<vl>      vvl;
  34. mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
  35. int rng(int lim) {
  36.     uniform_int_distribution<int> uid(0, lim - 1);
  37.     return uid(rang);
  38. }
  39. const int mod =   998244353; //1000000007;
  40. const int N = 3e5, M = N;
  41.  
  42. //vi g[N];
  43. //int a[N];
  44.  
  45. ll find(vector<ll> &parent, ll a)
  46. {
  47.     return (parent[a] = (parent[a] == a ? a : find(parent, parent[a])));
  48. }
  49.  
  50. void Union(vector<ll> &parent, vector<ll> &parent2, vector<ll> &rank, vector<ll> &count, vector<ll> &sum, ll a, ll b)
  51. {
  52.  
  53.     a = find(parent, parent2[a]);
  54.  
  55.     b = find(parent, parent2[b]);
  56.  
  57.  
  58.     if (a == b)
  59.         return;
  60.  
  61.     if (rank[a] == rank[b])
  62.     {
  63.         rank[a]++;
  64.     }
  65.  
  66.     if (rank[a] >= rank[b])
  67.     {
  68.         parent[b] = a;
  69.         sum[a] += sum[b];
  70.         count[a] += count[b];
  71.     }
  72.     else
  73.     {
  74.         parent[a] = b;
  75.         sum[b] += sum[a];
  76.         count[b] += count[a];
  77.     }
  78. }
  79.  
  80. void move(vector<ll> &parent, vector<ll> &parent2, vector<ll> &count, vector<ll> &sum, ll a, ll b)
  81. {
  82.     ll a1 = find(parent, parent2[a]);
  83.  
  84.     b = find(parent, parent2[b]);
  85.  
  86.     if (a == b)
  87.         return;
  88.  
  89.     parent2[a] = b;
  90.  
  91.     sum[b] += a;
  92.     count[b] += 1;
  93.  
  94.     sum[a1] -= a;
  95.     count[a1] -= 1;
  96.  
  97. }
  98.  
  99. void solve()
  100. {
  101.     ll n, m;
  102.     cin >> n >> m;
  103.  
  104.     vector<ll> parent(n + 1), parent2(n + 1), count(n + 1), sum(n + 1), rank(n + 1);
  105.     fo(i, n + 1)
  106.     {
  107.         parent[i] = i;
  108.         parent2[i] = i;
  109.         count[i] = 1;
  110.         sum[i] = i;
  111.         rank[i] = 0;
  112.     }
  113.  
  114.     fo(i, m)
  115.     {
  116.         ll x, y, z;
  117.         cin >> x >> y;
  118.         if (x == 1)
  119.         {
  120.             cin >> z;
  121.             /* code */
  122.             Union(parent, parent2, rank, count, sum, y, z);
  123.         }
  124.         else if (x == 2)
  125.         {
  126.             cin >> z;
  127.             move(parent, parent2, count, sum, y, z);
  128.         }
  129.         else
  130.         {
  131.             y = find(parent, parent2[y]);
  132.             cout << count[y] << " " << sum[y] << endl;
  133.         }
  134.     }
  135. }
  136.  
  137. int main() {
  138.     //ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  139.     srand(chrono::high_resolution_clock::now().time_since_epoch().count());
  140.  
  141.     int t = 1;
  142.     // cin >> t;
  143.     while (t--) {
  144.         solve();
  145.     }
  146.  
  147.     return 0;
  148. }
  149.  
  150.  
  151.  
  152.  
  153.  
Success #stdin #stdout 0s 4968KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/eGhngn
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!