Please help me to figure out why i am getting Runtime in this problem — This was my first time implementing trie
And i got Runtime for larger sub tasks in google kickstart A 2020 , problem D
My Code
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
using namespace std;
using namespace __gnu_pbds;
ll ans=0;
ll n,k;
typedef struct node{
ll cnt=0;
node* ch[26];
}trie;
struct node* root;
void insert(string &s)
{
struct node* cur = root;
ll N= s.length();
ll z;
for(ll i=0;i<N;i++)
{
z = (ll)(s[i]) -(ll) ('A');
// cout<<"::::::: "<<z<<endl;
if(cur->ch[z])
{
// cout<<"+++++"<<endl;
cur=cur->ch[z];
}
else
{
// cout<<"#######"<<endl;
struct node* newnode = (struct node*)malloc(sizeof(struct node)) ;
cur->ch[z]=newnode;
cur=newnode;
// cur->cnt++;
}
}
cur->cnt = cur->cnt + 1;
//cout<<cur->cnt<<" "<<z<<endl;
}
void dfs(struct node* cur,ll lvl)
{
for(ll i=0;i<26;i++)
{
// cout<<lvl<<" "<<i<<" ";
if(cur->ch[i]!=NULL)
{
// cout<<"S"<<endl;
dfs(cur->ch[i],lvl+1);
cur->cnt += cur->ch[i]->cnt;
}
}
// cout<<"yoo"<<" "<<lvl<<" "<<cur->cnt<<endl;
while(cur->cnt>=k && cur!=NULL)
{
cur->cnt-=k;
ans+=lvl;
}
return;
}
// void print(struct node*cn)
// {
// for(ll i=0;i<26;i++)
// {
// if(cn->ch[i])
// {
// cout<<i<<" ";
// }
// }
// return;
// }
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.flush();
ll t=1;
ll CaseN=1;
cin>>t;
while(t--)
{
ans=0;
cin>>n>>k;
root = (struct node*)malloc(sizeof(struct node));
for(ll i=0;i<n;i++)
{
string s;
cin>>s;
insert(s);
}
dfs(root,0);
// print(root);
cout<<"Case #"<<CaseN<<": ";
CaseN++;
// print your ans below;
cout<<ans<<endl;
}
return 0;
}
