Page 3 of 3

Posted: Thu Aug 12, 2004 5:10 pm
by Minilek
Oh sorry, I am dumb. I see now why your binary search works since you do not break when lo>=hi ^^;

i still don't see why your make_set works tho but maybe i will realize it latter : (

Re: 10685 - Nature

Posted: Wed Sep 02, 2009 6:00 pm
by Jehad Uddin
i m getting frustrated on this problem,i got 8 WAs in this prob,i have passed all the I/Os on the board,pls help me.Advanced thanks to the helpers.

Code: Select all

#include<iostream>
#include<string>
#include<map>
using namespace std;

int p[10000],rank[10000],n,m,mx;
map<string,int>flag;

void ini()
{
 int i;
 for(i=0;i<=2*n+1;i++)
 p[i]=i,rank[i]=0;
}

int find(int x)
{
 if(x!=p[x])
 p[x]=find(p[x]);
 return p[x];
}
void link(int x,int y)
{
 if(rank[x]>rank[y])
 {
  p[y]=x;
  if(rank[y]>0) rank[x]+=rank[y];
  else rank[x]++;
  if(rank[x]>mx) mx=rank[x];
 }
 else if(rank[y]>rank[x])
 {
  p[x]=y;
  if(rank[x]>0) rank[y]+=rank[x];
  else rank[y]++;
  if(rank[y]>mx) mx=rank[y];
 }
 else if(rank[x]==rank[y])
 {
  
  if(rank[x]==0) 
  {
   p[y]=x;
   rank[x]+=2;
   if(rank[x]>mx) mx=rank[x];
  }
  else
  {
   p[y]=x;
   if(rank[y]>0) rank[x]+=rank[y];
   else rank[x]++;
  if(rank[x]>mx) mx=rank[x];
  }
 
 
 }



}

int main()
{
 int i,j,k,l,u,v;
 char str1[40],str2[40];
 while(scanf("%d%d",&n,&m) == 2)
 {
  if(n==0&&m==0) break;
  flag.clear();
  ini();
  for(i=1;i<=n;i++)
  {
   scanf("%s",str1);
   flag[str1]=i;
  }
  mx=0;
  for(i=1;i<=m;i++)
  {
   scanf("%s%s",str1,str2);
   
   u=find(flag[str1]);
   v=find(flag[str2]);
   if(u!=v)
   link(u,v);
   
  }
  if(mx==0)  mx++;
  
  
  printf("%d\n",mx);
  
 
 
 }  



 return 0;
}

Re: 10685 - Nature

Posted: Sun Oct 02, 2011 6:55 am
by LucasSchm
Jehad Uddin wrote:i m getting frustrated on this problem,i got 8 WAs in this prob,i have passed all the I/Os on the board,pls help me.Advanced thanks to the helpers.

Code: Select all

#include<iostream>
#include<string>
#include<map>
using namespace std;

int p[10000],rank[10000],n,m,mx;
map<string,int>flag;

void ini()
{
 int i;
 for(i=0;i<=2*n+1;i++)
 p[i]=i,rank[i]=0;
}

int find(int x)
{
 if(x!=p[x])
 p[x]=find(p[x]);
 return p[x];
}
void link(int x,int y)
{
 if(rank[x]>rank[y])
 {
  p[y]=x;
  if(rank[y]>0) rank[x]+=rank[y];
  else rank[x]++;
  if(rank[x]>mx) mx=rank[x];
 }
 else if(rank[y]>rank[x])
 {
  p[x]=y;
  if(rank[x]>0) rank[y]+=rank[x];
  else rank[y]++;
  if(rank[y]>mx) mx=rank[y];
 }
 else if(rank[x]==rank[y])
 {
  
  if(rank[x]==0) 
  {
   p[y]=x;
   rank[x]+=2;
   if(rank[x]>mx) mx=rank[x];
  }
  else
  {
   p[y]=x;
   if(rank[y]>0) rank[x]+=rank[y];
   else rank[x]++;
  if(rank[x]>mx) mx=rank[x];
  }
 
 
 }



}

int main()
{
 int i,j,k,l,u,v;
 char str1[40],str2[40];
 while(scanf("%d%d",&n,&m) == 2)
 {
  if(n==0&&m==0) break;
  flag.clear();
  ini();
  for(i=1;i<=n;i++)
  {
   scanf("%s",str1);
   flag[str1]=i;
  }
  mx=0;
  for(i=1;i<=m;i++)
  {
   scanf("%s%s",str1,str2);
   
   u=find(flag[str1]);
   v=find(flag[str2]);
   if(u!=v)
   link(u,v);
   
  }
  if(mx==0)  mx++;
  
  
  printf("%d\n",mx);
  
 
 
 }  



 return 0;
}
If you haven't found out the problem yet, look at your stop condition, R can be 0 (or on your case, m).

Also, i would suggest changing the initialization of rank to 1 instead of 0, so you won't need that if(){}else{} on your link function.

Re: 10685 - Nature

Posted: Sun Dec 21, 2014 6:59 pm
by sss
output of my accepted code for the given input:
1
3
4
2
9

Re: 10685 - Nature

Posted: Thu Dec 25, 2014 4:58 pm
by Tahanima
I've been getting WA with this code. I'm not really understanding where the bug lies. Can anyone please help me out?
[deleted the code as I got AC]

Re: 10685 - Nature

Posted: Wed Jan 07, 2015 11:52 pm
by brianfry713
Change line 22 to:
int PX = Find(x), PY = Find(y);

Change line 62 to:
for(i = 0; i<idx; i++){

Re: 10685 - Nature

Posted: Fri Jan 09, 2015 1:42 am
by Tahanima
Got AC. Thanks a ton :)

Re: 10685 - Nature

Posted: Wed Feb 11, 2015 3:44 pm
by Tanmoy1228
Verdict: WA
can not get the problem..
please help......

Code: Select all

Remove After AC

Re: 10685 - Nature

Posted: Wed Feb 11, 2015 10:31 pm
by brianfry713
Don't read from a file.

Re: 10685 - Nature

Posted: Sat Feb 14, 2015 2:33 pm
by Tanmoy1228
brianfry713 wrote:Don't read from a file.
Thanks brianfry

Re: 10685 - Nature

Posted: Thu Apr 23, 2015 12:01 pm
by uDebug
Culled the input on this thread and uploaded it here:

http://www.udebug.com/UVa/10685

Re: 10685 - Nature

Posted: Mon Jul 17, 2017 2:06 pm
by lighted
Second input (exactly 6, 7, 8, 9, 12, 13, 15, 17 test cases) on uDebug named by "Online Uva judge" is not correct. Because creature's names are listed in one line. But according to problem's description they should be on C lines, where C is number of creatures.
Follow C lines with the names of the creatures, each consisting of lower case
letters (a, b, …, z). No name is longer than 30 letters.