Analysis: Luxury River Cruise by Nathan Pinsker

We will always apply our sequence of M instructions as a set. We can therefore calculate, for each port of our graph, where we arrive after applying instructions when starting at that port. This takes O(N*M) time. Once we have done this, we obtain a graph of directed edges between vertices representing ports, where an edge from port A to port B means a sequence of M instructions starting at port A leads to port B. This graph is one where each vertex has exactly one outgoing edge. It can be shown that the graph is structured as one or more components, each of which is a single cycle with several trees feeding into it. We are starting at some vertex in this graph, meaning that we only care about the connected component that the vertex is in.

If K is very large, we cannot traverse K edges to find out which port we will arrive at last. However, we can note that we will traverse the cycle in K's component many times. Let C be the length of our cycle. Therefore, we can just take K modulo C to reduce the number of edges we must traverse to a reasonable number. More precisely, we know that we will be in our cycle after traversing N edges, so if K > N, we know that traversing N + (K - N) modulo C edges is equivalent to traversing K edges. This is a reasonable number (at most 2*N) so we can compute this directly. The total runtime is O(N*M) time due to our construction of the graph at the beginning, which is easily fast enough.

Mark Gordon's code is below: 
/*
LANG: C++
*/
#include 
#include 
#include 

using namespace std;

#define MAXN 1000

int N, M;
long long K;
string S;
int L[MAXN];
int R[MAXN];

pair get_next(pair v) {
  return make_pair((S[v.second] == 'L' ? L : R)[v.first], (v.second + 1) % M);
}

int main() {
  freopen("cruise.in", "r", stdin); 
  freopen("cruise.out", "w", stdout);

  cin >> N >> M >> K;
  K *= M;
  for(int i = 0; i < N; i++) {
    cin >> L[i] >> R[i];
    L[i]--; R[i]--;
  }
  for(int i = 0; i < M; i++) {
    string s; cin >> s;
    S += s;
  }
  
  pair s0(0, 0);
  pair s1(0, 0);
  for(; K > 0; K--) {
    s0 = get_next(s0);
    s1 = get_next(get_next(s1));
    if(s0 == s1) {
      K--;
      break;
    }
  }
  if(K) {
    int rho = 1;
    for(s0 = get_next(s0); s0 != s1; rho++) {
      s0 = get_next(s0);
    }
    K %= rho;
  }
  for(; K > 0; K--) {
    s0 = get_next(s0);
  }
  cout << s0.first + 1 << endl;
  return 0;
}