# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
444210 | 2021-07-13T11:09:05 Z | BeanZ | Lozinke (COCI17_lozinke) | C++14 | 297 ms | 15892 KB |
// I_Love_LPL 1y0m3d #include <bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' const int N = 1e5 + 5; long long mod = 2038074751; const int lim = 4e5 + 5; const int lg = 20; const int base = 37; const long double eps = 1e-6; string s[N]; ll h[N], p[N]; map<ll, ll> mem; ll get(ll l, ll r){ return (h[r] - h[l - 1] * p[r - l + 1] + mod * mod) % mod; } bool cmp(string x, string y){ return x.length() < y.length(); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); if (fopen("tests.inp", "r")){ freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ll n; cin >> n; for (int i = 1; i <= n; i++){ cin >> s[i]; } sort(s + 1, s + n + 1, cmp); p[0] = 1; ll ans = 0; for (int i = 1; i <= 10; i++) p[i] = p[i - 1] * base % mod; for (int i = 1; i <= n; i++){ ll x = s[i].length(); for (int j = 1; j <= x; j++){ h[j] = (h[j - 1] * base + (s[i][j - 1] - 'a' + 1)) % mod; } map<ll, ll> eat; for (int j = 1; j <= x; j++){ for (int k = j; k <= x; k++){ if (j == 1 && k == x) continue; if (!eat[get(j, k)]) ans = ans + mem[get(j, k)]; eat[get(j, k)] = 1; } } mem[h[x]]++; } for (auto j : mem){ ans = ans + j.second * (j.second - 1); } cout << ans; } /* Ans: Out: */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 3404 KB | Output is correct |
2 | Correct | 2 ms | 3404 KB | Output is correct |
3 | Correct | 3 ms | 3404 KB | Output is correct |
4 | Correct | 3 ms | 3404 KB | Output is correct |
5 | Correct | 7 ms | 3696 KB | Output is correct |
6 | Correct | 10 ms | 3676 KB | Output is correct |
7 | Correct | 14 ms | 4300 KB | Output is correct |
8 | Correct | 24 ms | 4952 KB | Output is correct |
9 | Correct | 51 ms | 4824 KB | Output is correct |
10 | Correct | 154 ms | 8856 KB | Output is correct |
11 | Correct | 83 ms | 6124 KB | Output is correct |
12 | Correct | 288 ms | 15892 KB | Output is correct |
13 | Correct | 133 ms | 4784 KB | Output is correct |
14 | Incorrect | 238 ms | 14656 KB | Output isn't correct |
15 | Correct | 297 ms | 15640 KB | Output is correct |
16 | Correct | 138 ms | 3500 KB | Output is correct |
17 | Correct | 41 ms | 3404 KB | Output is correct |
18 | Correct | 29 ms | 3452 KB | Output is correct |
19 | Correct | 166 ms | 9512 KB | Output is correct |
20 | Correct | 70 ms | 3540 KB | Output is correct |