fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define h0ang ios_base::sync_with_stdio(false); cin.tie(NULL);
  6. #define ll long long
  7. #define fi first
  8. #define se second
  9. #define ii pair<int, int>
  10. #define iii pair<pair<int, int>, int>
  11. #define pb push_back
  12. #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  13.  
  14. const int MOD = 1e9 + 7;//998244353
  15. const int maxN = 2e5 + 5;
  16. int root[maxN], sz[maxN];
  17. map<int, int> mp[maxN];
  18.  
  19. int get_root(int u){
  20.     if(root[u] == u) return u;
  21.     return root[u] = get_root(root[u]);
  22. }
  23.  
  24. void union_(int u, int v){
  25.     u = get_root(u);
  26.     v = get_root(v);
  27.     if(u != v){
  28.         if(sz[u] < sz[v]) swap(u, v);
  29.         root[v] = u;
  30.         sz[u] += sz[v];
  31.     }
  32.     for(auto& it : mp[v]){
  33.         mp[u][it.first] += it.second;
  34.     }
  35. }
  36.  
  37. int main(){
  38.     h0ang
  39. //    freopen("ontap.INP", "r", stdin);
  40. //    freopen("ontap.OUT", "w", stdout);
  41.     int n, q;
  42.     cin >> n >> q;
  43.     int a[n + 5];
  44.     for(int i=1; i <= n; i++){
  45.         cin >> a[i];
  46.         root[i] = i;
  47.         mp[i][a[i]] = 1;
  48.     }
  49.     for(int i=0; i < q; i++){
  50.         int x, u, vc;
  51.         cin >> x >> u >> vc;
  52.         if(x == 1){
  53.             union_(u, vc);
  54.         }
  55.         else{
  56.             int rut = get_root(u);
  57.             cout << mp[rut][vc] << endl;
  58.         }
  59.     }
  60.     cerr << "Time elapsed: " << TIME << "s" << endl;
  61.     return 0;
  62. }
  63.  
Success #stdin #stdout #stderr 0.01s 14236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
Time elapsed: 0.007864s
https://ideone.com/ylx7LD
language:
C++ (gcc 8.3)
created:
13 hours 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!