Al.Cash's blog

Graph connectivity problem: efficient solution?
By Al.Cash, history, 9 years ago, In English

I solved the following problem http://acm.timus.ru/problem.aspx?space=1&num=2055 using approach described here http://codeforces.me/blog/entry/15296 + binary search, but my solution barely fits in Time Limit.

There are solutions 10 times faster than mine and I'm very interested what approach could they be using?

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

There is a solution that somehow is much faster than : sqrt-decomposition solution (my implementation of does not pass TL, other solution passes in about 0.5 sec).

→ Reply