fork download
copy 
  1. //snigdh_op
  2. #include<bits/stdc++.h>
  3. #define endl "\n"
  4. using namespace std;
  5. #define fio ios_base::sync_with_stdio(false)
  6.  
  7. struct tnode{
  8. 	tnode *ptr[26]={NULL};
  9. 	bool isWord=false;
  10. };
  11. typedef tnode* TTPTR;
  12. void add(TTPTR &T,string &s,int i)
  13. {
  14. 	int k=int(s[i])-97;
  15. 	if(i==s.length()-1)
  16. 	{
  17. 		if(T->ptr[k])
  18. 			T->ptr[k]->isWord=true;
  19.  
  20. 		else
  21. 		{
  22. 			T->ptr[k]=new tnode;
  23. 			T->ptr[k]->isWord=true;
  24. 		}
  25. 		return ;
  26. 	}
  27. 	else
  28. 	{	i++;
  29. 		if(!T->ptr[k])
  30. 			T->ptr[k]=new tnode;
  31. 		add(T->ptr[k],s,i);
  32. 	}
  33. }
  34. int fill(TTPTR &T,unordered_map<int,int>&mp)
  35. {	
  36. 	if(!T)return 0;
  37. 	int ans=0;
  38. 	if(T->isWord)ans++;
  39. 	for(int i=0;i<26;i++)ans+=fill(T->ptr[i],mp);
  40. 	mp[ans]++;
  41. 	return ans;
  42. }
  43. int main()
  44. {   fio;
  45.     cin.tie(NULL);
  46.     int n;
  47.     cin>>n;
  48.     vector<string>inp(n);
  49.     for(int i=0;i<n;i++)cin>>inp[i];
  50.     int m;
  51. 	cin>>m;
  52. 	TTPTR T=new tnode;
  53.  
  54. 	for(int i=0;i<n;i++)
  55. 	{	
  56. 		add(T,inp[i],0);
  57. 	}
  58. 	unordered_map<int,int>mp;
  59. 	int res=fill(T,mp);
  60. 	for(int i=n-1;i>=1;i--)mp[i]+=mp[i+1];
  61. 	while(m--)
  62. 	{
  63. 		int k;
  64. 		cin>>k;
  65. 		cout<<mp[k]-1<<endl;
  66. 	}
  67. 	return 0;
  68. }
Runtime error #stdin #stdout 0s 4388KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/T3z3xo
language:
C++14 (gcc 8.3)
created:
3 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!