(LLM-written response, always verify)

You can improve the usual DP by one n.

Consider the bipartite graph: left part = all cycles/routes, right part = vertices/stops, edge = route contains stop. One schedule row is a matching. So by Konig’s theorem for bipartite graphs, the answer is just the maximum degree:

max(longest cycle length, max_v number of simple cycles containing v)

Now count cycles with subset DP. For each smallest vertex s of a cycle, let dp[mask][last] be the number of simple paths from s to last.

Use only masks containing s and no vertex < s. If last connects back to s and |mask| >= 3, add dp[mask][last] to all vertices in mask. Each undirected cycle is counted twice, so divide by 2.

This gives O(n^2 * 2^n) time and O(n * 2^n) memory.

Edited by author 29.06.2026 14:21

sscanf("%d.%d", &a, &b)

Eleven empty lines

Maybe in year or two.

Forum is not for instant answers. It is rather knowledge base. There is no answer to your question in the base yet.

Maybe answer will appear but 99% that _you_ will first find the bug and post yourself test for the bug here than someone get wa29 and post test for it.

I tried it this way - i.e. propagate all with 1, then with sqrt(2) from current frontier to upcoming edges, but here is the thing:

distance 0 leads to 1 and 1.4 (all still fine and sorted)
distance 1 leads to 2 and 2.4 (all still fine and sorted)
distance 1.4 leads to 2.4 and 2.8 (all still fine and sorted)
distance 2 leads to 3 and 3.4 (all still fine and sorted)
distance 2.4 leads to 3.4 and 3.8 (all still fine and sorted)
distance 2.8 leads to 3.0 and 4.2 (WOOPS! - 3.0 will be placed after 3.4 and 3.8)

so I did  Dijkstra, but with super-optimization. Instead keeping all nodes in a heap, I kept a heap on unique distances (as of A+B*sqrt(2)), and for each such distance I kept bidirectional list of nodes with that distance as currently reached. This makes edge relaxation O(1) - remove from current list, and add to another. So it's O(N*M)+O(K*log(K)) where K is number of different distances, and there are not so much on the way. Although I checked with asserts, there are cases when you have like 8 or even 16 upcoming frontiers even during first 6 tests. Relexations start happening with test 5, but only test 7 leads to WA on them with too greedy approach.

Edited by author 24.06.2026 11:43

Because you can't get three trips here no matter the ordering