Yes same thing I too wanted to ask

Yes, right. Due to long queue issues.

+1

As I see it:

1. gridx and gridy arrays are unnecessary, there's no point in storing them explicitly
2. solve() can be slightly optimized by making curval global (and x and y also, but it will make code a bit less readable). Also local variables can be inlined

I understand that these kinds of optimizations are not what you expect from Div.3 but the main expected solution doesn't use dfs at all, so it's not like we wanted to fail dfs explicitly, we just didnt' tune ML for any dfs to pass.

UPD1: (sorry, previous UPD wasn't true, fixed)

UPD: We just re-checked your solution in Polygon with double ML after making some modifications and it passed, so I guess we should've made the ML larger. Sorry about that :(

its the absolute value of what is left, not what is eaten

Maybe the authors wanted to SendThemToHell

I understood your point, yes. The fact that in the end this task was challenging not because of it's algorithmic difficulty but because of the memory limit is kinda frustrating, this was not how it was intended.

Well, I can't argue with the fact that this Div. 3 is not as well-adjusted as the previous one, sorry for that. We'll try to make the next one more pleasant to solve.

Yes most of the recursive solutions fail just because of MLE. But my main point is that there are so rare dfs solutions with heavy optimization to be able to pass, I did not mean that DFS is enough to past.

I think that the author make a miscalculation to use 256Mb instead of 512Mb and kill around atleast half of the solutions.

Yet some of my CM friend still find it very confusing to optimize further, some even spend an hour without being able to solve it.

First, why do I have that much downvotes :') ?!!

I'll try to explain my solution step by step. First notice that in the graph, each node has at most one child. So basically, any connected component has at most ONE CYCLE.

Indeed, let's assume you're currently constructing the connected component starting from node $$$1$$$. When we're at node $$$i$$$ we have two choices: we can either add an edge to node $$$i + 1$$$ (so the graph looks like a path and we don't have any cycle) or we can add an edge to some node $$$j$$$ such that $$$j < i$$$ and we'll create a cycle. Notice that after a cycle has been created, we can't add any more edge.

Now let's say we found the cycles. For a given cycle, the length of the longest path is the same for each node of the cycle (it's the size of the cycle).

So now we know that a functional graph looks like

......x

......|

......|
......v

x->x->x->CYCLE

(the . are used to align the edges. I'm sorry I couldn't do something clean. I'll try to send a drawing asap)

Imagine it as we link some sort of directed tree (where all the edges are directed toward the root) to a cycle.

About my code:

What you can do is store for each node:

1) if it has been visited

2) if we are visiting the node (this means the node is part of the path we are exploring right now)

3) the longest path starting from this node

In my code $$$ans[i][j] == 0$$$ if the node hasn't been visited, $$$ans[i][j] == -1$$$ is we're visiting the node, else it's the longest path starting from this node.

Now let's iterate over each node $$$u$$$. If the node hasn't been visited, let's start a walk in the graph (basically we explore the unique path starting from node $$$u$$$). We'll keep track of a vector of all the nodes in the path ($$$curCycle$$$ in my code) and we'll also remember the length of the path ($$$cnt$$$ in my code)

This is what I do in the first while loop.

Let's say the child of our current node is $$$v$$$. If it's the first time we see it then we move to $$$v$$$ and keep exploring (don't forget to update $$$curCycle$$$ and $$$cnt$$$). If we already computed an answer for node $$$v$$$, we simply increment $$$cnt$$$ by this answer and break. Now, if $$$v$$$ is already part of our path (in my code it's $$$ans[i][j] == -1$$$), it means we cycled. So we're going to look for the last occurence of $$$v$$$ in our array $$$curCycle$$$. All the nodes after this occurence are part of the cycle and their answer should be updated accordingly. Notice that as we cycled, we can't expand our path anymore.

Now we also need to update the answers of all the nodes in the path (nodes which are outside of the cycle). So we basically start again to walk from node $$$u$$$ and we set it's answer to $$$cnt$$$. Then when we move to the child of the current node, $$$cnt$$$ should decrease because the length of the path is reduced by $$$1$$$.

The time complexity is $$$O(N)$$$ where $$$N$$$ is the number of nodes (here $$$N = nm$$$). Indeed, we visit each node exactly once because after a node has been visited, it's answer is remembered and we'll never explore again it's path.

Essentially, finding cycles in a functional graph is the same as finding if there is a cycle in a directed graph (See CSES Round Trip)

The only difference is that:

1) As the graph is pretty simple we can use a while loop instead of a DFS

2) We're actually finding ALL the cycles of the graph because each connected component has at most one cycle

About the other part of the algorithm, imagine you "compress" the cycles into one big node with it's answer = the length of the cycle. We now have a DAG (and more specifically it's a kind of directed chain) so we can apply DP (here we have only one transition per node).

The while loops are just a more convenient/efficient way to implement the algorithm.

A few problems about functional graphs:

Usaco silver, Swapity Swapity Swap

Usaco silver, Dance Mooves

Usaco gold, Exercise (well this one is a bit less related but it's an interesting problem)

I hope my explanations were clear, if they weren't just ask me and I'll do my best to explain :)

wait, did you really compressed the graph using strongly connected components ?

U wrote opposite maybe
I believe he would have used tarzan as Kosaraju takes more memory . I too passed it in recursive way but I had to find cycles by simple DFS . And code is still on the edge for MLE .

But isn't Kosaraju also dfs?

Consider in example all red numbers bigger than n. Obviously output must be No.

100 millions operations is at the border of the time limit per cases

Observations are quite important in the world of competitive programming :) it's pretty valid advice from yasserkhan45: if you can't see the answer immediately, experiment with some test cases. As is pointed out, a single test case was enough to see what happens in general, and a small modification was required for an odd starting position.

lower_bound(all(v), x) — usd with vectors/arrays s.lower_bound(x) — used with sets/maps

You should read this — https://www.cplusplus.com/reference/set/set/lower_bound/ https://www.cplusplus.com/reference/algorithm/lower_bound/