madlad's blog

By madlad, history, 22 months ago, In English

I was trying to solve this problem: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1402

I used simple BFS to solve the problem but I am getting WA.

My code: https://ideone.com/ljuSH7

There are no test cases for this on uDebug too and I am struggling to find out where I went wrong.

I just calculated the min time = time needed to complete all the jobs that need to be completed before 'x' and the max time = Total time — the time needed to complete all the jobs that require 'x' to be completed first and then I just calculated the difference of it.

Can someone help me?

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

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    madlad did you manage to solve it? or anyone else?

    I used code for topological sort. Once by ejecting the node asap and then by delaying it as long as possible. Still getting WA. Here's my code: https://ideone.com/VPbOmf

    Any help would be highly appreciated!

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your idea is correct, there must be something wrong in implementation.

I am sharing link to my code. Here I have used two graphs, one for min_time and one for max_time.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if you don't mind can you explain your solution a bit more or explain what is required in the problem as i cant just understand it thanks in advance

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone solved this problem.Please post if any corer cases?

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Done :) Many negative answers :(

»
5 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

there are Test_cases available at uDebug. These test_cases are large, so it takes 5-8 seconds to load. My Code, I used this logic : sum1 = sum of all verticles, which must be finished before the given task;
sum2 = sum of all verticles, except the ones which needs our given task to be finished...And the answer is sum2-sum1.