## 599 Problem description

The forum to report every bug you find or tell us what you'd like to find in UVa OJ

Moderator: Board moderators

New poster
Posts: 6
Joined: Thu Dec 30, 2010 7:25 pm

### 599 Problem description

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
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 599 Problem description

I just read the html and got ac.

AYAN
New poster
Posts: 3
Joined: Fri Jul 08, 2011 5:53 pm

### Re: 599 Problem description

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

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 599 Problem description

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]
we r surrounded by happiness
need eyes to feel it!

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

### Re: 599 Problem description

Use union find.
Check input and AC output for thousands of problems on uDebug!