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