please tell me what’s wrong in it, which corner case is not working? 2TC gives WA
// 0 : red and 1: black
#include <bits/stdc++.h>
#define fastIO \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);
using namespace std;
unsigned long long int MOD = 1e9 + 7;
unsigned long long int MAX = 1e5;
#define pi pair<int, int>
#define vi vector<int>
#define vvi vector<vi>
#define pushb push_back
#define popf pop_front
#define popb pop_back
#define pushf push_front
#define mipii map<int,pair<int,int>>
typedef long long ll;
typedef unsigned long long ull;
int returnLevel(int a){
int times=1;
while(times!=32){
if(a<=(1<<times)-1)
break;
times++;
}
return times;
}
void printDic(mipii & dic,string type){
cout<<"DIC IS "<<type<<" : "<< endl;
cout<<"NODE "<<" RED COUNT "<<" BLACK COUNT\n";
for(auto ele:dic){
cout<<ele.first<<" : "<<ele.second.first<<" , "<<ele.second.second<<endl;
}
}
void getPathToRoot(int a,mipii&dic,int curColor){
pi color={0,0};
if(curColor==0){
color={1,0};
}
else{
color={0,1};
}
dic[a]=color;
while(a!=1){
if(a%2==0){
a=a/2;
}
else{
a--;
a=a/2;
}
curColor=!curColor;
int red=color.first;
int black=color.second;
if(curColor==0){
red++;
}
else{
black++;
}
color={red,black};
dic[a]=color;
}
}
pi getLCA(mipii&dic1,mipii&dic,int a,int curColor){
pi color={0,0};
if(curColor==0){
color={1,0};
}
else{
color={0,1};
}
dic[a]=color;
while(a!=1){
if(a%2==0){
a=a/2;
}
else{
a--;
a=a/2;
}
curColor=!curColor;
int red=color.first;
int black=color.second;
if(curColor==0){
red++;
}
else{
black++;
}
color={red,black};
dic[a]=color;
if(dic1.find(a)!=dic1.end()){
//cout<<"LCA AT :"<<a<<endl;
int redDic1=dic1[a].first;
int blackDic1=dic1[a].second;
int totalReds=redDic1+red;
int totalBlacks=blackDic1+black;
if(curColor==0){
totalReds--;
}
else{
totalBlacks--;
}
return {totalReds,totalBlacks};
}
}
return {-1,-1};
}
int main()
{
fastIO
int t;
cin>>t;
int invert=0;
while(t--){
string OP;
cin>>OP;
if(OP=="Qi"){
invert++;
}
else{
int s,d;
cin>>s>>d;
int curColor=0;
// this is to get path from src to root
int levelS=returnLevel(s);
if(levelS%2==0){
// red
curColor=0;
}else{
// black
curColor=1;
}
if(invert%2!=0){
curColor=!curColor;
}
mipii dic1;
getPathToRoot(s,dic1,curColor);
//printDic(dic1,"source");
// this is to get path from des to root
int levelD=returnLevel(d);
if(levelD%2==0){
curColor=0;
}else{
curColor=1;
}
if(invert%2!=0){
curColor=!curColor;
}
mipii dic2;
pi count=getLCA(dic1,dic2,d,curColor);
//printDic(dic2,"destination");
if(OP=="Qb"){
cout<<count.second;
}
else{
cout<<count.first;
}
cout<<" ";
}
}
return 0;
}
/*
Algorithm :
1) To get path to root
as left child is 2*v && right child is 2*v+1
so
if : even index say 2 : to reach to root : index/2
else: index : to reach to root : (index-1)/2
2) to get color :
find level of index : nearest greater (2^level-1)
initially:
if level % 2 ==0 :
color = red
else:
color black
count is number of operations of Qi
if count is odd :
color=!color
make a path to root in step1 :
and find the LCA (Lowest common ancestors)
sum up values of all black nodes and red nodes till LCA node.
DS used :
1) map<int,pair<int,int>> first: red , second : black:
this is to calculate all red and black nodes till path or root
for LCA found we calculate black and red nodes till LCA ,
*/