P4232 Hide-and-Seek Beyond the Unconscious

(5) A Conversation from Heart to Heart. Snow is still falling in the old capital. I don’t know how far I’ve walked; I’ve already gone far from the marketplace. Ahead, I can vaguely see a huge palace. Is that the Palace of the Earth Spirits? I suddenly feel nervous. Here lives the most fearsome satori youkai in the Old Hell. Komeiji Satori, who has the power to read minds. Humans, youkai, even vengeful spirits—standing before her is like being stripped bare, with no secrets at all. It’s also said that in battle she uses hypnosis to repeatedly stir up her opponent’s deepest fears, defeating them from within. Of course a youkai like that would be disliked. Still, this underground trip can’t end just because we’re about to meet someone scary. Knock, knock—three taps on the palace gate. “A visitor? How rare.” In front of me stands a girl wearing blue clothes and a pink skirt, with pink hair. On her chest hangs a large red eye, connected to her body by six tubes radiating from it. She looks very gentle—nothing like the terrifying stories I’d heard. “A human from the surface traveling underground? That’s really rare—you actually found this place.” “It seems you don’t have any other intention and just want to look around. Come in, then.” We step through the gate. Worthy of the “Palace,” it’s truly vast—checkered floors in peach-pink and black, windows adorned with patterns. Ahead is a broad staircase leading to the second floor, where it splits into left and right corridors. “Pretty, isn’t it? It’s spacious here; the pets love it.” I follow Satori into her office. We sit on the sofa and chat for a long time, though I speak very little. During the conversation, I learn that she has a younger sister, Komeiji Koishi. Not wanting to be disliked for reading minds, Koishi closed her satori eye. To guide her sister, Satori often plays with her, accompanied by their pets. In the Palace of the Earth Spirits, Satori, her sister, and their pets have lived a peaceful, warm life. “Since you’re here, play with us,” Satori invites us to join their game. What kind of games do underground youkai play? And so, I agree to join Satori and Koishi’s “unconscious hide-and-seek.” They call it “hide-and-seek,” but it’s actually very different from the usual game—more like tag. Satori and Koishi start in two different places; Satori wins if she tags Koishi. But why call it “hide-and-seek”? It turns out Koishi can act unconsciously—she can make people around her subconsciously ignore her presence. It’s like invisibility, but not exactly the same. What an interesting ability—maybe it’s because she closed her satori eye? We have a blast. Sometimes I accidentally brush Koishi’s hand and jump in surprise. After a while, the sisters get tired. Satori has work to handle and heads back. The pets seem unsatisfied and want to continue. “But down here in the Old Hell, besides the mistress’s sister Koishi, who else can manipulate the unconscious? Forget it, let’s just play ordinary tag,” Orin suggests. The pets quickly throw themselves into “hide-and-seek beyond the unconscious.” At some point, I feel a chill behind me. I turn around—it’s Koishi. We just stand there, watching the pets play. Though I don’t know why I can patiently watch for so long, even after hours we’re still standing there. Koishi seems to have some questions. After a brief exchange, I summarize them. (See Problem Description.) As expected, this problem is indeed hard for unconscious Koishi. I’m grateful to have such a pleasant chat with the sisters, so I’ll do my best to think this problem through. (For the continuation of the story, see the editorial. Next, please see T4.)

Problem summary. On a directed acyclic graph, A Rin and A Kong stand at time $0$ on nodes numbered $s_r$ and $s_k$, respectively. Both know each other’s initial positions and have full knowledge of the map. Starting from time $1$, at each time step both A Rin and A Kong may either stay put or move to an adjacent node along a directed edge. Their moves at each time step start simultaneously, and they cannot change direction mid-step. When A Rin is caught by A Kong, the game ends immediately. If A Kong never catches A Rin, then after time $t$ ends, neither can move anymore, and the game ends at time $t+1$. A Kong’s goal is to catch A Rin as quickly as possible (catching means being on the same node at the same time), while A Rin’s goal is to avoid being caught for as long as possible. Specifically, if a game lasts for $t_0$ time steps, A Rin’s score is $t_0$, and A Kong’s score is $-t_0$. Both aim to maximize their own (expected) scores. We assume that throughout the process A Rin and A Kong always know each other’s current positions. At time $t$, neither can tell where the other will choose to move at time $t+1$. Koishi wants to know: under optimal play by both sides, what is the expected ending time of the game?

The first line contains $5$ integers $n$, $m$, $s_r$, $s_k$, $t$, separated by spaces. Here, $n$ is the number of nodes and $m$ is the number of edges. The next $m$ lines each contain two integers $a$, $b$, indicating a directed edge from $a$ to $b$ (no multiple edges).

Output a real number, rounded to $3$ decimal places, which is the expected ending time of the game. Your answer must exactly match the standard answer to be accepted.

Sample explanation. Sample $1$: If A Rin always stays still, then A Kong cannot catch A Rin within the first $t$ units of time; the answer is $t+1$, i.e., ``` 11.000 ``` Constraints. This problem uses bundled testdata. - For $30\%$ of the data, $n \leqslant 3$. - For the remaining $70\%$ of the data, $n, t \leqslant 20$. Among these, the first $40\%$ and the last $30\%$ are bundled and tested separately. Tip: This problem mainly checks whether you can use the correct method to compute the answer; strict time limits on the algorithm are not the focus. by orangebird. Translated by ChatGPT 5