fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX = 1000005;
  5. int trie[MAX][27]; // 0-25: litery, 26: koniec słowa
  6. int uni = 2; // 1 = korzeń
  7. int ile = 0; // liczba liści
  8.  
  9. pair<int,int> dfs(int v, int depth)
  10. {
  11. vector<int> ends;
  12. int cost = 0;
  13.  
  14. for(int c = 0; c < 26; ++c)
  15. {
  16. if (trie[v][c] == 0) continue;
  17. auto res = dfs(trie[v][c], depth + 1);
  18. cost += res.first;
  19. ends.push_back(res.second);
  20. }
  21.  
  22. // liść — słowo końcowe
  23. if (ends.empty())
  24. {
  25. ile++;
  26. return {depth, depth};
  27. }
  28.  
  29. sort(ends.begin(), ends.end());
  30.  
  31. // dla wszystkich poza najgłębszym liściem
  32. // sprawdzamy, czy opłaca się teleportować zamiast wracać
  33. for (int i = 0; i + 1 < (int)ends.size(); ++i)
  34. {
  35. int backCost = ends[i] - depth; // cofanie
  36. int teleportCost = 1; // powrót do korzenia
  37. if (teleportCost < backCost)
  38. cost -= backCost - teleportCost;
  39. }
  40.  
  41. return {cost, ends.back()};
  42. }
  43.  
  44. int main()
  45. {
  46. ios::sync_with_stdio(false);
  47. cin.tie(nullptr);
  48.  
  49. int n;
  50. cin >> n;
  51. string slo;
  52.  
  53. for(int i = 0; i < n; ++i)
  54. {
  55. int gdzie = 1;
  56. cin >> slo;
  57. for(char ch : slo)
  58. {
  59. int c = ch - 'a';
  60. if(trie[gdzie][c] == 0)
  61. trie[gdzie][c] = uni++;
  62. gdzie = trie[gdzie][c];
  63. }
  64. trie[gdzie][26]++; // koniec słowa
  65. }
  66.  
  67. auto wynik = dfs(1, 0);
  68. cout << "Minimalny koszt przejścia: " << wynik.first + n + n - ile << "\n";
  69. }
  70.  
Success #stdin #stdout 0.01s 5320KB
stdin
39
aaacbbcbbcbcbabbaabccaabaaabbab
aabaaaaaaaacb
aabcbacccccacbabacbcbcaabcbcaccacbbcabcccbccaaaca
aacbabbaab
abbaabcacbccbccbabbbbbaabcaaacaabaaacbcbbacabcbcbaab
abccabbbccaaccccabacaaccaacbaccaaacbcaabbc
acbaacbcaaccbbbacccbcacabcccbccaacaaabacabcabcccbbbccabaabbbaaabcababaacaccccac
acbabcbaccaababcabccaccbacbcbababbbcbabbabcccbaacbbbcbbbacbbaabaccabcbccacaacacababaacccbcbaccccccc
acbabcbcbcbbbbacbbbaabcbcbccbaaacabcbaabcaabba
accbaabaccabbacaaccbcbaaccbaccaaaacbcabccacbaaaacbbcaaabac
accbcbbabaccaabacacacbaabbccccbacaaccbaacacccbacabaacbbccbbbcbcabbbaaaaaabaabccc
b
ba
babacbaccbccbcacbcbbaaacbccbcbbcaaaaaabacbaccbcaacbbcbcbccbccacbcbaabbbcbccbcbbacabaabcabcabbcab
babbccba
babcbabbcacccbacbba
babcccbbbacabaababbaccbbcacccbaccbbcbcaccbbbabbcbcb
bacbaabbccccbcabcbacbbabaaabccbbbbbcacaacbabaccacaabcbbbcbaacbaaaaacbbcc
bbabacabababbaaccaaabaababccabbbcbaaacabcabacaacbaaababaabbbcbacbbabcbcbcacccabbcbbc
bbacbbbbcabbacbcbccabbaccbacccbcacbccacccaacacbccbbccbcccabbaabcaaaccabccccbcbcbabccbbaaaabca
bbbcbccbc
bbbcbcccb
bbcccaaabacabacccccccbbaccaccbaabacabacacacabbac
bcaaaaccabaccacaabccacccbbcabaacbcacbbaaabcccabbbcbaccbaccbababcabccaaaccaaaabbab
bcabaacababbcbabcabacabbaacbbcbaacbccaacabccaccabbabcbbbabccabbbaaaabcbaacaabbacbbccbaacaacccbbcbbb
bccbabbacacbcacccbbccccbcbbcccbabccbbcccbabcbba
bccbabbbcaabaccabcabbbabcacaababacbcbaccacacaabccabccacabcbbbacaacbcacbc
bccbcababcbcb
bccbcacaacaccbb
caacccacbcbbab
cacaaabcaccbcbccbccaaaacbabacccabbccccccababbbcbaabcaccccccabcbccaabcababcacbbabbccc
caccaacacababbbccbbacacaaabbacccaabcbbacbbccaccbabbccbbcbccbbcabccbccbcbaccacacacbbbaccbccbcbca
cbabbccbbbababcaaccbaaaaacaccbbaa
cbcaccbcbb
ccbacbacbccbccaaabbcbcabbcacccaaabbbccbcccabbbacbcaaabcbabcbbbccccaccacabbbbcbcbcccbbbacab
cccabcabbababaabacababacabbccacccbcbbccaabbcacccbccbaac
cccacccbabababacaababcabcacbabcbbaabcacbbccbaaacccacbbbbcbcbccbcbabababa
cccbbacbacccccabbbabaccacbabbabab
cccbbbbabccababacbaccaabcaaaccccbbaccbabaaacccaabbbbacaaa
stdout
Minimalny koszt przejścia: 277