What is the proper solution? (Got AC with a hack, my solution inside)

Posted by

araifr 7 Nov 2018 13:19

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?

Re: What is the proper solution? (Got AC with a hack, my solution inside)

Posted by

decay 7 Nov 2018 16:59

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*