### Peace_789's blog

By Peace_789, history, 9 months ago,

Hello guys , I am having trouble solving this problem

You can read problem statement here also.

Statement
You are playing a game consisting of n planets. Each planet has a teleporter to another planet (or the planet itself).

Your task is to process q queries of the form: when you begin on planet x and travel through k teleporters, which planet will you reach?

n , q can be upto 2.10^5.
k can be upto 10^9.


So , any hint to solve this problem will be grateful.

•  » » » 9 months ago, # ^ |   0 Initially, I tried the cycle approach which let to TLE for me. But if you notice it clearly its plain binary Lifting. Precompute jumps for each node. and then in query node walk or jump in binary value of k. You will get the answer. Spoilerint walk(int i,int k,vector& dp) { for (int d = 0; d <= D;++d) { if(k &(1<> i >> k; cout << walk(i, k, dp) << '\n'; }