Explanation

First, instead of trying to tackle the problem for arbitrary values of $k$, let's try calculating the number of steps it takes for each node to reach node $p$.

When at a fountain, we will only ever take the two most beautiful outgoing trails. Let's consider a graph, where we draw edges between states. Each state is represented as a pair $(u, f)$, where:

• $u$ is our current node
• $f$ represents whether we are taking the most beautiful trail

  • $f=0$ means we can take the most beautiful trail
  • $f=1$ means we can only take the second most beautiful trail

Now, we want to find the distance from every other state to $(p, 0)$. Finding the distances to $(p, 1)$ can be handled in a similar fashion.

We can use our graph traversal method of choice to traverse from $(p, 0)$ out to all of our other states. To handle this, we construct a reversed graph, and traverse out from $(p, 0)$ to other states. After calculating the distances, we know that the distance from any node $i$ to our state $(p, 0)$ is the distance from $(i, 0)$ to $(p, 0)$. We handle $(p, 1)$ similarly.

Alright, so now we know how to calculate the distance from every node to $p$. How do we handle large values of $k$?

Consider the fact that each state will directly map to another state, forming a successor graph. Thus, if we arrive at $(p, 0)$ or $(p, 1)$ at any point, one of the following must happen:

• We arrive at $p$, and end up in a cycle where $p$ is not present
• We arrive at $(p, f)$, and cycle back to $(p, f)$
• We arrive at $(p, f)$, encounter $(p, 1-f)$, and loop back to $(p, f)$

Say our state $(p, f)$ falls under the second scenario, where it ends up in a cycle of length $n$. Then, for a node $i$ to be able to reach $(p, f)$ after $k$ trails, the following must be true for some non-negative integer $c$:

Scenarios 1 and 3 can be handled in a similar fashion. For scenario 3, we have to store the time that we visit the state $(p, 1 - f)$ in our cycle.

With this, we can solve each query in $\mathcal{O}(N)$ by checking each node and seeing if it ends up at $p$, using the three cases outlined above.

Implementation

Time Complexity: $\mathcal{O}(M + NQ)$

Copy
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using ll = long long;

constexpr int INF = 1e9;

void count_routes(int n, int m, int p, int r[][2], int q, int g[]) {
	std::vector<std::vector<std::array<int, 2>>> adj(n);