Page 4 of 5

### 615 WA

Posted: Fri Oct 06, 2006 9:06 am
Anyone can tell me what's wrong in my code?I test every input here,and all get right output.But I get the wrong answer.

Code: Select all

``````//Is It A Tree?
#include <iostream>
using namespace std;

int main()
{
int* fr;
bool* ex;
int f=0;
int t=0;
int root=0;
int ca=0;
int num=0;
int st=0;
int now=0;
const int max=1000;
bool istree=true;
cin>>f;
cin>>t;
while(f!=-1||t!=-1)
{
fr=new int[max];
ex=new bool[max];
istree=true;
root=0;
num=0;
ca++;
while(f!=0||t!=0)
{
num++;
if(fr[t]>0||f==t)
{
istree=false;
break;
}
fr[t]=f;
ex[f]=true;
ex[t]=true;
cin>>f;
cin>>t;
}
if(istree==true)
{
for(int i=0;i<max;i++)
{
if(ex[i]==true&&fr[i]<=0)
{
if(root!=0)
{
istree=false;
break;
}
else
root=i;
}
st=i;
now=i;
while(fr[now]>0)
{
if(fr[now]==st)
{
istree=false;
break;
}
now=fr[now];
}
}
}
if(istree&&root>0&&num!=0)
cout<<"Case "
<<ca
<<" is a tree."
<<endl;
else
{
while(f!=0||t!=0)
{
cin>>f;
cin>>t;
}
cout<<"Case "
<<ca
<<" is not a tree."
<<endl;
}
delete [] fr;
delete [] ex;
fr=0;
ex=0;
cin>>f;
cin>>t;
}
return 0;
}
``````

### Re: Oh gosh-! I can`t solve this problem- (615)

Posted: Fri Apr 04, 2008 2:44 pm
try this
input:

Code: Select all

``````6 8  5 3  5 2  6 4
5 6  0 0

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

3 8  6 8  6 4
5 3  5 6  5 2  0 0

1 2 1 3 2 4 2 5 2 6 2 7 3 8 8 9 9 10 10 11 11 12 12 13 0 0

1 2 0 0

1 2 2 1 0 0

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

100008 200008 10008 30000 0 0
-1 -1
``````

Code: Select all

``````output:
Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.
Case 4 is a tree.
Case 5 is a tree.
Case 6 is not a tree.
Case 7 is not a tree.
Case 9 is not a tree.
Case 10 is not a tree.
``````
hope it helps

### Re: 615 - Is It A Tree?

Posted: Thu Jul 31, 2008 7:02 am
i think you have given one extra output.
there are nine cases in your input. ### Re: Some sample I/O on problem 615

Posted: Fri Dec 26, 2008 6:39 pm
Sedefcho wrote:Although at first sight it seems quite trivial, the problem 615
finally happens to be quite tricky and hard to get ACC on.
At least that's my feeling about it.

I got ACC on July 12, 2005 ( I mention this as I read in other
threads that there has been an old judge on that problem / 615 / ).

Here is some test data for anyone who might be
still working on that problem:

INPUT

Code: Select all

``````
0 0

