fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ;
  3.  
  4. #define ft first
  5. #define sd second 
  6. #define pb push_back
  7. #define all(x) x.begin(),x.end() 
  8.  
  9. #define ll long long int 
  10. #define vi vector<int>
  11. #define vii vector<pair<int,int> >
  12. #define pii pair<int,int>
  13. #define vl vector<ll>
  14. #define vll vector<pair<ll,ll> >
  15. #define pll pair<ll,ll>
  16. #define mp make_pair
  17.  
  18. #define sc1(x) scanf("%d",&x)
  19. #define sc2(x,y) scanf("%d%d",&x,&y)
  20. #define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)
  21.  
  22. #define scll1(x) scanf("%lld",&x)
  23. #define scll2(x,y) scanf("%lld%lld",&x,&y)
  24. #define scll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
  25.  
  26. #define pr1(x) printf("%d\n",x)
  27. #define pr2(x,y) printf("%d %d\n",x,y)
  28. #define pr3(x,y,z) printf("%d %d %d\n",x,y,z)
  29.  
  30. #define prll1(x) printf("%lld\n",x)
  31. #define prll2(x,y) printf("%lld %lld\n",x,y)
  32. #define prll3(x,y,z) printf("%lld %lld %lld\n",x,y,z)
  33.  
  34. #define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;
  35.  
  36. const int mod = 1000000000 + 7 ;
  37. const int maxn = 300000 + 10 ;
  38.  
  39.  
  40. /*
  41.  * C++ program to Implement AVL Tree
  42.  */
  43.  
  44. #define pow2(n) (1 << (n))
  45. using namespace std;
  46.  
  47. /*
  48.  * Node Declaration
  49.  */
  50. struct avl_node
  51. {
  52.     int data , sz ;
  53.     struct avl_node *left;
  54.     struct avl_node *right;
  55.  
  56. } *root[maxn];
  57.  
  58. /*
  59.  * Class Declaration
  60.  */
  61. class avlTree
  62. {
  63.     public:
  64.         int height(avl_node *);
  65.         int diff(avl_node *);
  66.         avl_node *rr_rotation(avl_node *);
  67.         avl_node *ll_rotation(avl_node *);
  68.         avl_node *lr_rotation(avl_node *);
  69.         avl_node *rl_rotation(avl_node *);
  70.         avl_node* balance(avl_node *);
  71.         avl_node* insert(avl_node *, int );
  72.         void display(avl_node *,avl_node *, int);
  73.         void inorder(avl_node *);
  74.         void preorder(avl_node *);
  75.         void postorder(avl_node *);
  76.         int getkthelement(avl_node *,int) ;
  77.         void freebst(avl_node *) ;
  78. };
  79.  
  80. /*
  81.  * Main Contains Menu
  82.  */
  83. avlTree avl ;
  84. int parent[maxn] , _rank[maxn] , setno[maxn] ;
  85. vi adj[maxn] ;
  86.  
  87.  
  88. void _union(int x,int y,int z){
  89. 	x = setno[x] ;
  90. 	y = setno[y] ;
  91. 	setno[x] = setno[y] = -1 ; 
  92. 	if(x != y){
  93. 		if(_rank[x] < _rank[y]){
  94. 			parent[x] = y ;
  95. 			setno[z] = y ;
  96. 			_rank[y] += _rank[x] ; 
  97. 			for(int i=0;i<adj[x].size();i++){
  98. 				root[y] = avl.insert(root[y],adj[x][i]) ;
  99. 				adj[y].pb(adj[x][i]) ;
  100. 			}
  101. 			adj[x].clear() ;
  102. 			avl.freebst(root[x]) ;
  103. 		}else{
  104. 			parent[y] = x ;
  105. 			setno[z] = x ;
  106. 			_rank[x] += _rank[y] ;
  107. 			for(int i=0;i<adj[y].size();i++){
  108. 				root[x] = avl.insert(root[x],adj[y][i]) ;
  109. 				adj[x].pb(adj[y][i]) ;
  110. 			}
  111. 			adj[y].clear() ;
  112. 			avl.freebst(root[y]) ;
  113. 		}
  114. 	}
  115. }
  116.  
  117. int main()
  118. {
  119.  
  120. 	int n , q , cnt = 0 ;
  121. 	cin >> n >> q ;
  122.   	for(int i=1;i<=n;i++){
  123.   		parent[i] = i ; 
  124.   		_rank[i] = 1 ;
  125.   		setno[i] = i ; 
  126.   		adj[i].pb(i) ;
  127.   		root[i] = avl.insert(root[i],i) ;
  128.   	}
  129.  
  130.   	while( q-- ){
  131.   		string ch ;
  132.   		cin >> ch ;
  133.   		int x , y ;
  134.   		sc2(x,y) ;
  135.   		if(ch[0] == 'U'){
  136.   			cnt ++ ;
  137.   			_union(x,y,n+cnt) ;
  138.   		}else{
  139.   			x = setno[x] ; assert( x != -1 ) ;
  140.   			printf("%d\n",avl.getkthelement(root[x],y)) ;
  141.   		}
  142.   	}
  143.     return 0;
  144. }
  145.  
  146. /*
  147.  * Height of AVL Tree
  148.  */
  149. int avlTree::height(avl_node *temp)
  150. {
  151.     int h = 0;
  152.     if (temp != NULL)
  153.     {
  154.         int l_height = height (temp->left);
  155.         int r_height = height (temp->right);
  156.         int max_height = max (l_height, r_height);
  157.         h = max_height + 1;
  158.     }
  159.     return h;
  160. }
  161.  
  162.  
  163.  void avlTree::freebst(avl_node *root){
  164.  
  165.  	if(!root) return ;
  166.  	freebst(root->left) ;
  167.  	freebst(root->right) ;
  168.  	delete root ;
  169.  }
  170. /**
  171. 	kth element in the bst
  172.  
  173. **/
  174.  
  175.  int avlTree::getkthelement(avl_node *root,int k)
  176. {
  177. 	int left , right ;
  178. 	left =  (root->left) ? root->left->sz : 0 ;
  179. 	right = (root->right) ? root->right->sz : 0 ;
  180. 	if(left >= k)
  181. 		return getkthelement(root->left,k) ;
  182. 	else if(left+1 == k)
  183. 		return root->data ;
  184. 	else
  185. 		return getkthelement(root->right,k-left-1) ;
  186. }
  187.  
  188. /*
  189.  * Height Difference 
  190.  */
  191. int avlTree::diff(avl_node *temp)
  192. {
  193.     int l_height = height (temp->left);
  194.     int r_height = height (temp->right);
  195.     int b_factor= l_height - r_height;
  196.     return b_factor;
  197. }
  198.  
  199. /*
  200.  * Right- Right Rotation
  201.  */
  202. avl_node *avlTree::rr_rotation(avl_node *parent)
  203. {
  204.     avl_node *temp;
  205.     temp = parent->right;
  206.     parent->right = temp->left;
  207.     parent->sz = ( parent->left ? parent->left->sz : 0 ) + (parent->right ? parent->right->sz : 0) + 1 ;
  208.     temp->left = parent;
  209.     temp->sz = ( temp->left ? temp->left->sz : 0 ) + (temp->right ? temp->right->sz : 0) + 1 ;
  210.     return temp;
  211. }
  212. /*
  213.  * Left- Left Rotation
  214.  */
  215. avl_node *avlTree::ll_rotation(avl_node *parent)
  216. {
  217.     avl_node *temp;
  218.     temp = parent->left;
  219.     parent->left = temp->right;
  220.     parent->sz = ( parent->left ? parent->left->sz : 0 ) + (parent->right ? parent->right->sz : 0) + 1 ;
  221.     temp->right = parent;
  222.     temp->sz = ( temp->left ? temp->left->sz : 0 ) + (temp->right ? temp->right->sz : 0) + 1 ;
  223.     return temp;
  224. }
  225.  
  226. /*
  227.  * Left - Right Rotation
  228.  */
  229. avl_node *avlTree::lr_rotation(avl_node *parent)
  230. {
  231.     avl_node *temp;
  232.     temp = parent->left;
  233.     parent->left = rr_rotation(temp);
  234.     parent->sz = ( parent->left ? parent->left->sz : 0 ) + (parent->right ? parent->right->sz : 0) + 1 ;
  235.     return ll_rotation (parent);
  236. }
  237.  
  238. /*
  239.  * Right- Left Rotation
  240.  */
  241. avl_node *avlTree::rl_rotation(avl_node *parent)
  242. {
  243.     avl_node *temp;
  244.     temp = parent->right;
  245.     parent->right = ll_rotation (temp);
  246.     parent->sz = ( parent->left ? parent->left->sz : 0 ) + (parent->right ? parent->right->sz : 0) + 1 ;
  247.     return rr_rotation (parent);
  248. }
  249.  
  250. /*
  251.  * Balancing AVL Tree
  252.  */
  253. avl_node *avlTree::balance(avl_node *temp)
  254. {
  255.     int bal_factor = diff (temp);
  256.     if (bal_factor > 1)
  257.     {
  258.         if (diff (temp->left) > 0)
  259.             temp = ll_rotation (temp);
  260.         else
  261.             temp = lr_rotation (temp);
  262.     }
  263.     else if (bal_factor < -1)
  264.     {
  265.         if (diff (temp->right) > 0)
  266.             temp = rl_rotation (temp);
  267.         else
  268.             temp = rr_rotation (temp);
  269.     }
  270.     return temp;
  271. }
  272.  
  273. /*
  274.  * Insert Element into the tree
  275.  */
  276. avl_node *avlTree::insert(avl_node *root, int value)
  277. {
  278.     if (root == NULL)
  279.     {
  280.         root = new avl_node;
  281.         root->data = value;
  282.         root->left = NULL;
  283.         root->right = NULL;
  284.         root->sz = 1 ; 
  285.         return root;
  286.     }
  287.     else if (value < root->data)
  288.     {
  289.         root->left = insert(root->left, value);
  290.         root->sz = ( (root->left) ? root->left->sz : 0 ) + ( (root->right) ? root->right->sz : 0 ) + 1 ;
  291.         root = balance (root);
  292.     }
  293.     else if (value >= root->data)
  294.     {
  295.         root->right = insert(root->right, value);
  296.         root->sz = ( (root->left) ? root->left->sz : 0 ) + ( (root->right) ? root->right->sz : 0 ) + 1 ;
  297.         root = balance (root);
  298.     }
  299.     root->sz = ( (root->left) ? root->left->sz : 0 ) + ( (root->right) ? root->right->sz : 0 ) + 1 ;
  300.     return root;
  301. }
Runtime error #stdin #stdout 0.04s 23056KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DKQVbo
language:
C++14 (gcc 8.3)
created:
9 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!