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

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

using namespace std;

define endl '\n'

define f(k,a,b) for(int k=(a);k<(b);k++)

define vi vector

define vvi vector <vector >

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!