12506 - Shortest Names

[sdipu]

I am getting WA in this problem. I am debugging my code for hours, but can't find any mistake in my code. Please help.

My idea is as follows-
I used Trie Tree to store the names. Then I used DFS to find out the total length.

Suppose I am given following names-

Code: Select all

aac 
aad
ace

So my tree will look like this-

Code: Select all

          [:3] 
            |
         [a:3]
        /      \
     [a:2]    [c:1]
    /     \          \
  [c:1]  [d:1]    [e:1]

Here, every node follows this format [character : number of names it occurs]. 

Now I find nodes with number of names == 1. And add the distance of this node from root to the total length.
So total length will be = 3 + 3 + 2 = 8

Is my approach wrong or am I making any silly mistake here?

[lighted]

You can post your code

[sdipu]

Here is my code

Code: Select all

code removed ;)

[lighted]

invalid input removed

[sdipu]

Problem description says-

It is guaranteed that no name is a prefix of another name (as a result, no two names can be equal).

As "a" is a prefix of "aaaaa", doesn't that make above input-ouputs incorrect? Am I missing something?

[lighted]

Yes you are right, i deleted invalid input. I checked your code for many input and it passed them all.

I don't know why it gives WA when you submit it with C++ 4.8.2. But it gives accepted when you submit your code with C++11 4.8.2.

[sdipu]

Thanks a lot for your help lighted.

I worked with this problem for hours but found nothing and never thought about submitting it in C++ 11. Thanks again for your time.