Advertisement
Guest User

Untitled

a guest
Sep 17th, 2014
191
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.60 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <string>
  7.  
  8. using namespace std;
  9.  
  10. #define pb push_back
  11. #define int long long
  12.  
  13. typedef struct _trie * trie;
  14.  
  15. const int maxn = (int)2e5 + 101;
  16.  
  17. struct _trie {
  18.     trie letter[33];
  19.     int ver;
  20.     bool mark; 
  21. };
  22.          
  23. int n, m;
  24. trie root;
  25. int trieSize = 0;
  26. int cntOfComp = 0;
  27. string x, y;
  28. int dp[maxn][2] = {0};
  29. bool used[maxn] = {false};
  30. string text[maxn];
  31. int cntR[maxn] = {0};
  32. int len[maxn] = {0};
  33. int bestCntR[maxn] = {0};
  34. int bestLen[maxn] = {0};
  35. int typeOfComp[maxn] = {0};
  36. vector < int > list1, list2;
  37. vector < int > g[maxn];
  38. vector < int > _g[maxn];
  39. vector < int > gg[maxn];
  40.  
  41. int add(string s)
  42. {
  43.     trieSize++;
  44.     trie curNode = root;
  45.     root -> mark = false;
  46.     int cnt = 0;
  47.     for (int i = 0; i < (int)s.size(); i++)
  48.     {
  49.     //  cout << "!" << endl;
  50.         s[i] = tolower(s[i]);
  51.         if (s[i] == 'r')
  52.             cntR[trieSize]++;
  53.         int next = (int)(s[i]) - (int)('a');
  54.         if (!curNode -> letter[next])
  55.             curNode -> letter[next] = new _trie(), curNode -> letter[next] -> mark = false;
  56.         curNode = curNode -> letter[next];
  57.         //curNode -> mark = false;
  58.     }
  59. //  cout << "OK" << endl;
  60.     if (curNode -> mark)
  61.         {
  62.                 trieSize--;
  63.                 return curNode -> ver;}
  64.  len[trieSize] = (int)s.size();
  65.     curNode -> ver = trieSize;
  66.     curNode -> mark = true;
  67.     return trieSize;
  68. }
  69.  
  70. void dfs1(int ver)
  71. {
  72.     used[ver] = true;
  73.     for (int i = 0; i < (int)g[ver].size(); i++)
  74.     {
  75.         int to = g[ver][i];
  76.         if (!used[to])
  77.             dfs1(to);
  78.     }
  79.     list1.pb(ver);
  80. }
  81.  
  82. void dfs2(int ver)
  83. {
  84.     used[ver] = true;
  85.     list2.pb(ver);
  86.     for (int i = 0; i < (int)_g[ver].size(); i++)
  87.     {                                                      
  88.         int to = _g[ver][i];
  89.         if (!used[to])
  90.             dfs2(to);
  91.     }
  92. }
  93.  
  94. void dfs3(int ver)
  95. {
  96.     dp[ver][0] = bestCntR[ver];
  97.     dp[ver][1] = bestLen[ver];
  98.     for (int i = 0; i < (int)gg[ver].size(); i++)
  99.     {
  100.         int to = gg[ver][i];
  101.         if (!used[to])
  102.             dfs3(to);
  103.         if (dp[to][0] < dp[ver][0]) {
  104.             dp[ver][0] = dp[to][0];
  105.             dp[ver][1] = dp[to][1];
  106.         }
  107.         else if (dp[to][0] == dp[ver][0]) {
  108.             dp[ver][1] = min(dp[ver][1], dp[to][1]);
  109.         }  
  110.     }
  111.     bestCntR[ver] = dp[ver][0];
  112.     bestLen[ver] = dp[ver][1];
  113. //  cout << ver << " : " << bestCntR[ver] << " " << bestLen[ver] << "!" << endl;
  114. }
  115.  
  116. void makeComp(int ver)
  117. {
  118.     cntOfComp++;
  119. //  cout << ver << "!" << endl;
  120.     dfs2(ver);                
  121.     int bestR = (int)2e9;
  122.     int bLen = (int)2e9;
  123.     for (int i = 0; i < (int)list2.size(); i++)
  124.     {                              
  125.         int ver = list2[i];
  126.         if (cntR[ver] < bestR)
  127.             bestR = cntR[ver], bLen = len[ver];
  128.         else if (cntR[ver] == bestR)
  129.             bLen = min(bLen, len[ver]);
  130.         typeOfComp[ver] = cntOfComp;
  131.     }
  132.     bestCntR[cntOfComp] = bestR;
  133.     bestLen[cntOfComp] = bLen;
  134. //  cout << bestCntR[cntOfComp] << " : " << bestLen[cntOfComp] << endl;
  135.     list2.clear();    
  136. }
  137.  
  138. void buildGG()
  139. {
  140.     for (int i = 1; i <= trieSize; i++)
  141.         for (int j = 0; j < (int)g[i].size(); j++)
  142.         {
  143.             int to = g[i][j];
  144.             int from = i;
  145.             if (typeOfComp[to] != typeOfComp[from])
  146.                 gg[typeOfComp[from]].pb(typeOfComp[to]);
  147.         }
  148. }
  149.  
  150. void get(string s, int &x, int &y)
  151. {
  152. //  cout << s << endl;
  153.     x = y = 0;
  154.     y = s.size();
  155.     trie curNode = root;
  156.     for (int i = 0; i < (int)s.size(); i++)
  157.     {
  158.         s[i] = tolower(s[i]);
  159.         if (s[i] == 'r')
  160.             x++;
  161.         int next = (int)(s[i]) - (int)('a');
  162.         if (!curNode)
  163.             continue;
  164.         if (!curNode -> letter[next]) {
  165. curNode = 0;
  166. continue;
  167. }
  168.         curNode = curNode -> letter[next];
  169.     }
  170.     if (!curNode)
  171.         return;
  172.     int t = typeOfComp[curNode -> ver];
  173.     if (dp[t][0] < x || (dp[t][0] == x && dp[t][1] < y)) {
  174.         x = dp[t][0];
  175.         y = dp[t][1];
  176.     }
  177. }
  178.  
  179. #undef int
  180.  
  181. int main()
  182. {
  183.     #define int long long
  184.     ios_base::sync_with_stdio(false);
  185.     root = new _trie();
  186.     cin >> n;
  187.     for (int i = 0; i < n; i++)
  188.         cin >> text[i];
  189.     cin >> m;
  190.     for (int j = 0; j < m; j++)
  191.     {
  192.         cin >> x >> y;
  193.         int v1 = add(x);
  194.         int v2 = add(y);
  195.     //  cout << v1 << " " << v2 << endl;
  196.         g[v1].pb(v2);
  197.         _g[v2].pb(v1);     
  198.     }
  199.     for (int i = 1; i <= trieSize; i++)
  200.         if (!used[i])
  201.             dfs1(i);
  202.     fill(used, used + maxn, false);
  203.     for (int i = 1; i <= trieSize; i++)
  204.     {
  205.         int ver = list1[trieSize - i];
  206.         if (!used[ver])
  207.         {
  208.         //  cout << "HELO" << endl;
  209.             makeComp(ver);  
  210.         }
  211.     }
  212.     buildGG();
  213.     fill(used, used + maxn, false);
  214.     for (int i = 1; i <= cntOfComp; i++)
  215.         if (!used[i])
  216.             dfs3(i);
  217.     int ansR = 0;
  218.     int ansSize = 0;    
  219.     for (int i = 0; i < n; i++)
  220.     {
  221.         int fst, sec;
  222.         get(text[i], fst, sec);
  223.         ansR += fst;
  224.         ansSize += sec;
  225.     }
  226.     cout << ansR << " " << ansSize + n - 1 << endl;
  227.     #undef int
  228.     return 0;
  229. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement