Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdio.h>
- #include <cmath>
- #include <algorithm>
- #include <vector>
- #include <string>
- using namespace std;
- #define pb push_back
- typedef struct * _trie trie;
- const int maxn = (int)2e5 + 101;
- struct _trie {
- trie letter[33];
- int ver = 0;
- }
- int n, m;
- trie root;
- int trieSize = 0;
- int cntOfComp = 0;
- string x, y;
- bool used[maxn] + {false};
- string text[maxn];
- int cntR[maxn] = {0};
- int len[maxn] = {0};
- int bestCntR[maxn] = {0};
- int bestLen[maxn] = {0};
- int typeOfComp[maxn] = {0};
- vector < int > list1, list2;
- vector < int > g[maxn];
- vector < int > _g[maxn];
- vector < int > gg[maxn];
- int add(string s)
- {
- trieSize++;
- trie curNode = root;
- for (int i = 0; i < (int)s.size(); i++)
- {
- s[i] = tolower(s[i]);
- if (s[i] == 'r')
- cntR[trieSize]++;
- int next = (int)(s[i]) - (int)('a');
- if (!curNode -> letter[next])
- curNode -> letter[next] = new _trie();
- curNode = curNode -> letter[next];
- }
- len[trieSize] = (int)s.size();
- curNode -> ver = trieSize;
- return trieSize;
- }
- void dfs1(int ver)
- {
- used[ver] = true;
- for (int i = 0; i < (int)g[ver].size(); i++)
- {
- int to = g[ver][i];
- dfs1(to);
- }
- list1.pb(ver);
- }
- void dfs2(int ver)
- {
- used[ver] = true;
- list2.pb(ver);
- for (int i = 0; i < (int)_g[ver].size(); i++)
- {
- int to = _g[ver][i];
- dfs2(to);
- }
- }
- void dfs3(int ver)
- {
- dp[ver][0] = bestCntR[ver];
- dp[ver][1] = bestLen[ver];
- for (int i = 0; i < (int)gg[ver].size(); i++)
- {
- int to = gg[ver][i];
- if (!used[to])
- {
- dfs3(to);
- if (dp[to][0] < dp[ver][0])
- dp[ver][0] = dp[to][0];
- if (dp[ver][0] == dp[to][0])
- dp[ver][1] = min(dp[ver][1], dp[to][1]);
- }
- }
- }
- void makeComp(int ver)
- {
- cntOfComp++;
- df2(ver);
- int bestR = (int)2e9;
- int bLen = (int)2e9;
- for (int i = 0; i < (int)list2.size(); i++)
- {
- int ver = list2[i];
- if (cntR[ver] < bestR)
- bestR = cntR[ver];
- if (cntR[ver] == bestR)
- bLen = min(bLen, len[ver]);
- typeOfComp[ver] = cntOfComp;
- }
- bestCntR[cntOfComp] = bestR;
- bestLen[cntOfComp] = bLen;
- list2.clear();
- }
- void buildGG()
- {
- for (int i = 1; i <= trieSize; i++)
- for (int j = 0; j < (int)g[i].size(); j++)
- {
- int to = g[i][j];
- int from = i;
- if (to != from)
- gg[from].pb(to);
- }
- }
- void get(string s, int &x, int &y)
- {
- x = y = 0;
- y = s.size();
- trie curNode = root;
- for (int i = 0; i < (int)s.size(); i++)
- {
- s[i] = tolower(s[i]);
- if (s[i] == 'r')
- x++;
- int next = (int)(s[i]) - (int)('a');
- if (!curNode)
- continue;
- if (!curNode -> letter[next])
- continue;
- curNode = curNode -> letter[next];
- }
- if (!curNode)
- return;
- int t = typeOfComp[curNode -> ver];
- if (bestCntR[t] < x)
- {
- x = bestCntR[t];
- y = bestLen[t];
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- root = new _trie();
- cin >> n;
- for (int i = 0; i < n; i++)
- cin >> text[i];
- cin >> m;
- for (int i = 0; i < m; i++)
- {
- cin >> x >> y;
- int v1 = add(x);
- int v2 = add(y);
- g[v1].pb(v2);
- _g[v2].pb(v1);
- }
- for (int i = 1; i <= trieSize; i++)
- if (!used[i])
- dfs1(i);
- fill(used, used + maxn, false);
- for (int i = 1; i <= trieSize; i++)
- {
- int ver = list1[trieSize - i + 1];
- if (!used[ver])
- makeComp(ver);
- }
- buildGG();
- fill(used, used + maxn, false);
- for (int i = 1; i <= cntOfComp; i++)
- if (!used[i])
- dfs3(i);
- int ansR = 0;
- int ansSize = 0;
- for (i = 0; i < n; i++)
- {
- int fst, sec;
- get(text[i], fst, sec);
- ansR += fst;
- ansSize += sec;
- }
- cout << ansR << " " << ansSize << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement