ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1367. Top Secret

Test 2 Incorrect!
Posted by svr 4 Dec 2006 00:48
My program solves all testes on forum
but has WA2.
After some experiments I established that test 2 has
form : xx+xx
       x#|#x
where symbols x are not important
It is obvious that secrets # mutually unreacheable
But experiments say that test has it's answer 11
                                              11
Re: Test 2 Incorrect!
Posted by svr 17 Dec 2007 15:55
Reading ЧАВО helped. Was mistake of input.
But problem has appeared rather difficult.
Approach with Dfs from each # leads to TLE.
It is necessary take to acount topology.
Field consists of some lakes closed by + and #.
We should start Dfs from inside of these lakes and
#-s found this time on boundary are mutually achievable.
AC!.
P.S. It helpfull to make relation of approachibility having
transitiveness property to be equivalence. It can be made
by dividing one big cell in 4 smaller ones and moving
along them.

Edited by author 20.12.2007 07:56