10685 - Nature

[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 : (

[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;
}

[LucasSchm]

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.

[sss]

output of my accepted code for the given input:
1
3
4
2
9

[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]

[brianfry713]

Change line 22 to:
int PX = Find(x), PY = Find(y);

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

[Tahanima]

Got AC. Thanks a ton

[Tanmoy1228]

Verdict: WA
can not get the problem..
please help......

Code: Select all

Remove After AC

[brianfry713]

Don't read from a file.

[Tanmoy1228]

Don't read from a file.

Thanks brianfry

[uDebug]

Culled the input on this thread and uploaded it here:

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

[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.