Advertisement
Guest User

Untitled

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