I am getting a runtime error(SIGSEGV) and not able to figure out.
This is my first question using binary lifting implementation.
Please, someone, help me debug.
for sigsegv changing n to 1100000 or 2*10^6 works i dont know why though?( a fairly large value)
still it is giving WA
It is because you are not jumping correctly.
say if no. of jumps required from v vertex are 13 Now 8th jump will have wt>w but 16th jump will have wt<=w i.e mx[up[v][3]]>w(8 jumps) but mx[up[v][4]]<=w(16 jumps) now mx[up[v][3][0]]>w will be greater than w as 9th jump from v will have either more wt or same wt than 13th jump from v so you are getting WA.
FIANL STATEMENT YOU ARE NOT JUMPING PRPERLY HERE:
for(int i=LOG_N-1;i>=0;i–)
{
if(up[v][i]!=-1)
{
if(mx[up[v][i]]>w)
{
long long x=up[up[v][i]][0];
if(x==-1)
pr=c[v];
else
pr=c[v]-c[x];
//cout<<x<<endl;
//cout<<c[v]<<" "<<c[x]<<endl;
done=true;
break;
}
}
}
1 Like
Thank you so much!
You were correct, I wasn’t jumping till the farthest ancestor of v wt>w.
I was just breaking out on the first ancestor of v having wt>w.
Thanks,I got AC