615 - Is It A Tree?

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

Moderator: Board moderators

payton1
New poster
Posts: 5
Joined: Mon Oct 02, 2006 10:31 pm

615 WA

Post by payton1 » 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;
}

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

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

Post by turcse143 » 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
''I want to be most laziest person in the world''

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Re: 615 - Is It A Tree?

Post by smilitude » Thu Jul 31, 2008 7:02 am

i think you have given one extra output.
there are nine cases in your input. ;)
fahim
#include <smile.h>

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: Some sample I/O on problem 615

Post by mak(cse_DU) » 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.
Mak
Help me PLZ!!

codeworrior
New poster
Posts: 14
Joined: Wed Oct 21, 2009 11:04 am

Re: 615 - Is It A Tree?

Post by codeworrior » Sun Jan 10, 2010 5:18 pm

//code removed after AC

why am i getting WA...
Last edited by codeworrior on Tue Jan 12, 2010 4:27 pm, edited 1 time in total.

codeworrior
New poster
Posts: 14
Joined: Wed Oct 21, 2009 11:04 am

615 is it a tree??

Post by codeworrior » Mon Jan 11, 2010 8:21 am

//code removed after AC


why am i getting WA...
thanks in advance

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 615 - Is It A Tree?

Post by helloneo » Mon Jan 11, 2010 4:03 pm

See previous posts..
Your code fails on turcse143's test cases..

codeworrior
New poster
Posts: 14
Joined: Wed Oct 21, 2009 11:04 am

Re: 615 - Is It A Tree?

Post by codeworrior » Tue Jan 12, 2010 4:25 pm

yes corrected it ...got AC..thanks..

AmitMist
New poster
Posts: 6
Joined: Wed Feb 18, 2009 10:20 pm

Re: 615 - Is It A Tree?

Post by AmitMist » 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. :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;
}

sajidzaman
New poster
Posts: 1
Joined: Wed Dec 07, 2011 7:42 am
Location: Islamabad
Contact:

Re: 615 - Is It A Tree?

Post by sajidzaman » 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

shatil_cse
New poster
Posts: 11
Joined: Thu Apr 05, 2012 8:33 pm

615 - Is It A Tree?

Post by shatil_cse » 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 
Last edited by shatil_cse on Thu May 03, 2012 10:16 pm, edited 1 time in total.

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

Re: 615 - Is It A Tree?

Post by brianfry713 » Wed May 02, 2012 1:10 am

Input:
1 2 3 3 0 0
-1 -1

AC Output:
Case 1 is not a tree.
Check input and AC output for thousands of problems on uDebug!

shatil_cse
New poster
Posts: 11
Joined: Thu Apr 05, 2012 8:33 pm

Re: 615 - Is It A Tree?

Post by shatil_cse » 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 .

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

Re: 615 - Is It A Tree?

Post by brianfry713 » 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.
Check input and AC output for thousands of problems on uDebug!

shatil_cse
New poster
Posts: 11
Joined: Thu Apr 05, 2012 8:33 pm

Re: 615 - Is It A Tree?

Post by shatil_cse » 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.

Post Reply

Return to “Volume 6 (600-699)”