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