Run shortest path algorithm.

Change the direction of all edges.

Run shortest path algorithm.

It is actually possible to build all sparse trees simultaneously using small-to-large, but the time complexity is worse. The intended solution uses an algorithm that runs in $$$O(|S| \log N)$$$ for each set $$$S$$$. The algorithm is as follows:

1. Sort the vertices in $$$S$$$ based on their euler tour traversal order.
2. All extra vertices in the sparse tree can found as the $$$\text{LCA}$$$ of every pair of vertices in $$$S$$$ that are adjacent in the sorted order.
3. Once all required vertices are found, we can find the edges by iterating the vertices (including the extra ones) in euler tour traversal order and maintaining a stack.

You can optimise it further to make the total time complexity $$$O(N(\log N + \log \max(A)))$$$. But the time limit is not that tight that even the small-to-large solution is able to pass.

It probably just runs that fast. The hot path only includes an add, a compare, and a conditional jump, which is < 3 cycles with branch prediction. Computers run at a few GHZ, so 500ms sounds right.

The $$$10^8$$$ things/second heuristic is just a heuristic for usualish groups of operations, you can do better if u have a fast loop body (especially if the compiler avx-ifies, which might be happening here).

To see exactly what is happening u can try putting it in https://godbolt.org/ with the correct compiler version/flags.

we can write (b^2-a^2) as(b-a)*(b+a) // proof for 1 can not be expressed in terms of b^2-a^2 so the min positive value of a we can take is 1 and for b its 2 as (b>a) as stated in the problem so, (b-a)=1; (b+a)=3; and their multiplication would give us 3 as the min value which can be expressed in terms of b^2-a^2; and one more conclusion can be drawn is that after three all odd numbers can be expressed in the form of b^2-a^2 (because we can express every odd number (lets say a)as 1*a; and a can always be represented as a sum of 2 consecutive numbers which are always odd **** lest take a=4 ,b=5; b-a=1; b+a=9; 9*1=9; that is odd)

// proof for 4 cannot be expressed in terms of b^2-a^2 to make equation even we have to make (b-a) even first so in order to make that even min value of a we can take is 1 and for b is 3 so, (b-a)=2; (b+a)=4; and their multiplication will give us 8 that is the minimum even value we can achieve and from here we can draw one more conclusion that all the even values will be multiples of 4 as no matter what we take values of a and b whenever (b-a) is even (b+a) would also be even (because to make the diffrence of 2 numbers even their parity should be same and if we add same parity numbers then result is even) so that would make the result divisble by 4

I could come up with this result by building a sequence,

I added the difference between b^2 and a^2 in the sequence as follows:

4 — 1, 9 — 4, 16 — 9, 9 — 1, 25 — 16 ..

by listing the "difference between squares" in nondecreasing order,

I got the sequence:

3, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, 23, 24, 25, ,27, 28, 29, 31..

I noticed that the first number "3" doesn't follow the pattern, so I assumed it was a special case,

but the remaining numbers follow a consistent pattern that I came to figure out as:

"3 + 4 * (N // 3) + N % 3"

You need to make sure que is a heap before running dijkstra for the second time. 173757547