Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

calmhandtitan's blog

By calmhandtitan, history, 5 years ago, In English,

Can someone please help tell me why I am getting WA for 131D - Subway or where my code goes wrong.

I get WA at test8 which is a very big test having 3000 nodes for which I am unable to debug.

Here's my submission. 11783845

My intended algorithm is as follows:

  1. First find all the vertices in the ring(cycle) using dfs().

  2. Then do DFS for each of the vertex in the ring to find the distance of each node from the ring. This is done by dfs2()

This algorithm is the same as mentioned in the editorial

Seeking some help. Thank you. :)

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Let me just tell you, How did i solve this problem.

  1. Actually the main task is to find out the only back edge in the graph. Since the constraints are low i have found by removing each edge once. Although, we can do this task in linear time as well by maintained visiting time of each vertex.

  2. Once you have found the back edge suppose (u,v) , remove that edge from the graph now realise that the graph is a tree which contains exactly one path from a node to every other node. find the path from u,v in this tree. Note that these are all those nodes which are going to be appeared in our one and only cycle. highlight these vertex with some random value ( i used 1 as this random value :P ). Now for all those vertices which are not highlighted do dis(x) = dis(parent) + 1 , subtract 1 from the final distances. I have coded this in the same way i described you can check my solution here.