https://cses.fi/problemset/task/1160
can someone please help me in this question?
I am not getting any ideas as to how i should proceed...
Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 134 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 06.11.2026 17:48:56 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
Each node has only one outgoing edge, so we have no options (like choosing where to go next); we merely follow the (only) edge.
This kind of directed graph is also called a functional graph. One of the most important properties of functional graphs is that each component (here, a component is that of an undirected sense) has a single cycle, and possibly a few trees (that are directed, where each node points to the parent and the root is on the cycle) attached to them.
If you're not sure, I recommend that you take a few random examples (random $t_i$s, in this problem) and draw the graph. Say,
n=10, t[1..10] = {2, 3, 1, 2, 2, 4, 4, 9, 8, 9}. The key is to see that, starting from any vertices, you are going to eventually reach the cycle (i.e. arrive at a node that is on the cycle) of the component.Say we're processing a query from
atob. First, if these two nodes belong to different components, it is easy to see that we'll never be able to reachbfroma.Now, assume they are on the same component. If
bis on the cycle of the component, you are going to reach it fromain some number of steps. It would consist of two stages: first, you reach the cycle (ifais not on the cycle). Second, you reachb. Figuring out how long each stage takes is left to you. Note that the length of the first stage is the same regardless ofb.If
bis not on the cycle, then it belongs to a tree hanging around the cycle. Forato reachbthen,ashould be a descendant ofb(or equivalently,bis an ancestor ofa). How to check that? Again, I'd like you to work on that.If anything's not clear or you have more questions, feel free to ask.
thanks for the crystal clear explanation i absolutely understood everything!
implementing this is definitely going to be a little tough but ill try then get back
Edit: https://codeforces.me/blog/entry/79518 this is an attempt to writing the editorial
for the graph section of cses but its incomplete... if u have time can u finish this off? it
would be of great help!!
Shouldn't $$$a$$$ be an ancestor of $$$b$$$ in case $$$b$$$ is not on the cycle ?
Like for Example in this graph. Link To Image
i dont get your quesn..can u explain further? e.g. a = 2 b = 1 a is not the ancestor of b though b isnt on the cycle
I mean to reach from a to b. In the graph I gave, shouldn't a be an ancestor of b.
The sentence "$$$a$$$ is an ancestor of $$$b$$$." means that $$$a$$$ is on the parent side (like parent, grandparent, grand-grandparent, ...), up in the hierarchy and closer to the cycle. Is this what you meant?
Yes, Meaning $$$depth(a) \lt depth(b)$$$ Or More Formally,
$$$dt(a) \lt dt(b) \; and \; ft(a) \gt ft(b)$$$ Where $$$dt$$$ and $$$ft$$$ are discovery times and finish times respectively.
Namnamseo i tried but i am still getting WA on only 1 testcase but its very huge so i cannot understand
approach: i first assign depth to nodes by randomly assigning any one node of the cycle as 1 then doing depth[node] = depth[child[node]] + 1
then by building a binary lifting table i jump
this will work because as you pointed out in functional graph, there is only one path i.e. a length 4 path from some node x has only one possible ending node
now depending on difference of depth of nodes i jump and if i reach the node i print the depth difference else print -1
special case here is that if two nodes are of the same cycle then depth[a] < depth[b] might be possible
in that case , i print the length of the cycle — depth[b] + depth[a]
my code: https://ideone.com/pi9Cx3
any help will be appreciated thanks!!!
Great job! I'm impressed by your implementation, especially using depths to make matters simple.
One thing (I think) you've missed is that, the case of
dep[a]>dep[b]can do occur, even whenais not on the cycle. Specifically, what ifahas a small depth,bis beyond thedep=1point and the cycle size is large enough?YES ABSOLUTELY!! my final code that got accepted...
https://ideone.com/hKsG5K
i did the same thing as above but i added a trick — depth of a node in a cycle can be either the depth or if b is part of a cycle its depth can be depth[b] — cyclelength
thanks a lot!! i could never have done this question without you!!
Glad to hear that! Well done.
nvm i understood