10672 - Marbles on a tree

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
kamrul
New poster
Posts: 9
Joined: Sat Aug 24, 2002 11:21 am
Location: Dhaka, Bangladesh

10672 - Marbles on a tree

Post by kamrul » Mon Jul 05, 2004 7:52 pm

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]
Last edited by kamrul on Tue Jul 06, 2004 8:48 pm, edited 1 time in total.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Jul 05, 2004 8:52 pm

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
New poster
Posts: 9
Joined: Sat Aug 24, 2002 11:21 am
Location: Dhaka, Bangladesh

Thanks:

Post by kamrul » Tue Jul 06, 2004 8:45 pm

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

a.elbashandy
New poster
Posts: 12
Joined: Fri Dec 23, 2011 6:23 pm

Re: 10672 - Marbles on a tree

Post by a.elbashandy » Sat Mar 23, 2013 5:05 am

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

Code: Select all

removed after accepted
Last edited by a.elbashandy on Sat Mar 23, 2013 1:07 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10672 - Marbles on a tree

Post by brianfry713 » Sat Mar 23, 2013 9:49 am

Check input and AC output for thousands of problems on uDebug!

a.elbashandy
New poster
Posts: 12
Joined: Fri Dec 23, 2011 6:23 pm

Re: 10672 - Marbles on a tree

Post by a.elbashandy » Sat Mar 23, 2013 1:07 pm

thanks brianfry713

kakaroto2
New poster
Posts: 2
Joined: Sat Dec 07, 2013 5:30 am

Re: 10672 - Marbles on a tree

Post by kakaroto2 » Sat Dec 07, 2013 5:35 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10672 - Marbles on a tree

Post by brianfry713 » Tue Dec 10, 2013 1:33 am

Input:

Code: Select all

4
1 2 1 2
2 1 1 3
3 1 1 4
4 0 0
AC output 3
Check input and AC output for thousands of problems on uDebug!

kakaroto2
New poster
Posts: 2
Joined: Sat Dec 07, 2013 5:30 am

Re: 10672 - Marbles on a tree

Post by kakaroto2 » Tue Dec 10, 2013 3:22 am

brianfry713 wrote: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!

Post Reply

Return to “Volume 106 (10600-10699)”