CCC 2020 - J5 / S2: Escape Room

Define grid[r][c] to be the integer in the $r$-th row of the $c$-th column of the input grid. Let done[x]=true if we can reach any cell $(r,c)$ such that $r\cdot c=x$ and false otherwise. If done[x] is true, then we also know that done[grid[r][c]] is true for all cells $(r,c)$ such that $r\cdot c=x$.

So we essentially have a directed graph with vertices $1\ldots 10^6$ where there exists a directed edge from x to grid[r][c] whenever $r\cdot c=x$. We want to test whether there exists a path from $1$ to $N\cdot M$ in this graph.

Thus, we can simply start DFSing from vertex $1$ and mark all the vertices that we visit in the boolean array done. If we set done[N*M]=true, then a path exists, and we can terminate after printing "yes." Note that in the code below, todo[x] denotes the adjacency list of x.

#include <bits/stdc++.h>

using namespace std;

int M, N;
vector<int> todo[1000005];
bool done[1000005];

void dfs(int x) {
	if (done[x]) {