fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll int
  4. ll vis[100005];
  5. ll trie[26][100005];
  6. ll ans[100005];
  7. ll sz,cur;
  8. string s;
  9. void in()
  10. {
  11.     ll st=0,dep=0,mi=0;
  12.     for (ll i=s.size()-1;i>=0;i--)
  13.     {
  14.         dep+=1;
  15.         ll cur=s[i]-97;
  16.         if(!vis[trie[cur][st]])
  17.         {
  18.             trie[cur][st]=++sz;
  19.         }
  20.         vis[trie[cur][st]]+=1;
  21.         if(i==(s.size()-1))
  22.             mi=vis[trie[cur][st]];
  23.         else
  24.         {
  25.           mi=min(mi,vis[trie[cur][st]]); // mi stores the minimum value on current path
  26.         }
  27.         ans[dep]=max(ans[dep],mi); // ans[] stores result for a given depth for all strings
  28.         st=trie[cur][st];
  29.     }
  30. }
  31. int main()
  32. {
  33.     ll i,j,k,n,m,t;
  34.     scanf("%d",&t);
  35.     while(t--)
  36.     {
  37.         ll q;
  38.         sz=0;
  39.         for(i=0;i<=100000;i++)
  40.         {
  41.             ans[i]=0,vis[i]=0;
  42.         }
  43.         scanf("%d %d",&n,&q);
  44.         while(n--)
  45.         {
  46.             cin>>s;
  47.             in();
  48.         }
  49.         while(q--)
  50.         {
  51.             scanf("%d",&j);
  52.             printf("%d\n",ans[j]);
  53.         }
  54.     }
  55. }
  56.  
Time limit exceeded #stdin #stdout 5s 4536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9DAlEB
language:
C++14 (clang 8.0)
created:
5 years ago
visibility:
public

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!