Hello guys , I am having trouble solving this problem

You can read problem statement here also.

**Statement**

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

Thanks in advance :)

# | User | Rating |
---|---|---|

1 | tourist | 3565 |

2 | Benq | 3540 |

3 | Petr | 3519 |

4 | maroonrk | 3503 |

5 | jiangly | 3391 |

6 | ecnerwala | 3363 |

7 | Radewoosh | 3349 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 199 |

2 | Errichto | 196 |

3 | rng_58 | 194 |

4 | SecondThread | 186 |

4 | awoo | 186 |

6 | Um_nik | 182 |

7 | vovuh | 178 |

8 | Ashishgup | 176 |

9 | -is-this-fft- | 173 |

9 | antontrygubO_o | 173 |

Hello guys , I am having trouble solving this problem

You can read problem statement here also.

```
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.

Thanks in advance :)

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/04/2021 00:48:12 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Hey this is a classic Binary Lifting problem.

my own explanation for me

See if you can understand it and try the problem on ur own. Cheers

Hey bro , Here is what I had tried.

Detect all cycles and keep track of all cycles where each node in cycle is given node no.

then for node x in query , if x is already part of some cycle then it's very easy to ans. the kth node.

but for case where node isn't part of any cycle , I tried binary lifting on inverted tree (in which edge causing cycles are erased.) FOR THIS CASE , I am unable to code.

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.

SpoilerThanks bro , will try it :)

I was thinking on exactly same line. Though a pure binary lifting approach works.