Ghost0fSparta's blog

By Ghost0fSparta, history, 6 years ago, In English

Hello CF, I have been recently trying to solve 427C. As per the editorial I have found all the strong connected components and then have found the minimum cost for each SCC component. Also I have found the number of junctions having the minimum value. But I am getting wrong answer for test case 71. My solution is here. I can't figure out my mistake can anybody help?

Let me jot down which function is doing what in my code
1) dfs_visit : Used for applying dfs on the graph provided and obtain the sequence of nodes according to their ending time which is stored in stack named seq.
2) scc_comp : Used to get the different SCCs for the reverse graph t_v which will be stored in scc.


The second issue is why are these two submissions giving different answers on Test case 71 Solution1 and Solution2.
Any optimization suggestions are also welcomed.
Thanks:)

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

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

Auto comment: topic has been updated by Ghost0fSparta (previous revision, new revision, compare).