fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/em8kM5
language:
C++14 (gcc 8.3)
created:
8 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!