Hi Everyone,

Yesterday I made a post about getting a TLE on Codeforces round #788, problem B. Today I'm making another post, about getting a TLE on Codeforces round #788, problem C :). Once again, I have what I think is a nlog(n) solution, and while it's able to pass the first two pre-tests, it doesn't solve the third in a short enough period of time. I posted my solution below along with a short description of how it works, and I would highly appreciate any feedback on what I did wrong and how I can improve.

Thank you.

Solution: https://codeforces.com/contest/1670/submission/156244281

Explanation:

1. Read the input into three vectors, "a", "b", and "c"

2. Create an adjacency list ("graph") between the elements of "a" and "b"

3. While doing so, mark any elements of "c" with values other than 0 as "bad" in hash_map

4. Count the # of cycles in the "graph" using DFS and a stack; don't count cycles that include "bad" nodes

5. Iteratively calculate 2^(# of cycles) and use modular arithmetic to guard against overflow

I think the primary issue with my code is inside the DFS, but I don't know why because I think that by marking visited nodes, the complexity shouldn't exceed nlog(n).