fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long fun(long long i,long long j,vector<string>ok) {
  4. 			string a=ok[i];
  5. 			string b=ok[j];
  6. 			long long l=min(a.length(),b.length());
  7. 			long long k;
  8. 			for(k=0;k<l;k++)
  9. 				if(a[k]!=b[k])
  10. 					break;
  11. 				return k;
  12. }
  13. int main()
  14. {
  15. 	long long t;cin>>t;
  16. 	while(t--)
  17. 	{
  18. 		long long n;cin>>n;
  19. 		vector<string>ok(n);
  20. 		long long hai[n];
  21. 		for(long long i=0;i<n;i++)
  22. 		{
  23. 			string s;cin>>s;
  24. 			ok[i]=s;
  25. 			hai[i]=0;
  26. 		}
  27. 		sort(ok.begin(),ok.end());
  28. 		set<pair<long long,pair<long long,long long>>>ko;
  29. 		for(long long i=1;i<n;i++)
  30. 		{
  31. 			long long k=fun(i-1,i,ok);
  32. 			ko.insert({k,{i-1,i}});
  33. 		}
  34. 		long long ans=0;
  35. 		while(!ko.empty())
  36. 		{
  37. 			auto it=ko.rbegin();
  38. 			long long a=(*it).second.first;
  39. 			long long b=(*it).second.second;
  40. 			if(!hai[a]&&!hai[b])
  41. 			{
  42. 				long long tez=(*it).first*(*it).first;
  43. 				ans+=tez;
  44. 				hai[a]=hai[b]=1;
  45.  
  46. 			}
  47. 			else
  48. 			{
  49. 				ko.erase(*it);continue;
  50. 			}
  51. 			long long left,right;
  52. 			left=a-1;right=b+1;
  53. 			while(left>0&&hai[left])
  54. 				left--;
  55. 			while(right<n&&hai[right])
  56. 				right++;
  57. 			if(left>=0&&right<n&&!hai[left]&&!hai[right])
  58. 			{
  59. 				ko.insert({fun(left,right,ok),{left,right}});
  60. 			}
  61. 			ko.erase(*it);
  62. 		}
  63. 		cout<<ans<<endl;
  64.  
  65. 	}
  66. }
Success #stdin #stdout 0s 4528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/O892Os
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!