fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.  
  5. 	int Q;
  6. 	cin >> Q;	// number of queries
  7. 	assert(Q<=100000&&Q>=1);
  8. 	bool root=0;    // root denotes the color of the ROOT 0-> black 1-> white.
  9. 	while(Q--){
  10. 		string ch;
  11. 		int x,y;
  12. 		cin >> ch;
  13. 		// Qi -> change color all black nodes to red and all red nodes to black
  14. 		// Qb -> number of black nodes on the path from node x to node y.
  15. 		// Qr -> number of red nodes on the path from node x to node y.
  16. 		if(ch[1]=='i'){
  17. 			root=root^1;	// toggling root color
  18.  
  19. 		}else{
  20. 			cin >> x >> y;
  21. 			assert(x<=1000000000&&x>=1);
  22. 			assert(y<=1000000000&&y>=1);
  23. 			bool colx;
  24. 			int c=0,xx,pathlen=0;
  25. 			xx=x;
  26. 			while(xx){    // c number of nodes on the path from x to root
  27. 				c++;  // this is used to find the color of node x.
  28. 				xx/=2;
  29. 			}
  30. 			c&1 ? colx=root : colx=root^1; // getting the color of node x
  31.  
  32. 			while(1){
  33. 				if(x==y){
  34. 					pathlen++;
  35. 					break;
  36. 				}
  37. 				if(x>y)
  38. 					x/=2;
  39. 				else
  40. 					y/=2;
  41. 				pathlen++;
  42. 			}
  43. 			// total pathlen from node x to node y
  44. 			// depending upon the color of node x and path length from node x to node y.
  45. 			// we can answer number of black/red nodes on the path from x to y.
  46. 			if(ch[1]=='b'){
  47. 				if(colx){
  48. 					cout << pathlen/2 << endl;
  49. 				}else{
  50. 					cout << (pathlen+1)/2 << endl;
  51. 				}
  52. 			}else{
  53. 				if(colx){
  54. 					cout << (pathlen+1)/2 << endl;
  55. 				}else{
  56. 					cout << pathlen/2 << endl;
  57. 				}
  58. 			}
  59. 		}	
  60. 	}
  61. 	return 0;
  62. }
Runtime error #stdin #stdout #stderr 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:21: int main(): Assertion `x<=1000000000&&x>=1' failed.
https://ideone.com/3XLbpA
language:
C++14 (gcc 8.3)
created:
9 years 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!