10685 - Nature

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

Moderator: Board moderators

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by Minilek » 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 : (

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 10685 - Nature

Post by Jehad Uddin » 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[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
New poster
Posts: 17
Joined: Mon May 18, 2009 10:00 pm

Re: 10685 - Nature

Post by LucasSchm » 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[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
New poster
Posts: 1
Joined: Tue Feb 26, 2013 8:23 pm

Re: 10685 - Nature

Post by sss » Sun Dec 21, 2014 6:59 pm

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

Tahanima
New poster
Posts: 8
Joined: Thu Dec 25, 2014 4:50 pm

Re: 10685 - Nature

Post by Tahanima » 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]
Last edited by Tahanima on Fri Jan 09, 2015 1:51 am, edited 2 times in total.

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

Re: 10685 - Nature

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

Tahanima
New poster
Posts: 8
Joined: Thu Dec 25, 2014 4:50 pm

Re: 10685 - Nature

Post by Tahanima » Fri Jan 09, 2015 1:42 am

Got AC. Thanks a ton :)

Tanmoy1228
New poster
Posts: 10
Joined: Sat Jul 19, 2014 2:55 am

Re: 10685 - Nature

Post by Tanmoy1228 » Wed Feb 11, 2015 3:44 pm

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

Code: Select all

Remove After AC
Last edited by Tanmoy1228 on Sat Feb 14, 2015 2:32 pm, edited 1 time in total.

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

Re: 10685 - Nature

Post by brianfry713 » Wed Feb 11, 2015 10:31 pm

Don't read from a file.
Check input and AC output for thousands of problems on uDebug!

Tanmoy1228
New poster
Posts: 10
Joined: Sat Jul 19, 2014 2:55 am

Re: 10685 - Nature

Post by Tanmoy1228 » Sat Feb 14, 2015 2:33 pm

brianfry713 wrote:Don't read from a file.
Thanks brianfry

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10685 - Nature

Post by uDebug » Thu Apr 23, 2015 12:01 pm

Culled the input on this thread and uploaded it here:

http://www.udebug.com/UVa/10685
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10685 - Nature

Post by lighted » 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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 106 (10600-10699)”