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
- #define int long long
- typedef struct _trie * trie;
- const int maxn = (int)2e5 + 101;
- struct _trie {
- trie letter[33];
- int ver;
- bool mark;
- };
- int n, m;
- trie root;
- int trieSize = 0;
- int cntOfComp = 0;
- string x, y;
- int dp[maxn][2] = {0};
- 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;
- root -> mark = false;
- int cnt = 0;
- for (int i = 0; i < (int)s.size(); i++)
- {
- // cout << "!" << endl;
- 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 -> letter[next] -> mark = false;
- curNode = curNode -> letter[next];
- //curNode -> mark = false;
- }
- // cout << "OK" << endl;
- if (curNode -> mark)
- {
- trieSize--;
- return curNode -> ver;}
- len[trieSize] = (int)s.size();
- curNode -> ver = trieSize;
- curNode -> mark = true;
- return trieSize;
- }
- void dfs1(int ver)
- {
- used[ver] = true;
- for (int i = 0; i < (int)g[ver].size(); i++)
- {
- int to = g[ver][i];
- if (!used[to])
- 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];
- if (!used[to])
- 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];
- dp[ver][1] = dp[to][1];
- }
- else if (dp[to][0] == dp[ver][0]) {
- dp[ver][1] = min(dp[ver][1], dp[to][1]);
- }
- }
- bestCntR[ver] = dp[ver][0];
- bestLen[ver] = dp[ver][1];
- // cout << ver << " : " << bestCntR[ver] << " " << bestLen[ver] << "!" << endl;
- }
- void makeComp(int ver)
- {
- cntOfComp++;
- // cout << ver << "!" << endl;
- dfs2(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], bLen = len[ver];
- else if (cntR[ver] == bestR)
- bLen = min(bLen, len[ver]);
- typeOfComp[ver] = cntOfComp;
- }
- bestCntR[cntOfComp] = bestR;
- bestLen[cntOfComp] = bLen;
- // cout << bestCntR[cntOfComp] << " : " << bestLen[cntOfComp] << endl;
- 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 (typeOfComp[to] != typeOfComp[from])
- gg[typeOfComp[from]].pb(typeOfComp[to]);
- }
- }
- void get(string s, int &x, int &y)
- {
- // cout << s << endl;
- 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]) {
- curNode = 0;
- continue;
- }
- curNode = curNode -> letter[next];
- }
- if (!curNode)
- return;
- int t = typeOfComp[curNode -> ver];
- if (dp[t][0] < x || (dp[t][0] == x && dp[t][1] < y)) {
- x = dp[t][0];
- y = dp[t][1];
- }
- }
- #undef int
- int main()
- {
- #define int long long
- 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 j = 0; j < m; j++)
- {
- cin >> x >> y;
- int v1 = add(x);
- int v2 = add(y);
- // cout << v1 << " " << v2 << endl;
- 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];
- if (!used[ver])
- {
- // cout << "HELO" << endl;
- 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 (int i = 0; i < n; i++)
- {
- int fst, sec;
- get(text[i], fst, sec);
- ansR += fst;
- ansSize += sec;
- }
- cout << ansR << " " << ansSize + n - 1 << endl;
- #undef int
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement