Page 4 of 5

615 WA

Posted: Fri Oct 06, 2006 9:06 am
by payton1
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
by turcse143
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
by smilitude
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
by mak(cse_DU)
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
by codeworrior
//code removed after AC

why am i getting WA...

615 is it a tree??

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


why am i getting WA...
thanks in advance

Re: 615 - Is It A Tree?

Posted: Mon Jan 11, 2010 4:03 pm
by helloneo
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
by codeworrior
yes corrected it ...got AC..thanks..

Re: 615 - Is It A Tree?

Posted: Fri Aug 27, 2010 3:41 pm
by AmitMist
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. :oops: :roll: :x :roll: :oops:
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[501][501];

int d[501][501];
int n; 
int vertex[501];
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[1]=x;
		vertex[2]=y;
		w[1][2]=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
by sajidzaman
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
by shatil_cse
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
by brianfry713
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
by shatil_cse
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
by brianfry713
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
by shatil_cse
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.