fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int trie[1000005][28];
  5. int odw[1000005];
  6. vector<int> graf[1000005];
  7. int gdz[1000005];
  8. int topo[1000005];
  9. vector<int> wy;
  10. vector<int> wy1;
  11. int ile = 0;
  12. int uni = 2;
  13.  
  14. pair<int,pair<int,int>> dfs(int x,int gle)
  15. {
  16. 	vector<pair<int,int>> tab;
  17. 	int wyn = 0;
  18. 	for(int i = 0;i < 26;++i)
  19. 	{
  20. 		if(trie[x][i] == 0) continue;
  21. 		pair<int,pair<int,int>> c = dfs(trie[x][i],gle+1);
  22. 		wyn += c.first;
  23. 		tab.push_back(c.second);
  24. 	}
  25. 	if(tab.size() == 0)
  26. 	{
  27. 		//cout << x << ' ';
  28. 		ile++;
  29. 		return {gle,{gle,trie[x][26]}};
  30. 	}
  31. 	//tab.push_back({1e9,-1});
  32. 	//if(tab.size() == 1)
  33. 	//{
  34. 	//	return {wyn,tab[0]};
  35. 	//}
  36. 	sort(tab.begin(),tab.end());
  37. 	int gdzie = -1;
  38. 	//cout << wyn << ' ' << gle  << endl;
  39. 	for(int i = 1;i < (int)tab.size();++i)
  40. 	{
  41. 		if(tab[i-1].first-gle+1 <= gle)
  42. 		{	
  43. 			if(tab[i-1].second != -1)
  44. 			{
  45. 				graf[tab[i-1].second].push_back(tab[i].second);
  46. 				//cout << tab[i].second;
  47. 			}
  48. 			//wy.push_back(tab[i-1].second);
  49. 			wyn -= gle;
  50. 			wyn += tab[i-1].first-gle+1;
  51. 			//cout << tab[i-1] << endl;
  52. 			//cout << wyn << endl;
  53. 			gdzie = i-1;
  54. 		}
  55. 		else
  56. 		break;
  57. 	}
  58. 	for(int i = gdzie+1;i < tab.size();++i)
  59. 	{
  60. 		if(tab[i].first-gle+1 <= gle)
  61. 		{
  62. 			continue;
  63. 		}
  64. 		if(tab[i].second != -1)
  65. 		{
  66. 			wy1.push_back(tab[i].second);
  67. 			//cout << tab[i].second;
  68. 		}
  69. 	}
  70. 	//cout << wyn << endl;
  71. 	if(tab[gdzie+1].first-gle+1 <= gle)
  72. 	{
  73. 		return {wyn,tab[gdzie+1]};
  74. 	}
  75. 	else
  76. 	return {wyn,{1e9,-1}};
  77. }
  78.  
  79.  
  80. int main()
  81. {
  82. 	ios_base::sync_with_stdio(0);
  83. 	int n,x;
  84. 	string slo;
  85. 	//set<string> tak;
  86. 	vector<string> f;
  87. 	cin >> n;
  88. 	for(int i = 0;i < n;++i)
  89. 	{
  90. 		int gdzie = 1;
  91. 		cin >> slo;
  92. 		//tak.insert(slo);
  93. 		f.push_back(slo);
  94. 		for(int j = 0;j < slo.size();++j)
  95. 		{
  96. 			if(trie[gdzie][slo[j]-'a'] == 0)
  97. 			{
  98. 				trie[gdzie][slo[j]-'a'] = uni;
  99. 				trie[uni][27] = gdzie;
  100. 				uni++;
  101. 			}
  102. 			gdzie = trie[gdzie][slo[j]-'a'];
  103. 		}
  104. 		gdz[i+1] = gdzie;
  105. 		trie[gdzie][26] = i+1;
  106. 	}
  107. 	/*for(int i = 1;i < uni;++i)
  108. 	{
  109. 		for(int j = 0;j < 27;++j)
  110. 		{
  111. 			cout << trie[i][j] << ' ';
  112. 		}
  113. 		cout << endl;
  114. 	}*/
  115. 	cout << dfs(1,0).first+n+n-ile << endl;
  116. 	vector<int> co;
  117. 	for(int i = 1;i <= n;++i)
  118. 	{
  119. 		for(int j : graf[i])
  120. 		{
  121. 			topo[j]++;
  122. 		}
  123. 	}
  124. 	for(int i = 1;i <= n;++i)
  125. 	{
  126. 		bool czy = 0;
  127. 		for(int j = 0;j < 26;++j)
  128. 		{
  129. 			if(trie[gdz[i]][j] > 0)
  130. 			{
  131. 				czy = 1;
  132. 				break;
  133. 			}
  134. 		}
  135. 		if(topo[i] == 0 && czy == 0)
  136. 		{
  137. 			co.push_back(i);
  138. 			//cout << i << endl;
  139. 		}
  140. 	}
  141. 	vector<int> wynn;
  142. 	while(co.size())
  143. 	{
  144. 		x = co.back();
  145. 		co.pop_back();
  146. 		vector<int> h;
  147. 		int gdzie = gdz[x];
  148. 		//cout << 'l' << ' '<< x << endl;
  149. 		while(gdzie >= 1)
  150. 		{
  151. 			if(odw[gdzie] == 1) break;
  152. 			odw[gdzie] = 1;
  153. 			if(trie[gdzie][26] > 0)
  154. 			{
  155. 				h.push_back(trie[gdzie][26]);
  156. 			}
  157. 			gdzie = trie[gdzie][27];
  158. 		}
  159. 		for(int i : graf[x])
  160. 		{
  161. 			topo[i]--;
  162. 			if(topo[i] == 0)
  163. 			{
  164. 				//cout << i << endl;
  165. 				co.push_back(i);
  166. 			}
  167. 		}
  168. 		for(int i = h.size()-1;i >= 0;--i)
  169. 		{
  170. 			wynn.push_back(h[i]);
  171. 		}
  172. 	}
  173. 	cout << f[wynn[0]-1] << 'E';
  174. 	for(int i = 1;i < wynn.size();++i)
  175. 	{
  176. 		int ile = 0;
  177. 		for(int j = 0;j < min(f[wynn[i]-1].size(),f[wynn[i-1]-1].size());++j)
  178. 		{
  179. 			if(f[wynn[i]-1][j] == f[wynn[i-1]-1][j])
  180. 			{
  181. 				ile++;
  182. 			}
  183. 			else
  184. 			{
  185. 				break;
  186. 			}
  187. 		}
  188. 		//cout << ile << endl;
  189. 		if((int)f[wynn[i]-1].size()+1 <= ((int)f[wynn[i-1]-1].size())+((int)f[wynn[i]-1].size())+2-ile-ile)
  190. 		{
  191. 			cout << f[wynn[i]-1] << 'E';
  192. 		}
  193. 		else
  194. 		{
  195. 			cout << 'T';
  196. 			for(int j = 0;j < ((int)f[wynn[i-1]-1].size()-ile);++j)
  197. 			{
  198. 				cout << 'B';
  199. 			}
  200. 			for(int j = ile;j < f[wynn[i]-1].size();++j)
  201. 			{
  202. 				cout << f[wynn[i]-1][j];
  203. 			}
  204. 			cout << 'E';
  205. 		}
  206. 	}
  207. 	/*for(int i = 1;i <= n;++i)
  208. 	{
  209. 		cout << i << ';' << ' ';
  210. 		for(int j : graf[i])
  211. 		{
  212. 			cout << j << ' ';
  213. 		}
  214. 		cout << endl;
  215. 	}*/
  216. 	/*for(int i : wy1)
  217. 	{
  218. 		int gdzie = 1;
  219. 		//cout << f[i-1] << endl;
  220. 		for(int j = 0;j < f[i-1].size();++j)
  221. 		{
  222. 			gdzie = trie[gdzie][f[i-1][j]-'a'];
  223. 			//cout << gdzie << endl;
  224. 			if(odw[gdzie] == 0)
  225. 			{
  226. 				if(trie[gdzie][26] != 0)
  227. 				{
  228. 					cout << trie[gdzie][26] << ' ';
  229. 				}
  230. 				odw[gdzie] = 1;
  231. 			}
  232. 		}
  233. 	}*/
  234. }
  235.  
