Advertisement
pb_jiang

ABC353E

May 11th, 2024
895
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.18 KB | None | 0 0
  1. #include <assert.h>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #ifndef __DEBUG__
  5. #define dbg(...) 42
  6. #endif
  7. template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
  8.  
  9. using ll = long long;
  10. using pii = pair<int, int>;
  11. using pll = pair<ll, ll>;
  12. using vl = vector<ll>;
  13. using vi = vector<int>;
  14.  
  15. const ll maxn = 3e5 + 3;
  16. ll now = 0;
  17. vl hit(maxn);
  18. ll dict[maxn][26];
  19.  
  20. void insert(const string &str)
  21. {
  22.     ll u = 0;
  23.     for (auto c : str) {
  24.         ll offset = c - 'a';
  25.         if (dict[u][offset] == 0)
  26.             dict[u][offset] = ++now;
  27.         u = dict[u][offset];
  28.         hit[u] += 1;
  29.     }
  30. }
  31. ll get(const string &str)
  32. {
  33.     ll u = 0, ret = 0;
  34.     for (auto c : str) {
  35.         ll offset = c - 'a';
  36.         if (dict[u][offset] == 0)
  37.             return ret;
  38.         u = dict[u][offset];
  39.         ret += hit[u];
  40.     }
  41.     return ret;
  42. }
  43.  
  44. int main(int argc, char **argv)
  45. {
  46.     ll n;
  47.     cin >> n;
  48.     vector<string> vs(n);
  49.     for (auto &x : vs)
  50.         cin >> x;
  51.  
  52.     ll ans = 0;
  53.     for (const auto &x : vs) {
  54.         ll v = get(x);
  55.         dbg(x, v);
  56.         ans += v;
  57.         insert(x);
  58.     }
  59.     cout << ans << endl;
  60.     return 0;
  61. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement