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!