tcknSS's blog

By tcknSS, history, 4 weeks ago, In English,
Hello everyone !
I've just seen this 2 problem : B/Travel & C/Lilypads in HKI Mock NOI 2015 (seems like it's a Mock contest of Singaporean coders) but I couldn't find out any fast enough solutions for them.
Here are the links to the problems :
B :
C :
In problem B, I tried to implement a lot of solutions (e.g. remove each edge and find the shortest path between two vertices that it connects, ...) but that is just enough to pass the first 4 subtasks (which helps me gain <= 50% of the points).
In problem C, I think it's a kind of Dynamic Connectivity problem. I've heard about some data structures that can solve this problem. If my memory is correct, link-cut tree can solve it but many people say that it's really hard to code it in a contest. 
Now I'm really stuck and trying to find a help which could leads me to a bright future. Can you please tell me how can I solve these problems. Thank you !
  • Vote: I like it
  • 0
  • Vote: I do not like it