fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ld double
  5. const int nax=1e5+5;
  6. ll ans=0;
  7. int n,k;
  8. string s;
  9.  
  10. class node{
  11.     public : 
  12.     int val;
  13.     node** child;
  14.     node(){
  15.         val=0;
  16.         child=new node*[26];
  17.         for(int i=0;i<26;i++){
  18.             child[i]=NULL;
  19.         }
  20.     }
  21. };
  22. class trie{
  23.     public :
  24.     node* root;
  25.     trie(){
  26.         root=new node;
  27.     }
  28.     void insert(node* cn, int index){
  29.         if(index==s.size()) return ;
  30.         int pos=s[index]-'A';
  31.         if(cn->child[pos]==NULL){
  32.             node* temp=new node;
  33.             cn->child[pos]=temp;
  34.         }
  35.         cn->child[pos]->val++;
  36.         insert(cn->child[pos],index+1);
  37.     }
  38.     int dfs(node * cn, int lev){
  39.         int r=0;
  40.         if(cn==NULL) return 0;
  41.         for(int i=0;i<26;i++){
  42.             if(cn->child[i] == NULL) continue;
  43.             r+=dfs(cn->child[i],lev+1);
  44.         }
  45.         cn->val-=r;
  46.         ans+=(cn->val/k)*lev;
  47.  
  48.         return r+(cn->val/k)*k;
  49.     }
  50. };
  51.  
  52. int main() {
  53.     ios_base::sync_with_stdio(false);
  54.     cin.tie(NULL); cout.tie(NULL);
  55.     int tt;
  56.     cin>>tt;
  57.     int ty=1;
  58.     while(tt--){
  59.         ans=0;
  60.         cin>>n>>k;
  61.         trie obj;
  62.         for(int i=0;i<n;i++){
  63.             cin>>s;
  64.             obj.insert(obj.root,0);
  65.         }
  66.         int faltu=obj.dfs(obj.root,0);
  67.         cout<<"Case #"<<ty++<<": "<<ans<<'\n';
  68.     }
  69. }
Success #stdin #stdout 0s 4272KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/zV7x9m
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!