599 Problem description

[raisdead]

I noticed that the html and the pdf for problem 599 are not the same. Which one is correct?

http://uva.onlinejudge.org/index.php?op ... roblem=540

http://uva.onlinejudge.org/external/5/599.pdf

[Shafaet_du]

I just read the html and got ac.

[AYAN]

Why getting WA with this code ? Can anyone give some sampe input ouput..
#include<stdio.h>
#include<string.h>
int bfs(int);
int vis[200];
struct{
int a[100],size;
}node[100];
int main()
{
char p,q,s[1000],ch;
int t,loc[2000],l,i,acorn,tree,no,m,n;
scanf("%d",&t);
getchar();
while(t--)
{
no=0;
for(i=0;i<30;i++)
{
vis=0;
node.size=0;
}
for(ch='A';ch<='Z';ch++)
{
loc[ch]=-1;
}
while(gets(s))
{
if(s[0]=='*')
break;
for(i=0;;i++)
{
if(s>='A'&&s<='Z')
{
p=s;
break;
}
}
for(i++;;i++)
{
if(s>='A' && s<='Z')
{
q=s;
break;
}
}
if(loc[p]==-1)
loc[p]=no++;
if(loc[q]=-1)
loc[q]=no++;
m=loc[p];
n=loc[q];
node[m].a[node[m].size++]=n;
node[n].a[node[n].size++]=m;
}
gets(s);
acorn=tree=0;
l=strlen(s);
for(i=0;i<l;i++)
{
if(s>='A' && s<='Z')
{
n=loc[s[i]];
if(n==-1)
acorn++;
else if(vis[n]==0)
{
tree++;
bfs(n);
}
}
}
printf("There are %d tree(s) and %d acorn(s).\n",tree,acorn);
}
return 0;
}
int bfs(int n)
{
int q[50000],front,rear,i,m;
vis[n]=1;
front=rear=1;
q[front]=n;
while(front<=rear)
{
n=q[front++];
for(i=0;i<node[n].size;i++)
{
m=node[n].a[i];
if(vis[m]==0)
{
vis[m]=1;
q[++rear]=m;
}
}
}
return 0;
}

[mahade hasan]

getting TLE ans .... help me plz......

Code: Select all

#include<iostream>
#include<stdio.h>
#include<queue>
#include<string.h>
#include<vector>
using namespace std;

int main()
{
   int I,K,L,M,N,Tcase,Tree,Acron;
   char Input[100],A,B;
   scanf("%d",&Tcase);
   while(Tcase--){
      Tree=0;Acron=0;
      vector<char>V[10000],V2;
      bool Status[150]={0};
      scanf("\n");
      while(gets(Input)&&Input[0]!='*'){
         I=-1;
         while(Input[++I]){
            if(isalpha(Input[I])){
               A=Input[I];break;
            }
         }
         while(Input[++I]){
            if(isalpha(Input[I])){
               B=Input[I];break;
            }
         }
         V[A].push_back(B);
         //printf("A=%c  B=%c  V=%c\n",A,B,V[A][V[A].size()-1]);
      }
      scanf("\n");
      gets(Input);
      I=-1;
      while(Input[++I]){
         if(isalpha(Input[I])){
            V2.push_back(Input[I]);
            Status[Input[I]]=true;
            //printf("V2=%c\n",V2[V2.size()-1]);
         }
      }
      for(I=0;I<V2.size();I++){
         N=0;
         if(Status[V2[I]]==true){
            queue <char>Q;
            Q.push(V2[I]);
            Status[V2[I]]=false;
            N=1;
            while(!Q.empty()){
               A=Q.front();
               Q.pop();
               for(K=0;K<V[A].size();K++){
                  if(Status[V[A][K]]==true){
                     Status[V[A][K]]=false;
                     Q.push(V[A][K]);
                     ++N;
                  }
               }
            }
         }
         if(N==1)++Acron;
         else if(N>1) ++Tree;
      }
      printf("There are %d tree(s) and %d acorn(s).\n",Tree,Acron);
   }
   return 0;
}

[/color]

[brianfry713]

Use union find.