## 10226 - Hardwood Species

Moderator: Board moderators

robin_0
New poster
Posts: 7
Joined: Tue Apr 28, 2015 9:47 am

### Re: 10226 - Hardwood Species

I'm getting TLE
Would anybody kindly see what may be wrong here :/
I modified merge sort algorithm to get nlogn time but instead I'm getting TLE :/

Code: Select all

``````#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

char L[20005][50],R[20005][50],array[20005][50];
int cnt[20005],lc[20005],rc[20005];

void mergesort(int p,int r);
void merge (int p ,int q ,int r);

void mergesort(int p,int r)
{
if(p<r)
{
int q=(p+r)/2;
mergesort(p,q);
mergesort(q+1,r);
merge(p,q,r);
}

}

void merge (int p ,int q ,int r)
{

int n1=q-p+1;
int n2=r-q;
int i,j,k;

for(i=0;i<n1;i++)
{
strcpy(L[i],array[i+p]);
lc[i]=cnt[i+p];
}

for(j=0;j<n2;j++)
{

strcpy(R[j],array[j+q+1]);
rc[j]=cnt[j+q+1];
}

i=0;
j=0;

for(k=p;k<=r;k++)
{
if(i<n1&&j<n2)
{
if(strcmp(L[i],R[j])<0)
{
strcpy(array[k],L[i]);
cnt[k]=lc[i];
i++;
}
else
{
strcpy(array[k],R[j]);
cnt[k]=rc[j];
j++;
}

}
else if(i<n1)
{

strcpy(array[k],L[i]);
cnt[k]=lc[i];
i++;

}
else
{
strcpy(array[k],R[j]);
cnt[k]=rc[j];
j++;
}
}
}

int main()
{
int t,i,j,tot=0,tp=1,sum;
char inp[200];

scanf("%d",&t);
gets(array[0]);
gets(array[0]);

for(;tp<=t;tp++)
{
if(tp>1)
printf("\n");
sum=0;
tot=0;
while(gets(inp))
{
if(strlen(inp)==0)
break;
sum++;
for(i=0;i<tot;i++)
{
if(!strcmp(inp,array[i]))
{
{
cnt[i]++;
break;
}
}
}
if(i==tot)
{
strcpy(array[tot],inp);
cnt[tot]=1;
tot++;
}
}

mergesort(0,tot-1);

for(i=0;i<tot;i++)
printf("%s %.4lf\n",array[i],((double)cnt[i]/(double)sum)*100.00);
}

return 0;
}``````

bappi48
New poster
Posts: 1
Joined: Mon Jul 06, 2015 9:17 pm

### 10226 - Hardwood Species - Getting WA

Please can anyone indicate where I'm doing wrong. On sample input output I'm getting correct answer, but in Online judge I'm getting WA.

Code: Select all

``````#include <iostream>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>

#include <cstdio>

using namespace std;

int main()
{

set<string> treeSet;
set<string>::iterator it;
map<string,int> treeCount;

string tmpString;
int caseCount,totalTrees;
float percentage;

cin>>caseCount>>ws;

for(int i=0;i<caseCount;i++){
totalTrees = 0;
treeSet.clear();
treeCount.clear();
while(1){ // Read all string in testSet
getline(cin,tmpString);
if(tmpString == "") break;
treeSet.insert(tmpString);
treeCount[tmpString]++;
totalTrees++;
}

for(it = treeSet.begin(); it!=treeSet.end();it++){
percentage = (treeCount[*it] * 100.00 )/totalTrees ;
cout<<*it<<" "<<fixed<<setprecision(4)<<percentage<<endl;
}

if((i+1)<caseCount){
cout<<'\n';
}

}

return 0;
}

``````