fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fu(i,a,b) for (int i=a; i<=b; i++)
  3. #define int long long
  4. const int maxn=1e5;
  5. using namespace std;
  6. int n,q; vector<int> a,R,dept; map<int,int> color[maxn+5];
  7.  
  8. void init(){
  9.     cin >> n >> q;
  10.     a.resize(n+1); R.resize(n+1); dept.resize(n+1);
  11.     fu(i,1,n){
  12.         cin >> a[i];
  13.         R[i]=i;
  14.         color[i][a[i]]++;
  15.     }
  16. }
  17.  
  18. int get_root(int u){
  19.     while(R[u]!=u) u=R[u]; 
  20.     return u;
  21. }
  22.  
  23. void connect(int root, int child){
  24.     R[child]=root;
  25.     for(auto [x,cnt]: color[child]) color[root][x]+=cnt;
  26.     color[child].clear();
  27. }
  28.  
  29. void dsu(int u, int v){
  30.     int ru = get_root(u),rv=get_root(v);
  31.     if(ru!=rv){
  32.         if(dept[ru]>dept[rv]) connect(ru,rv);
  33.         else if(dept[ru]<dept[rv]) connect(rv,ru);
  34.         else{
  35.             connect(ru,rv);
  36.             dept[ru]++;
  37.         }
  38.     }
  39. }
  40.  
  41.  
  42. void solve(){
  43.     while(q--){
  44.         int tmp,x,y; cin >> tmp >> x >> y;
  45.         if(tmp==1) dsu(x,y);
  46.         else cout << color[get_root(x)][y] << "\n";
  47.     }
  48. }
  49.  
  50. signed main() {
  51.     ios_base::sync_with_stdio(false); cin.tie(NULL); 
  52.     init();
  53.     solve();
  54. }
  55.  
Success #stdin #stdout 0.01s 8176KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HzPGQ0
language:
C++ (gcc 8.3)
created:
1 year 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!