Official Analysis (C++)

Explanation

Because $n \cdot m$ is reasonably small, we can construct a graph where we have an edge $a \rightarrow b$ if we start at port $a$ and end at port $b$ after going through the entire sequence of directions.

This new graph that we make remains a functional graph. Thus, our problem can be distilled into a slightly easier problem.

Given a functional graph, what is our final destination after $k$ moves if we start at node $1$?

To solve this problem, we can consider the following:

• If $k < n$, we can directly simulate each of our movements
• If $k \geq n$, we will end up in a cycle and repeat the same set of moves within it

In a cycle, the number of moves we need to make can be reduced by taking the remainder of the remaining steps modulo the cycle length. Thus, once we simulate enough moves to find a cycle, we can modulo the remaining moves by our cycle size and simulate the final moves.

Alternatively, you can use binary lifting, which is a little easier to implement but requires more advanced knowledge.

Implementation

Time Complexity: $\mathcal{O}(NM)$

Copy
#include <bits/stdc++.h>

using ll = long long;

int main() {
	std::ifstream read("cruise.in");

	int n, m, k;
	read >> n >> m >> k;
	std::vector<std::array<int, 2>> adj(n);

Copy
import java.io.*;
import java.util.*;

public class Cruise {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("cruise.in"));
		PrintWriter pw = new PrintWriter(new FileWriter("cruise.out"));

		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());

Copy
with open("cruise.in") as read:
	n, m, k = map(int, read.readline().split())
	adj = []
	for _ in range(n):
		l, r = map(int, read.readline().split())
		adj.append((l - 1, r - 1))

	moves = [1 if c == "R" else 0 for c in read.readline().split()]

next = [0] * n