fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. typedef long double ld;
  5. #define rep(i,a,b)  for(ll i=a;i<b;i++)
  6. #define nl cout<<endl
  7.  
  8. #define pii pair<ll,ll>
  9. #define vi  vector<ll>
  10. #define vii vector<pii>
  11. #define mi  map<ll,ll>
  12. #define all(a)  (a).begin(),(a).end()
  13.  
  14. #define pb push_back
  15. #define ff first
  16. #define ss second
  17. #define hell 1000000007
  18.  
  19. #define test4(x,y,z,a) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<"		a is "<<a<<endl;
  20. #define test3(x,y,z) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<endl;
  21. #define test2(x,y) cout<<"x is "<<x<<"		y is "<<y<<endl;
  22. #define test1(x) cout<<"x is "<<x<<endl;
  23. #define N 300009
  24.  
  25. ll power(ll a,ll b,ll m)
  26. {
  27. 	ll ans=1;
  28. 	while(b)
  29. 	{
  30. 		if(b&1)
  31. 			ans=(ans*a)%m;
  32. 		b/=2;
  33. 		a=(a*a)%m;
  34. 	}
  35. 	return ans;
  36. }
  37. map<ll,vi> mp;
  38. typedef struct node
  39. {
  40. 	node* val[27];
  41. 	ll cnt=0;
  42. 	ll depth=0;
  43. }trie;
  44.  
  45. void insert(trie *head,string s)
  46. {
  47. 	trie* curr = head;
  48. 	ll lol=1;
  49. 	rep(i,0,s.length())
  50. 	{
  51. 		ll haha=s[i]-'A';
  52. 		if(!curr -> val[haha])
  53. 		curr->val[haha]= new trie();
  54.  
  55. 		curr=curr-> val[haha];
  56.  
  57. 		(curr->cnt)++;
  58. 		curr->depth=lol++;
  59. 	}
  60. }
  61. void traverse(trie *head)
  62. {
  63. 	if(head == NULL)
  64. 	return;
  65. 	trie* curr=head;
  66.  
  67. 	rep(i,0,26)
  68. 	{
  69.  
  70. 		trie* curr1=curr->val[i];
  71. 		if(curr1!=NULL)
  72. 		{
  73. 			if(curr1->cnt)
  74. 			mp[curr1->depth].pb(curr1->cnt);
  75. 		}
  76. 		traverse(curr1);
  77. 	}
  78. }
  79. int main()
  80. {	
  81. 	ios_base::sync_with_stdio(false);
  82. 	cin.tie(NULL);
  83. 	cout.tie(NULL);
  84.  
  85. 	ll t;cin>>t;
  86. 	rep(ppp,1,t+1)
  87. 	{
  88. 		cout<<"Case #"<<ppp<<": ";
  89.  
  90. 		ll n,k;cin>>n>>k;
  91. 		mp.clear();
  92. 		trie* head = new trie();
  93. 		rep(i,1,n+1)
  94. 		{
  95. 			string s;cin>>s;
  96. 			insert(head,s);
  97. 		}
  98. 		traverse(head);
  99.  
  100. 		ll ans=0;
  101. 		for(auto it=mp.begin();it!=mp.end();it++)
  102. 		{
  103. 			vi vv=it->ss;
  104. 			rep(i,0,vv.size())
  105. 			{
  106. 				ans+=vv[i]/k;
  107. 			}
  108. 		}
  109. 		cout<<ans<<endl;
  110.  
  111. 	}
  112. }
  113.  
Time limit exceeded #stdin #stdout 5s 4252KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NuwL7X
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!