Success #stdin #stdout 0.01s 34360KB
comments (?)
stdin
copy 
57
a
aaaaaababbbbabbbabaabbaabbabbbaabbbabbbbbbabaaaba
aaaabaaabababbababbbbaababaabbbbabaaabaabaabaaabaabbabbbbbabbbbabaa
aaaabaabababbaaabbabbbbabbaabbbabbaaabbbaaaaaabbbaababbabaaaabbabbabbbbbbaaaaaabaabab
aaabababaabbabbbbbbaa
aaababbabbabbabbbbabbababbaabbbbaaababaaabbbbaa
aaabbaaaaababbabb
aaabbbaabbabbbbabbabbbbaaabbbabaaabaabaabababaaabab
aaabbbaba
aaabbbabaabbbaaabbabbbaababaaaaaaabbbaaabaabaaaab
aababbbabbaaabaaababbbbabaababbbbbbbbbbbbaaabbaaaababbbbba
aabbabbaabaabbbabbabaabbaaabbbaba
aabbbabbabbabbabaababbaaaaaaaabaaaabbbaaabaaaaabbbbbbbbbaabaaaabbbabbbbbabaaaba
aabbbbabaababbabaaaabbaabaababab
aabbbbbbabbaaaaaaaabbbbababbaaababaaabbbabababbabbaaabbbbaa
abaaaaabbabbbbaabbbbaabbb
abaaabbbbababababbbbbabbaaaab
abaabbabbaaaababaaabbbaaaababaabbaabbaaababaabbbabbabbaababaabaaaaaa
ababaabbaaabababaabbabbbaaaabaababbbabbabbb
ababbabaabababbbaaaabbbaaaaababaaabaabaababaabaaa
ababbabbabbbabbababbaaabab
ababbbabbbababbaaabaabaaabbababaabbbbaaaabbaabbaabaabbaabaabbbabbbaabbababaaaaaaaaaaaba
ababbbbabaababbbababbabbbbabbaabbbababbbbabbbaaababaaabbaabaabaabbaabaabaaab
abbaaaababbabbaaaabaaaabaaaaababbabaaaabbb
abbaabbbbbaabbaabbbabbabbaba
abbabbaaaaaabaaaaabaaab
abbabbabbaab
abbabbbbbabaaaaabaaaaaaaaaaabbabbaabbaaaaaabbaababbaaaaaabbba
abbbbaaa
abbbbaabbbaaaaabbbbaababbbaababaaabaaaaaaaba
ba
baaaaababaaababbbaaaa
baaabbbbbaabbabaabbaabaaababaaabbabbbbabbb
baabaabbbbbbabbbaaabbabbbbabbbbaaabbbbabaaaaabaaabaaaaabaabaaabaaabababaaaababab
baababbabbbbbbba
baababbbbbab
baabbbbabbabbbabbbabbabbabbbab
baabbbbbbbabaabababaaababaabababaabbabaaabaabbbabbaaaaabbbbbbbabaaaabbabbaababbabbaaabbaaab
babbbbaaababbabababbaabaabbbaaabaaabbbbabaaaabbbabbbaaaabaaaaabaabaabbbbaabbaabbbbbbaaababbbbaa
babbbbaabaabbaaaaabababaaabaaaabaabaaaabbbbaaaababbaabbabbaaaababbabbbbbbababbabba
babbbbabbaabaababbbababbabbbaaabbabaababbaaaaabbaababaaababbabb
bbaaaaabaaaaaaaaababababba
bbaaaababbbaabaabbaaabababababbbaaaaabaabbababbabbbaabaabababaaaaaaaaba
bbaaabaabaabababaababaaaaabbababbabbaaaaabbaabaaabbba
bbaaababbbaabaabbbaaaaaaaaa
bbaabaabbbaaaaabaaabbaaaaaabbbbbababbbbabbbaaaabbbbbbbabaaaaabbbababbbbbbaaabbbbbabaaa
bbaabbbabaaaababbbbaabbaaaabbbbbbbbbababbaaabbbbabbbbba
bbaabbbabbaaaabbababbbbaaababaabbabababbbbb
bbabaabaaabbabbabaaabaaaaaaaabaaaabbabbbbaaaaa
bbabbbaabbbbbababaabaabbaabbbaabbbbbabbaaaab
bbabbbbaabaabbbaaaaaabaabaabaaaaaaaaaababbabaabaaabbbbabbbab
bbabbbbbaaaabbbbaabaabbabbbbabbbbbaabbabaaababbaaaaaabaaabaabaaabaaaaabababbbbba
bbbaabbabbabbbaabbbaabbbbaabaaaaaabaabbbbaaaaaabbbbaabbaaa
bbbbaaaaaaababbbbbabbabbbbababa
bbbbabaaaaaabaaaaabbbbbbbbaabbaaabbbaaabbbabbbbbabaaaabbaababab
bbbbabbaababaaaababbbaaaaaaaabaaaaaaababaabaaaaabaaaaabbbabaabbaabbbabbabbbaaabaab
bbbbabbbbaababbbabaaabbaaa
stdout
copy 
2704
bbbbabbbbaababbbabaaabbaaaEbbbbabbaababaaaababbbaaaaaaaabaaaaaaababaabaaaaabaaaaabbbabaabbaabbbabbabbbaaabaabEbbbbabaaaaaabaaaaabbbbbbbbaabbaaabbbaaabbbabbbbbabaaaabbaabababEbbbbaaaaaaababbbbbabbabbbbababaEbbbaabbabbabbbaabbbaabbbbaabaaaaaabaabbbbaaaaaabbbbaabbaaaEbbabbbbbaaaabbbbaabaabbabbbbabbbbbaabbabaaababbaaaaaabaaabaabaaabaaaaabababbbbbaEbbabbbbaabaabbbaaaaaabaabaabaaaaaaaaaababbabaabaaabbbbabbbabEbbabbbaabbbbbababaabaabbaabbbaabbbbbabbaaaabEbbabaabaaabbabbabaaabaaaaaaaabaaaabbabbbbaaaaaEbbaabbbabbaaaabbababbbbaaababaabbabababbbbbEbbaabbbabaaaababbbbaabbaaaabbbbbbbbbababbaaabbbbabbbbbaEbbaabaabbbaaaaabaaabbaaaaaabbbbbababbbbabbbaaaabbbbbbbabaaaaabbbababbbbbbaaabbbbbabaaaEbbaaababbbaabaabbbaaaaaaaaaEbbaaabaabaabababaababaaaaabbababbabbaaaaabbaabaaabbbaEbbaaaababbbaabaabbaaabababababbbaaaaabaabbababbabbbaabaabababaaaaaaaabaEbbaaaaabaaaaaaaaababababbaEbaETbbbbabbaabaababbbababbabbbaaabbabaababbaaaaabbaababaaababbabbEbabbbbaabaabbaaaaabababaaabaaaabaabaaaabbbbaaaababbaabbabbaaaababbabbbbbbababbabbaEbabbbbaaababbabababbaabaabbbaaabaaabbbbabaaaabbbabbbaaaabaaaaabaabaabbbbaabbaabbbbbbaaababbbbaaEbaabbbbbbbabaabababaaababaabababaabbabaaabaabbbabbaaaaabbbbbbbabaaaabbabbaababbabbaaabbaaabEbaabbbbabbabbbabbbabbabbabbbabEbaababbbbbabETBBBBBabbbbbbbaEbaabaabbbbbbabbbaaabbabbbbabbbbaaabbbbabaaaaabaaabaaaaabaabaaabaaabababaaaabababEbaaabbbbbaabbabaabbaabaaababaaabbabbbbabbbEbaaaaababaaababbbaaaaEaEabbbbaabbbaaaaabbbbaababbbaababaaabaaaaaaabaEabbbbaaaEabbabbbbbabaaaaabaaaaaaaaaaabbabbaabbaaaaaabbaababbaaaaaabbbaEabbabbabbaabETBBBBBaaaaabaaaaabaaabEabbaabbbbbaabbaabbbabbabbabaEabbaaaababbabbaaaabaaaabaaaaababbabaaaabbbEababbbbabaababbbababbabbbbabbaabbbababbbbabbbaaababaaabbaabaabaabbaabaabaaabEababbbabbbababbaaabaabaaabbababaabbbbaaaabbaabbaabaabbaabaabbbabbbaabbababaaaaaaaaaaabaEababbabbabbbabbababbaaababEababbabaabababbbaaaabbbaaaaababaaabaabaababaabaaaEababaabbaaabababaabbabbbaaaabaababbbabbabbbEabaabbabbaaaababaaabbbaaaababaabbaabbaaababaabbbabbabbaababaabaaaaaaEabaaabbbbababababbbbbabbaaaabEabaaaaabbabbbbaabbbbaabbbEaabbbbbbabbaaaaaaaabbbbababbaaababaaabbbabababbabbaaabbbbaaEaabbbbabaababbabaaaabbaabaabababEaabbbabbabbabbabaababbaaaaaaaabaaaabbbaaabaaaaabbbbbbbbbaabaaaabbbabbbbbabaaabaEaabbabbaabaabbbabbabaabbaaabbbabaEaababbbabbaaabaaababbbbabaababbbbbbbbbbbbaaabbaaaababbbbbaEaaabbbabaETabbbaaabbabbbaababaaaaaaabbbaaabaabaaaabEaaabbbaabbabbbbabbabbbbaaabbbabaaabaabaabababaaababEaaabbaaaaababbabbEaaababbabbabbabbbbabbababbaabbbbaaababaaabbbbaaEaaabababaabbabbbbbbaaEaaaabaabababbaaabbabbbbabbaabbbabbaaabbbaaaaaabbbaababbabaaaabbabbabbbbbbaaaaaabaababEaaaabaaabababbababbbbaababaabbbbabaaabaabaabaaabaabbabbbbbabbbbabaaEaaaaaababbbbabbbabaabbaabbabbbaabbbabbbbbbabaaabaE
https://ideone.com/KzPQiV
language:
C++ (gcc 8.3)
created:
8 hours 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!