fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 1e6 + 7;
  6.  
  7. map<char, int> to[maxn];
  8. set<int> nam[maxn][2];
  9. int sz = 1;
  10.  
  11. void add_str(string s, int num, int type)
  12. {
  13. int v = 0;
  14. for(auto c: s)
  15. {
  16. if(!to[v][c])
  17. to[v][c] = sz++;
  18. v = to[v][c];
  19. }
  20. nam[v][type].insert(num);
  21. }
  22.  
  23. int par[maxn];
  24. int ans = 0;
  25.  
  26. void dfs(int v = 0, int lev = 0)
  27. {
  28. for(auto it: to[v])
  29. {
  30. int u = it.second;
  31. dfs(u, lev + 1);
  32. if(nam[v][0].size() < nam[u][0].size())
  33. swap(nam[v][0], nam[u][0]);
  34. for(auto it: nam[u][0])
  35. nam[v][0].insert(it);
  36. if(nam[v][1].size() < nam[u][1].size())
  37. swap(nam[v][1], nam[u][1]);
  38. for(auto it: nam[u][1])
  39. nam[v][1].insert(it);
  40. }
  41. while(nam[v][0].size() && nam[v][1].size())
  42. {
  43. ans += lev;
  44. par[*nam[v][0].begin()] = *nam[v][1].begin();
  45. nam[v][0].erase(nam[v][0].begin());
  46. nam[v][1].erase(nam[v][1].begin());
  47. }
  48. }
  49.  
  50. int main()
  51. {
  52. //freopen("input.txt", "r", stdin);
  53. //freopen("output.txt", "w", stdout);
  54. ios::sync_with_stdio(0);
  55. cin.tie(0);
  56. int n;
  57. cin >> n;
  58. for(int i = 0; i < n; i++)
  59. {
  60. string s;
  61. cin >> s;
  62. add_str(s, i, 0);
  63. }
  64. for(int i = 0; i < n; i++)
  65. {
  66. string s;
  67. cin >> s;
  68. add_str(s, i, 1);
  69. }
  70. dfs();
  71. cout << ans << "\n";
  72. for(int i = 0; i < n; i++)
  73. cout << i + 1 << ' ' << par[i] + 1 << "\n";
  74. return 0;
  75. }
Success #stdin #stdout 0.07s 77696KB
stdin
Standard input is empty
stdout
0