Hi all,
I was trying to solve the problem mentioned in the title of this post using the trie data structure, but something seems to be inefficient/inaccurate in my code.(You may refer to the problem statement here).
Below is presented my solution:-
//God's Grace
#include <iostream>
#include <map>
#include <algorithm>
#include <queue>
#include <list>
#include <string>
#include <cmath>
#include <stack>
#include <cstdio>
#include <fstream>
#include <climits>
#include <set>
#include <vector>
#include <tuple>
#include <cstring>
#include <functional>
#include <utility>
using namespace std;
#define endl '\n'
#define f(k,a,b) for(int k=(a);k<(b);k++)
#define vi vector <int>
#define vvi vector <vector <int> >
#define vii vector <pair <int, int > >
#define lli long long int
#define pii pair <int,int>
#define piii pair< pair<ll int,ll int>, ll int >
#define fsd fflush(stdout);
void tc(int i){cout<<"Case #"<<i+1<<": ";}
void yes(){cout<<"YES"<<endl;}
void no(){cout<<"NO"<<endl;}
void impb(){cout<<"IMPOSSIBLE"<<endl;}
const int fix = 1e9 +7;
const short int ALPHABET_SIZE=26;
int cnt=0;
typedef struct trie_node{
struct trie_node *links[ALPHABET_SIZE];
bool ew;
int no_of_words;
}tride;
tride* getnew(void){
tride* fresh = new tride;
fresh->ew=false;
fresh->no_of_words=0;
f(i,0,ALPHABET_SIZE){
fresh->links[i]=NULL;
}
return fresh;
}
void tride_insert(tride* root, string key){
tride* temp = root;
f(i,0,key.length()){
int index = key[i] — 'A';
if(!temp->links[index]){
temp->links[index] = getnew();
//cnt++;
}
temp = temp->links[index];
}
temp->ew=true;
}
int tride_size(tride* root){
if(root==NULL)
return 0;
int ans=0;
if(root->ew){
ans=1;
}
f(i,0,ALPHABET_SIZE){
ans+=tride_size(root->links[i]);
}
//cout<<ans<<endl;
return root->no_of_words=ans;
}
int tride_search(tride* root, string key){
tride* temp = root;
f(i,0,key.length()){
int index = key[i] — 'A';
if(!temp->links[index])
return 0;
temp = temp->links[index];
}
if(temp!=NULL/*&&temp->ew*/){
return tride_size(temp);
}
return 0;
}
int aux=0;
void answer(tride *root){
if(root==NULL)
return;
int temp = 0;
f(i,0,ALPHABET_SIZE){
if(root->links[i]&&root->links[i]->no_of_words>1){
answer(root->links[i]);
}else if(root->links[i]&&root->links[i]->no_of_words==1){
temp++;
}
//if(root->links[i])
//cout<<root->links[i]->no_of_words<<" ";
}
if(root->ew){
temp++;
}
//cout<<endl;
if(temp==1){
aux++;
}
//cout<<temp<<endl;
if(temp>=2){
cnt++;
}
}
int main() {
int t;
cin>>t;
f(i,0,t){
int n;
cin >>n;
string resp;
tride* head =getnew();
f(j,0,n){
cin>>resp;
reverse(resp.begin(),resp.end());
//cout<<resp<<endl;
tride_insert(head,resp);
}
tride_size(head);
f(q,0,ALPHABET_SIZE){
aux=0;
answer(head->links[q]);
cnt+=(aux/2);
}
tc(i);
cout<<2*cnt<<endl;
cnt=0;
}
return 0;
}
This worked correctly for the small dataset but gave me a 'WA' for the large dataset. Can someone please explain me why ? It will be very helpful if someone could give me a counter test case. Thanks in advance!