467D - Fedor and Essay - CodeForces Solution

#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
#define f first
#define s second
const ll N = 1e6 + 9, M = 100 , mod = 1e9 + 7 , OO = 2 * 1e9 , OOLL = 6 * 1e18;
clock_t START_TIME = clock();
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif
void judge();
void end_clock();
map<string , int> id;
int a[N];
pair<ll,ll> p[N] , dp[N]; // { R's , length }
vector<int> adj[N];
vector<pair<pair<ll,ll> , ll>> MIN;
int n , m;
void TOlower(string &s){ for(auto &ch : s) ch = tolower(ch);}
pair<ll,ll> cal(string &s){
    pair<ll,ll> x = {0 , s.size()};
    for(auto &ch : s) x.f += (ch == 'r');
    return x;
}
void dfs(int u , pair<ll,ll> cur){
    auto &ret = dp[u];
    if(~ret.f) return;
    cur = min(cur , p[u]);
    ret = cur;
    for(auto &v : adj[u]) dfs(v , cur);
}
void sol(){
    int cnt = 0;
    memset(dp , -1 , sizeof(dp));
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        string s; cin >> s;
        TOlower(s);
        auto &cur_id = id[s];
        if(!cur_id) cur_id = ++cnt , a[i] = cur_id , p[cur_id] = cal(s);
        else a[i] = cur_id;
    }
    cin >> m;
    for (int i = 0; i < m; ++i)
    {
        string s , t; cin >> s >> t;
        TOlower(s); TOlower(t);
        auto &id_ss = id[s] , &id_tt = id[t];
        if(!id_ss) id_ss = ++cnt , p[id_ss] = cal(s);
        if(!id_tt) id_tt = ++cnt , p[id_tt] = cal(t);
        adj[id_tt].emplace_back(id_ss);
        MIN.emplace_back(p[id_ss] , id_ss);
        MIN.emplace_back(p[id_tt] , id_tt);
    }
    sort(MIN.begin() , MIN.end());
    for(auto &i : MIN) dfs(i.s , make_pair(OO , OO) );
    pair<ll,ll> ret = {0 , 0};
    for(int i = 0 ; i < n ; i++)
    {
        if(dp[a[i]].f == -1) dfs(a[i] , make_pair(OO ,OO));
        auto &x = dp[a[i]];
        ret.f += x.f; ret.s += x.s;
    }
    cout << ret.f << " " << ret.s;
}
int main(){
    judge();
    int q = 1;
   // cin >> q;
    while (q--){
        sol();
     //   cout << '\n';
    }
    end_clock();
}
void judge(){
    ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(0);
    #ifndef ONLINE_JUDGE
     freopen("in.txt", "r", stdin);
     freopen("out.txt", "w", stdout);
     freopen("error.txt", "w", stderr);
    #endif
}
void end_clock(){
  #ifndef ONLINE_JUDGE
    clock_t START_TIME = clock();
    cout << '\n' << "// Time taken = " << fixed << setprecision(5) << (clock( ) - START_TIME) * 1e3 / CLOCKS_PER_SEC;
 #endif
}