fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // https://w...content-available-to-author-only...s.org/ordered-set-gnu-c-pbds/
  5. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. #define rep(i,s,e) for(int i=s ; i < e ; i++)
  7. #define rrep(i,s,e) for(int i=s ; i > e ; i--)
  8. #define srep(i,s,e,j) for(int i=s ; i < e ; i+=j)
  9. #define tr(i,x) for(auto i : x)
  10. #define vinp(a) for(int i=0 ; i<a.size() ; i++)cin>>a[i]
  11. #define ainp(a,n) for(int i=0; i<n; i++)cin>>a[i]
  12. #define int long long
  13. #define vi vector<int>
  14. #define vvi vector<vector<int>>
  15. #define vs vector<string>
  16. #define vb vector<bool>
  17. #define vpi vector<pii>
  18. #define maxpqi priority_queue<int>
  19. #define minpqi priority_queue <int, vector<int>, greater<int> >
  20. #define mem0(x) memset(x, 0, sizeof(x))
  21. #define mem1(x) memset(x, -1, sizeof(x))
  22. #define pii pair<int,int> 
  23. #define F first
  24. #define S second
  25. #define mk make_pair
  26. #define pb push_back
  27. #define pf push_front
  28. #define endl '\n'
  29. #define gcd(a,b) __gcd(a,b)
  30. #define clr(x) memset(x,0,sizeof(x))
  31. #define lb lower_bound
  32. #define ub upper_bound
  33. #define npos string::npos
  34. #define all(x) x.begin(),x.end()
  35. #define sayyes cout << "YES" << endl
  36. #define sayno cout << "NO" << endl
  37. // --------------- TEMPLATE ENDS ---------------
  38.  
  39.  
  40. #define MXNUM 100005
  41.  
  42. class DSU{
  43. public:
  44.     // 1 indexed;
  45.     int N;
  46.     vector<int>p;
  47.  
  48.     DSU(int len){
  49.         N = len;
  50.         p.resize(N+1, -1);
  51.     }
  52.  
  53.     int Find(int i){
  54.         if(p[i] < 0)return i;
  55.         return p[i] = Find(p[i]);
  56.     }
  57. };
  58.  
  59. vi a;
  60. vi colorToIndex;
  61.  
  62. void solve(int tcase){
  63.     int N, Q; cin >> N >> Q; 
  64.  
  65.     DSU dsu(N);
  66.  
  67.     colorToIndex.clear();
  68.     colorToIndex.resize(MXNUM, -1);
  69.  
  70.     a.clear();
  71.     a.resize(N+1);
  72.  
  73.     rep(i, 1, N+1){
  74.         int col; cin >> col;
  75.  
  76.         if(colorToIndex[col] == -1)
  77.                 colorToIndex[col] = i;
  78.  
  79.         dsu.p[i] = -col;
  80.     }
  81.  
  82.     // Now the task is to segregate all indices of same color together.
  83.     rep(i, 1, N+1){
  84.         int rCur = dsu.Find(i);
  85.  
  86.         int curCol = -dsu.p[rCur];
  87.  
  88.         if(colorToIndex[curCol] == rCur) continue;
  89.  
  90.         dsu.p[colorToIndex[curCol]] = rCur;
  91.         colorToIndex[curCol] = rCur;
  92.     }
  93.  
  94.     vi ans;
  95.     while(Q--){
  96.         int op; cin >> op;
  97.         if(op == 1){
  98.             int cur, next; cin >> cur >> next;
  99.  
  100.             // Edge case: 1 x x
  101.             if(cur == next) continue;
  102.  
  103.             // CASE1: color cur is not present.
  104.             if(colorToIndex[cur] == -1) continue;
  105.  
  106.             // CASE2: cur is present & next is not present.
  107.             if(colorToIndex[next] == -1){
  108.                 int idxCur = colorToIndex[cur];
  109.  
  110.                 // erase all current colors.
  111.                 colorToIndex[cur] = -1;
  112.  
  113.                 int rCur = dsu.Find(idxCur);
  114.                 dsu.p[rCur] = -next;
  115.  
  116.                 colorToIndex[next] = rCur;
  117.             }
  118.  
  119.             // CASE2: both cur & next are present.
  120.             else if(colorToIndex[cur] != -1 && colorToIndex[next] != -1){
  121.                 int idxCur = colorToIndex[cur];
  122.                 int idxNext = colorToIndex[next];
  123.  
  124.                 // erase all current colors.
  125.                 colorToIndex[cur] = -1;
  126.  
  127.                 int rCur = dsu.Find(idxCur);
  128.                 int rNext = dsu.Find(idxNext);
  129.  
  130.                 dsu.p[rCur] = rNext;
  131.  
  132.                 colorToIndex[next] = rNext;
  133.             }
  134.         }else{
  135.             int idx; cin >> idx;
  136.             int rIdx = dsu.Find(idx);
  137.             ans.pb(dsu.p[rIdx]);
  138.         }
  139.     }
  140.  
  141.     cout << "Case " << tcase << ":" << endl;
  142.     for(int x: ans)cout << -x << endl;
  143. }
  144.  
  145. int32_t main(){
  146.     fastio
  147.     // freopen("input.txt","r",stdin);
  148.     // freopen("output.txt","w",stdout);
  149.     int tt = 1;
  150.     cin >> tt;
  151.     rep(i, 1, tt+1){
  152.         solve(i);
  153.     }
  154.     return 0;
  155. }
  156.  
Success #stdin #stdout 0s 5452KB
comments (?)
stdin
copy 
1
5 4
1 2 3 4 5
1 1 3
2 1
1 3 5
2 1
stdout
copy 
Case 1:
3
5
https://ideone.com/O4lHS2
language:
C++14 (gcc 8.3)
created:
2 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!