Timeismoney - BOI

Problems and Contests
#1

For this problem from BOI https://oj.uz/problem/view/balkan11_timeismoney from the MST section, can DSU be used instead of MST?

In particular, binary search on V, V >= time*money -> V/time >= money then dsu all the edges for which this is true. If the final graph is connected then V can be reached if not V cannot.

This solution seems oddly fast considering the constraint is M <= 10,000, so what is the mistake here?

Additionally, what is the intended solution with MST?

#2

Link the code for your approach? I don’t see why this would be correct at all.

#3

You are right it is not correct. For some reason I thought that if all the edges satisfies V/time >= money then the entire graph satisfies this property, but this is definitely not correct. What is the intended solution though?

#4

You can look it up. \quad

#5

http://boi2011.ro/resurse/tasks/timeismoney-sol.pdf

1 Like