fork download
copy 
  1. /**
  2.  * 
  3.  * https://c...content-available-to-author-only...s.com/blog/entry/75011#comment-591464
  4.  * 
  5. **/
  6.  
  7.  
  8. #include<bits/stdc++.h>
  9. using namespace std;
  10. #define ll long long
  11. #define mod 1000000007
  12. #define pb push_back
  13. #define mp make_pair
  14. #define deb(x) cout<<#x<<" : "<<x<<"\n";
  15. #define debug(x, y) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\n";
  16. #define ff first
  17. #define ss second
  18. #define ub upper_bound
  19. #define lb lower_bound
  20. #define all(a) (a).begin(),(a).end()
  21. #define bs binary_search
  22. #define sz size()
  23. #define vi vector<int>
  24. #define pii pair<int,int>
  25. #define pll pair<ll,ll>
  26. #define ld long double
  27. #define clr fflush(stdout);
  28. //#define clr cout.flush();
  29. #define N 100001
  30. #define fpr(i, a, b) for(int i=a;i<b;i++)
  31. #define fdr(i, a, b) for(int i=a;i>b;i--)
  32. #define repp(i, a, b, d) for(int i=a;i<b;i+=d)
  33. #define repd(i, a, b, d) for(int i=a;i>b;i-=d)
  34. #define LLMIN LLONG_MIN
  35. #define LLMAX LLONG_MAX
  36. #define AKASH_PATEL ios_base::sync_with_stdio(false);
  37. #define SVNIT_SURAT cin.tie(NULL);cout.tie(NULL);
  38. #define mset(x, a) memset(x,a,sizeof(x));
  39. #define nl cout<<'\n';
  40. #define print(c) cout<<c<<'\n';
  41. #define setp(n) cout << fixed << setprecision(n)
  42. #define take_arr(a, n) fpr(i,0,n) cin>>a[i];
  43. #define print_arr(a, n) for(int i=0;i<n;i++) {cout<<a[i]<<" ";} cout<<'\n';
  44. #define take_mat(mat, n, m) fpr(i,0,n) fpr(j,0,m) cin>>mat[i][j];
  45. #define set_mat(mat, n, m, k) fpr(i,0,n) fpr(j,0,m) mat[i][j]=k;
  46. #define print_mat(dist, n, m) for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<dist[i][j]<<" ";}cout<<'\n';}
  47.  
  48. template<class T>
  49. bool inside(T a, T b, T c) { return a <= b && b <= c; }
  50. ll ans=0;
  51. ll n,k;
  52. struct trie
  53. {
  54. 	trie *a[26];
  55. 	int weight;
  56. 	int depth;
  57. 	trie()
  58. 	{
  59. 		for(int i=0;i<26;i++)
  60. 		{
  61. 			a[i]=NULL;
  62. 		}
  63. 		weight=0;
  64. 	}
  65. };
  66. void *insert(string s,int wt,trie *root)
  67. {
  68. //	if(!root->a[curr])
  69. //	{
  70. //		root->a[curr]=new trie();
  71. //	}
  72. //    (root->a[curr]->weight)++;
  73. //	if(idx+1!=s.size())
  74. //	{
  75. //		root->a[curr]=insert(s,wt,idx+1,root->a[curr]);
  76. //	}
  77. //	return root;
  78.     int curr,d=1;
  79.     fpr(i,0,s.sz)
  80.     {
  81.         curr=s[i]-'A';
  82.         if(!root->a[curr])
  83.         {
  84.             root->a[curr]=new trie();
  85.         }
  86.         root=root->a[curr];
  87.         root->weight++;
  88.         root->depth=d++;
  89.     }
  90. }
  91. int searchBest(string s,trie *root)
  92. {
  93. 	int idx=0,curr,max=-1,n=s.size();
  94. 	while(idx<n)
  95. 	{
  96. 		curr=s[idx]-'A';
  97. 		if(!root->a[curr])
  98. 			return -1;
  99. 		max=root->a[curr]->weight;
  100. 		root=root->a[curr];
  101. 		idx++;
  102. 	}
  103. 	return max;
  104. }
  105. void print1(trie *root) // change here
  106. {
  107. 	for(long i=0;i<26;i++)
  108. 	{
  109. 		if(root->a[i])
  110. 		{
  111. 			print1(root->a[i]);
  112. 		}
  113. 	}
  114. 	ans+=root->weight/k;
  115. //	cout<<s<<'\n';
  116. //	cout<<root->weight<<'\n';
  117. }
  118. int main() {
  119.     AKASH_PATEL;
  120.     SVNIT_SURAT;
  121.     int t;
  122.     cin >> t;
  123.     fpr(tas, 1, t + 1) {
  124.         ans=0;
  125.         cin>>n>>k;
  126.         trie *node=new trie();
  127.         string s[n];
  128.         take_arr(s,n)
  129.         fpr(i,0,n)
  130.         {
  131.             insert(s[i],1,node);
  132.         }
  133.         print1(node); // changed here
  134.         cout << "Case #" << tas << ": " << ans << '\n';
  135.     }
  136.     return 0;
  137. }
  138.  
Runtime error #stdin #stdout 0s 4308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4U0qVM
language:
C++14 (gcc 8.3)
created:
4 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!