I was learning about binary lifting and solving this problem on cses, it runs fine on smaller visualizable cases, but is failing on every large testcase. Can someone help?Link to problem
==================
code
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(a) a.begin(),a.end()
#define flash ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define test int t;cin>>t;while(t--)
#define loop(n) for(int i=0;i<n;i++)
#define input(arr,n) for(int i=0;i<n;i++)cin>>arr[i];
#define nline "\n"
#define P pair<ll,pair<ll,ll>>
using namespace std;
using namespace chrono;
int MOD=1000000007;
bool valid(int x,int y,int n,int m){return x>=0 && x<n && y>=0 && y<m;}
int powMod(int a,int n){ ll ans=1;for(int i=1;i<=n;i++){ ans=(ans*a)%MOD;}return ans%MOD; }
vector<int>dx={0,0,1,-1};
vector<int>dy={1,-1,0,0};
class TreeAncestor {
public:
vector<vector<int>>up;
int LOG;
TreeAncestor(int n, vector<int>& parent) {
LOG = ceil(log2(n));
up.resize(n+1,vector<int>(LOG+1,-1));
for(int i=0;i<=n;i++)
{
up[i][0]=parent[i];
}
for(int j=1;j<=LOG;j++)
{
for(int i=0;i<=n;i++)
{
if(up[i][j-1]!=-1)
up[i][j] = up[up[i][j-1]][j-1];
else
up[i][j]=-1;
}
}
}
int getKthAncestor(int node, int k) {
if(k==1)
return up[node][0];
int ans=node;
for(int j=0;j<=LOG;j++) //O(log(N))
{
if(k&(1<<j))
{
ans=up[ans][j];
if(ans==-1)
break;
k-=(1<<j);
}
}
return ans;
}
};
void solve()
{
int n,q;
cin>>n>>q;
vector<int>parent(n+1);
for(int i=1;i<=n;i++)
{
int u;
cin>>u;
parent[i]=u;
}
TreeAncestor ob(n,parent);
for(int i=0;i<q;i++)
{
int node,k;
cin>>node>>k;
cout<<ob.getKthAncestor(node,k)<<nline;
}
}
int main()
{
flash
auto start1 = high_resolution_clock::now();
// test
solve();
auto stop1 = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop1 - start1);
cerr << "Time in miliseconds: " << duration.count() / 1000 << endl;
return 0;
}
The problem probably is the fact that you set
LOG
asceil(log2(n))
, although in the problem description,k <= 10^9
holds true, so your code can only jumpn
steps (instead ofk
).