Page 3 of 3
Posted: Thu Aug 12, 2004 5:10 pm
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
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,rank,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,str2;
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)

}
if(mx==0)  mx++;

printf("%d\n",mx);

}

return 0;
}
``````

### Re: 10685 - Nature

Posted: Sun Oct 02, 2011 6:55 am
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,rank,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,str2;
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)

}
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
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
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
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
Got AC. Thanks a ton ### Re: 10685 - Nature

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

Code: Select all

``````Remove After AC
``````

### Re: 10685 - Nature

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

### Re: 10685 - Nature

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

### Re: 10685 - Nature

Posted: Thu Apr 23, 2015 12:01 pm
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
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.