99006 700002 700002 880002  880002 1000001 1000001 1234567890
[color=#BF0000]1234567890[/color] 22  0 0

-1 -1 ``````

You can safely assume that node number is less than 1000002.

### Re: 615 - Is It A Tree?

Posted: Sun Jan 10, 2010 5:18 pm
//code removed after AC

why am i getting WA...

### 615 is it a tree??

Posted: Mon Jan 11, 2010 8:21 am
//code removed after AC

why am i getting WA...

### Re: 615 - Is It A Tree?

Posted: Mon Jan 11, 2010 4:03 pm
See previous posts..
Your code fails on turcse143's test cases..

### Re: 615 - Is It A Tree?

Posted: Tue Jan 12, 2010 4:25 pm
yes corrected it ...got AC..thanks..

### Re: 615 - Is It A Tree?

Posted: Fri Aug 27, 2010 3:41 pm
Guys,this problem is making me crazy. I cant think even on other things. I have gone through all the post related with 615. plz help me why this is giving me WA.     my algo:
1. search the adjacent matrix for root with in degree.(which in degree is 0?)
2. then see for multiple root
3. then finding the distance of all node from root using floyed warshall( considering a connected edge weighted as 1)
I know its a long code. h\but plz help me.

Code: Select all

``````#include<iostream>

using namespace std;

int w;

int d;
int n;
int vertex;
int len;

void floyd()
{
int i, j, k;
for( i = 1 ; i <= n ; i++)
{
for( j = 1 ; j <= n ; j++)
{
if(w[i][j] != 0 )
d[i][j] = w[i][j];

else d[i][j] = 999999; // 999999 consider as infinite

}
}

for(i =1 ; i <= n ; i++)
d[i][i] = 0;

for( k = 1 ; k <= n ; k++)
{
for( i = 1 ; i <= n ;i++)
{
for( j =1 ; j <= n ; j++)
{
if(d[i][k]+d[k][j] < d[i][j])
{
d[i][j] = d[i][k]+d[k][j];

}
}
}
}

}

void init()
{
int j,i;
for( i = 1 ; i <= 501 ; i++)
{
for( j = 1 ; j <= 501 ; j++)
{
w[i][j]=0;
}
}

for(i=0;i<501;i++)
vertex[i]= -5;
}

int find(int x)
{
for(int i=1;i<501;i++)
{
if(vertex[i]==x)
{
return i;
}
}

return -5;
}

int main()
{

int root,x,y,nn,root_no,temp_x,temp_y,flag,cas=1;
register int i,j;

//	freopen("in_615.txt","r",stdin);

while(scanf("%d %d",&x,&y) && x!=-1 && y!=-1)
{
init();
if(x==y)
{
if(x==0)
printf("Case %d is not a tree.\n",cas);
else
printf("Case %d is not a tree.\n",cas);

cas++;
continue;
}

vertex=x;
vertex=y;
w=1;

i=3;
flag=0;
while(scanf("%d %d",&x,&y) && x!=0 && y!=0)
{
temp_x=find(x);
if(temp_x== -5)
{
vertex[i]=x;
temp_x=i;
i++;
}
temp_y=find(y);
if(temp_y== -5)
{
vertex[i]=y;
temp_y=i;
i++;
}
if(w[temp_x][temp_y]!=1)
w[temp_x][temp_y]=1;
else
flag=1;

}
if(flag==1)
{
printf("Case %d is not a tree.\n",cas);
cas++;
continue;
}

len=i;
n=len-1;
root=0;root_no=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(w[j][i]!=0)
break;
}
if(j==n+1)
{
root_no=i;
root++;
}
}
if(root!=1)
{
printf("Case %d is not a tree.\n",cas);
cas++;
continue;
}
flag=0;

for(i=1;i<=n;i++)
{
root=0;
for(j=1;j<=n;j++)
{
if(w[j][i]!=0)
root++;
}
if(root!=1)
{
if(root_no!=i)
flag=1;
//continue;
}
}
if(flag==1)
{
printf("Case %d is not a tree.\n",cas);
cas++;
continue;
}

floyd();
flag=0;

for(i=1;i<=n;i++)
{
if(d[root_no][i]==999999)
{
flag=1;
break;
}
}
if(flag!=1)
{
printf("Case %d is a tree.\n",cas);
cas++;
}
else
{
printf("Case %d is not a tree.\n",cas);
cas++;
}

}

return 0;
}
``````

### Re: 615 - Is It A Tree?

Posted: Wed Dec 07, 2011 7:46 am
Hello everyone,

Is it possible to find the judges test input? because as far as i have tested with the inputs given in this thread, my program is working fine.

But on submitting it says wrong answer. I would like to get more inputs to test my program.

Regards
Sajid

### 615 - Is It A Tree?

Posted: Tue May 01, 2012 10:37 am
why WA ?
I have tried for many inputs which gives correct ans ...
I can't find those inputs which gives WA ..

Code: Select all

``//code removed ``

### Re: 615 - Is It A Tree?

Posted: Wed May 02, 2012 1:10 am
Input:
1 2 3 3 0 0
-1 -1

AC Output:
Case 1 is not a tree.

### Re: 615 - Is It A Tree?

Posted: Wed May 02, 2012 7:29 pm
brianfry713 wrote:Input:
1 2 3 3 0 0
-1 -1

AC Output:
Case 1 is not a tree.
U are really a great helper .
I got my mistakes but when I modified my code I got TLE .............
I think the process I chose is not good for this problem .

### Re: 615 - Is It A Tree?

Posted: Wed May 02, 2012 11:20 pm
Instead of a linear search for each node, you could use a c++ map. You may need to change the way you store the edges to enable a search to make sure all nodes are reachable from the root.

### Re: 615 - Is It A Tree?

Posted: Thu May 03, 2012 10:14 pm
brianfry713 wrote:Instead of a linear search for each node, you could use a c++ map. You may need to change the way you store the edges to enable a search to make sure all nodes are reachable from the root.

thanks
Actually I don't have knowledge about c++ map .
But I got accepted by using a array which contains the parent as value & child as index . Then i make sure that all nodes are reachable from the root & it takes .008 sec.