10672 - Marbles on a tree

[kamrul]

I used recursion to solve this problem. and it gives the solution to the test cases given in the problem perfectly. But i m getting WA .
can anyone tell me what's wrong with my code.
Code:
[cpp]
Code has been removed.
[/cpp]

[Adrian Kuegel]

It seems that you assume that the root of the tree is always the node numbered 1, but that is wrong.
Your program fails on inputs where the root is not node 1,
like
2
1 0 0
2 2 1 1
0

Output should be 1.

[kamrul]

Oh. That was a bad mistake.
Now i got AC
Thanks for your help.

[a.elbashandy]

I'm getting WA, are there any critical test cases to test my code ?

Code: Select all

removed after accepted

[brianfry713]

http://www.algorithmist.com/index.php/UVa_10672

[a.elbashandy]

thanks brianfry713

[kakaroto2]

Here's my code.

Code: Select all

#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;

int main()
{
    int n;
    while( ~scanf("%d",&n)&&n )
    {
        int father,value,nkid;
        int iskid[10005]={0};
        int marble[10005]={0};
        vector<vector<int> >tree;
        tree.clear() , tree.resize(n);
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d",&father,&value,&nkid);
            marble[father-1]=value-1;
            int kid;
            for(int j=0;j<nkid;j++)
            {
                scanf("%d",&kid);
                tree[father-1].push_back(kid-1);
                iskid[kid-1]=1;
            }
        }
        int root=-1;
        for(int i=0;i<n;i++)
        {
            if( !iskid[i] )
            {
                root=i;
                break;
            }
        }
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            if(i==root)
                continue;
            int marbles=marble[i];
            int k=tree[i].size();
            for(int j=0;j<k;j++)
            {
                marbles+=marble[ tree[i][j] ];
            }
            cnt+=abs(marbles);
        }
        printf("%d\n",cnt);
    }
    return 0;
}

I don't use DFS,but I realize that 1 isn't neccessarily the root.
So I search for it,and pass several special inputs,but still got a'WA'.
HELP ME!!!

[brianfry713]

Input:

Code: Select all

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

AC output 3

[kakaroto2]

Input:

Code: Select all

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

AC output 3

thx!
I've already figure out that my algo will fail when the depth of the tree is more than 3.
So I compromise to Dfs,and then Ac in 25ms.
Thanks again for brianfry713's test sample!