Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

PintinhoPreto's blog

Someone can give me a hit for problem IMPER in SPOJ?
By PintinhoPreto, history, 9 years ago, In English

I try it using a BFS. Starting in a node with degree 1, setting the node as visited and its neighbors, adding in the queue the neighbors of neighbors of node. But, i was received only wrong answer with this strategy :(

Link for the problem: http://www.spoj.com/problems/IMPER/

sorry for my bad english.

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

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Your approach will lead to WA, consider the following test case:

10

1 2 3 4 2 6 7 8 9

-1

What is the right answer?

To solve this problem you need to learn what is and how to calculate the diameter of a tree. I won't link any tutorial, since I don't know about any particularly good, but googling it should be enough.

This is the code I got Accepted with: Don't click me

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    oow, thank you so much for advice.

    After looking for the diameter of a tree, this problem look so easy xD

    Thanks very much :D

    → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I got Accepted in 2 OJ and there is one thing I can't understand:

Why does this case return 2 instead of 3?

7

1 2 1 4 1 6

Thanks!

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

One of the tags of this post is "need help" XD .

→ Reply