Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define pb push_back
- #define fst first
- #define snd second
- #define all(c) (c).begin(), (c).end()
- typedef long long ll;
- typedef long double ld;
- const ll INF64 = 1e18 + 228;
- const int INF32 = 1e9 + 1337;
- const int MOD = 1e9 + 7;
- map<ll, pair<ll, ll> > f;
- map<ll, vector<ll> > g;
- vector<string> a;
- vector<ll> has;
- map<ll, bool> u;
- int p = 31;
- vector<ll> p_pow;
- string lower(string x)
- {
- for(int i = 0; i < x.length(); i++)
- if(x[i] >= 'A' && x[i] <= 'Z') x[i] += 'a' - 'A';
- return x;
- }
- ll hs(string a)
- {
- ll ans = 0;
- for(int i = 0; i < a.size(); i++)
- {
- ans += (a[i] - 'a') * p_pow[i] % MOD;
- }
- return ans;
- }
- int main()
- {
- #ifndef __WIN32
- ifstream cin("input.txt");
- ofstream cout("output.txt");
- #endif
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- int n;
- cin >> n;
- a.resize(n);
- has.resize(n);
- int n_nn = 500001;
- p_pow.resize(n_nn);
- p_pow[0] = 1;
- for(int i = 1; i < n_nn; i++)
- p_pow[i] = p_pow[i - 1] * p % MOD;
- for(int i = 0; i < n; i++)
- {
- cin >> a[i];
- a[i] = lower(a[i]);
- int cntR = 0;
- for(int j = 0; j < a[i].length(); j++) cntR += a[i][j] == 'r';
- ll hh = hs(a[i]);
- has[i] = hh;
- f[hh] = {cntR, a[i].length()};
- }
- int m;
- cin >> m;
- for(int i = 0; i < m; i++)
- {
- string from, to;
- cin >> from >> to;
- from = lower(from);
- to = lower(to);
- ll h1 = hs(from), h2 = hs(to);
- int c1 = 0, c2 = 0;
- for(int j = 0; j < from.length(); j++) c1 += from[j] == 'r';
- for(int j = 0; j < to.length(); j++) c2 += to[j] == 'r';
- f[h1] = {c1, from.length()};
- f[h2] = {c2, to.length()};
- g[h1].pb(h2);
- }
- ll ansr = 0, ansl = 0;
- for(int i = 0; i < n; i++)
- {
- ll cntI = f[has[i]].fst;
- ll ln = f[has[i]].snd;
- queue<ll> q;
- q.push(has[i]);
- u.clear();
- while(!q.empty())
- {
- ll v = q.front();
- u[v] = 1;
- if(f[v].fst < cntI)
- {
- cntI = f[v].fst;
- ln = f[v].snd;
- }
- else if(f[v].fst == cntI && f[v].snd < ln)
- {
- ln = f[v].snd;
- }
- q.pop();
- for(auto& it : g[v])
- {
- if(!u[it])
- {
- q.push(it);
- }
- }
- }
- ansr += cntI;
- ansl += ln;
- }
- cout << ansr << " " << ansl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement