devil_60's blog

By devil_60, history, 6 years ago, In English

I am unable to get what is wrong with my logic. The question link is here: http://codeforces.com/contest/580/problem/C

My solution is this: https://pastebin.com/DNgpJGnW

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

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

Your code gives WA as it does not stop on the path to one of the leaf nodes even after having greater than m consecutive vertices with cats,it refreshes the value of variable val to 0 on the same path and counts those leaf nodes as well.Example test case would be:
Input :
4 1
1 1 0 0
1 2
2 3
3 4
Output :
0 (but your code gives output as 1)
You can use a return statement to return from the path where greater than m consecutive vertices have cats.

Here is a link to my submission:39347359

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

    Hey I couldn't understand why the answer is 2 in the second example shown in that problem.

    The way I see it he can only go restaurant at vertex 5 through the path 1 -> 2 -> 5 which has only 1 cat. The path to 4, 6, 7 have 2 cats which exceeds the threshold.

    Here is my code — https://pastebin.com/ws0frPRy

    Thanks for your time !

    Best Regards, Srivatsa

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

      The question asks for consecutive vertices so the path to 4 is fine since the vertices with cats are not next to each other on the path.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    In the sample example 1

    4 1
    1 1 0 0
    1 2
    1 3
    1 4
    

    we can't go to 2 but we can go to 3 and 4 why the ans is 2 and 2nd test

    7 1
    1 0 1 1 0 0 0
    1 2
    1 3
    2 4
    2 5
    3 6
    3 
    

    we can't go to 4 and 6 and 7 why ans is 2 may be i understood question wrong please help me