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 (a1 == 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.     while (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.  
  138. int main() {
  139.     //ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  140.     srand(chrono::high_resolution_clock::now().time_since_epoch().count());
  141.  
  142.     int t = 1;
  143.     // cin >> t;
  144.     while (t--) {
  145.         solve();
  146.     }
  147.  
  148.     return 0;
  149. }
  150.  
  151.  
Success #stdin #stdout 0s 4992KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ilHep5
language:
C++14 (gcc 8.3)
created:
3 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!