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 »

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 »

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 »

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 »

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 »

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 »

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 »

Got AC. Thanks a ton :)

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

Re: 10685 - Nature

Post by Tanmoy1228 »

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 »

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 »

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

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

Re: 10685 - Nature

Post by uDebug »

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: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10685 - Nature

Post 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.
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)”