fork download
copy 
  1. //Author: AnandRaj uux
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef long double ld;
  7. typedef pair<int,int> pii;
  8. typedef vector<int> vi;
  9. typedef vector<vi> vvi;
  10. typedef vector<pii> vpii;
  11. typedef pair<ll,ll> pll;
  12. typedef vector<ll> vl;
  13. typedef vector<vl> vvl;
  14. typedef vector<pll> vpll; 
  15.  
  16. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  17. #define test() int t;cin>>t;while(t--)
  18. #define forn(i,f,n) for(int i=f;i<f+n;i++)
  19. #define rforn(i,l,n) for(int i=l;i>l-n;i--)
  20. #define all(v) v.begin(),v.end()
  21. #define prin(V) for(auto v:V) cout<<v<<" ";cout<<endl
  22. #define take(V,f,n) for(int i=f;i<f+n;i++) cin>>V[i]
  23. #define what(x) cerr<<#x<<" = "<<x<<endl
  24. #define KStest() int t,t1;cin>>t;t1=t;while(t--)
  25. #define KScout cout<<"Case #"<<t1-t<<": "
  26.  
  27. const int MOD = 1e9+7,MAX = 1e5+5;
  28. /////////////////FastExp///////////////////
  29. ll powN(ll a,ll p)
  30. {
  31. 	if(p==0) return 1;
  32. 	ll z=powN(a,p/2);
  33. 	z=(z*z)%MOD;
  34. 	if(p%2) z=(z*a)%MOD;
  35. 	return z;
  36. }
  37. /////////////////FastExp///////////////////
  38. //////////////////Sieve////////////////////
  39. vector<bool> is_prime(MAX+1, true);
  40. void Sieve()
  41. {
  42. 	is_prime[0] = is_prime[1] = false;
  43. 	int i,j;
  44. 	for (i = 2; i*i <= MAX; i++) 
  45. 	{
  46.     	if (is_prime[i]) 
  47.     	{
  48.         	for (j = i * i; j <= MAX; j += i)
  49.             	is_prime[j] = false;
  50.     	}
  51. 	}
  52. }
  53. //////////////////Sieve////////////////////
  54.  
  55. int main()
  56. {
  57. 	KStest()
  58. 	{
  59. 		int n,k;
  60. 		cin>>n>>k;
  61. 		vector<string> V(n);
  62. 		take(V,0,n);
  63. 		sort(all(V));
  64. 		vvl H(n);
  65. 		int maxsi=0;
  66. 		int p=31;
  67.  
  68. 		//Hash Matrix
  69. 		for(int i=0;i<n;i++)
  70. 		{
  71. 			H[i].push_back(0);
  72. 			ll hash=0;
  73. 			ll ppow=1;
  74. 			for(auto c:V[i])
  75. 			{
  76. 				hash=(hash+ppow*(c-'A'+1))%MOD;
  77. 				ppow=(ppow*p)%MOD;
  78. 				H[i].push_back(hash);
  79. 			}
  80. 			maxsi=max(maxsi,(int)V[i].size());
  81. 		}
  82.  
  83. 		int ans=0;
  84. 		set<int> Done;
  85.  
  86. 		for(int len=maxsi;len>=0;len--)		//Start from biggest length
  87. 		{
  88. 			map<ll,set<int>> M;				//Map for Hashes
  89. 			for(int i=0;i<n;i++)
  90. 			{
  91. 				if(Done.count(i)) continue;
  92. 				if(V[i].size()<len) continue;
  93. 				M[H[i][len]].insert(i);
  94. 			}
  95. 			for(auto m:M)					//Iterate over all prefix of that length 
  96. 			{
  97. 				while(m.second.size()>=k)
  98. 				{
  99. 					vi Ne;					//Removing groups of K if possible
  100. 					for(auto s:m.second)
  101. 					{
  102. 						Ne.push_back(s);
  103. 						Done.insert(s);
  104. 						if(Ne.size()==k) break;
  105. 					}
  106. 					for(auto ne:Ne)
  107. 					{
  108. 						m.second.erase(ne);
  109. 					}
  110. 					ans+=len;
  111. 				}
  112. 			}
  113. 		}
  114. 		KScout<<ans<<endl;
  115. 	}
  116. }
Success #stdin #stdout 0s 4476KB
comments (?)
stdin
copy 
2
2 2
KICK
START
8 2
G
G
GO
GO
GOO
GOO
GOOO
GOOO
stdout
copy 
Case #1: 0
Case #2: 10
https://ideone.com/MHVKpt
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!