10685 - Nature
Moderator: Board moderators
-
- Learning poster
- Posts: 74
- Joined: Fri May 08, 2009 5:16 pm
Re: 10685 - Nature
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
If you haven't found out the problem yet, look at your stop condition, R can be 0 (or on your case, m).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; }
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
output of my accepted code for the given input:
1
3
4
2
9
1
3
4
2
9
Re: 10685 - Nature
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]
[deleted the code as I got AC]
Last edited by Tahanima on Fri Jan 09, 2015 1:51 am, edited 2 times in total.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10685 - Nature
Change line 22 to:
int PX = Find(x), PY = Find(y);
Change line 62 to:
for(i = 0; i<idx; i++){
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!
Re: 10685 - Nature
Got AC. Thanks a ton ![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
-
- New poster
- Posts: 10
- Joined: Sat Jul 19, 2014 2:55 am
Re: 10685 - Nature
Last edited by Tanmoy1228 on Sat Feb 14, 2015 2:32 pm, edited 1 time in total.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10685 - Nature
Don't read from a file.
Check input and AC output for thousands of problems on uDebug!
-
- New poster
- Posts: 10
- Joined: Sat Jul 19, 2014 2:55 am
Re: 10685 - Nature
Thanks brianfrybrianfry713 wrote:Don't read from a file.
Re: 10685 - Nature
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