Advertisement
kostes

Untitled

Mar 20th, 2019
550
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.64 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define fst first
  5. #define snd second
  6. #define all(c) (c).begin(), (c).end()
  7. typedef long long ll;
  8. typedef long double ld;
  9. const ll INF64 = 1e18 + 228;
  10. const int INF32 = 1e9 + 1337;
  11. const int MOD = 1e9 + 7;
  12. map<ll, pair<ll, ll> > f;
  13. map<ll, vector<ll> > g;
  14. vector<string> a;
  15. vector<ll> has;
  16. map<ll, bool> u;
  17. int p = 31;
  18. vector<ll> p_pow;
  19. string lower(string x)
  20. {
  21. for(int i = 0; i < x.length(); i++)
  22. if(x[i] >= 'A' && x[i] <= 'Z') x[i] += 'a' - 'A';
  23. return x;
  24. }
  25. ll hs(string a)
  26. {
  27. ll ans = 0;
  28. for(int i = 0; i < a.size(); i++)
  29. {
  30. ans += (a[i] - 'a') * p_pow[i] % MOD;
  31. }
  32. return ans;
  33. }
  34. int main()
  35. {
  36. #ifndef __WIN32
  37. ifstream cin("input.txt");
  38. ofstream cout("output.txt");
  39. #endif
  40. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  41.  
  42. int n;
  43. cin >> n;
  44. a.resize(n);
  45. has.resize(n);
  46. int n_nn = 500001;
  47. p_pow.resize(n_nn);
  48. p_pow[0] = 1;
  49. for(int i = 1; i < n_nn; i++)
  50. p_pow[i] = p_pow[i - 1] * p % MOD;
  51.  
  52. for(int i = 0; i < n; i++)
  53. {
  54. cin >> a[i];
  55. a[i] = lower(a[i]);
  56. int cntR = 0;
  57. for(int j = 0; j < a[i].length(); j++) cntR += a[i][j] == 'r';
  58. ll hh = hs(a[i]);
  59. has[i] = hh;
  60. f[hh] = {cntR, a[i].length()};
  61. }
  62. int m;
  63. cin >> m;
  64. for(int i = 0; i < m; i++)
  65. {
  66. string from, to;
  67. cin >> from >> to;
  68. from = lower(from);
  69. to = lower(to);
  70. ll h1 = hs(from), h2 = hs(to);
  71. int c1 = 0, c2 = 0;
  72. for(int j = 0; j < from.length(); j++) c1 += from[j] == 'r';
  73. for(int j = 0; j < to.length(); j++) c2 += to[j] == 'r';
  74. f[h1] = {c1, from.length()};
  75. f[h2] = {c2, to.length()};
  76. g[h1].pb(h2);
  77. }
  78. ll ansr = 0, ansl = 0;
  79. for(int i = 0; i < n; i++)
  80. {
  81. ll cntI = f[has[i]].fst;
  82. ll ln = f[has[i]].snd;
  83. queue<ll> q;
  84. q.push(has[i]);
  85. u.clear();
  86. while(!q.empty())
  87. {
  88. ll v = q.front();
  89. u[v] = 1;
  90. if(f[v].fst < cntI)
  91. {
  92. cntI = f[v].fst;
  93. ln = f[v].snd;
  94. }
  95. else if(f[v].fst == cntI && f[v].snd < ln)
  96. {
  97. ln = f[v].snd;
  98. }
  99. q.pop();
  100. for(auto& it : g[v])
  101. {
  102. if(!u[it])
  103. {
  104. q.push(it);
  105. }
  106. }
  107. }
  108. ansr += cntI;
  109. ansl += ln;
  110. }
  111. cout << ansr << " " << ansl;
  112. return 0;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement