Could anyone who solved it share the idea?

My solution was: iterate over all vertices i. Fix each i start bfs, so you get a tree (rooted in i). Find it's diameter (from the farthest node v from root i start another BFS and find the farthest node u from v. The distance from u to v would be the diameter).

Across all the diameters find the minimum, that would be the answer.

This solution got WA 8. After random_shuffle() on adjacency lists I've got WA 17.

Now repeat this solution 100 times and you get AC.

So my question is, what is the solution?

1. Find shortest paths from all vertices with Floyd-Warshall or BFSes
2. Brute force all possible tree centers. Note, that a diameter center can be either a vertex or an edge.

Basically, my solution is exactly yours while I believe you've forgotten to check edges that can form a center.

My solution is completely deterministic.

Edited by author 07.11.2018 17:03

Edited by author 07.11.2018 17:03

I just tried all vertices and all edges (meaning pushing both neighbors in priority before BFS starts), then checked tree diameter across all vertices, not just to these roots (there is O(N) algo for that). I used no Floyd-Warshall for candidates, just tried all pairs v1 <= v2, besides I am not sure Floyd will help here because original graph diameter can be shorter than that of resulting tree (e.g. see WA17 topic).