# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
95363 | teomrn | Lozinke (COCI17_lozinke) | C++14 | 93 ms | 62072 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int p = 37;
const int MOD = 1000000009;
const int SZMAX = 666013 * 13;
const int NMAX = 20010;
struct Hashmap {
int head[SZMAX];
int h[NMAX], val[NMAX], urm[NMAX], cnt = 0;
int NIL = 0;
int end() {
return NIL;
}
void clear() {
while (cnt) {
head[h[cnt] % SZMAX] = 0;
cnt--;
}
}
int & find(int x) {
for (int i = head[x % SZMAX]; i; i = urm[i])
if (h[i] == x)
return val[i];
return NIL;
}
int & operator[](int x) {
int & ans = find(x);
if (ans != NIL)
return ans;
cnt++;
h[cnt] = x;
val[cnt] = 0;
urm[cnt] = cnt;
swap(urm[cnt], head[x % SZMAX]);
return val[cnt];
}
} Hash, act;
void solve()
{
int n;
cin >> n;
long long ans = -n;
vector <string> v(n);
for (auto & i: v) {
cin >> i;
int h = 0;
for (auto j : i)
h = (31LL * h + j - 'a' + 1) % MOD;
Hash[h]++;
}
for (auto s : v) {
act.clear();
for (int beg = 0; beg < s.size(); beg++) {
int h = 0;
for (int i = beg; i < s.size(); i++) {
h = (31LL * h + s[i] - 'a' + 1) % MOD;
if (act.find(h) == act.end()) {
act[h] = 1;
ans += Hash.find(h);
}
}
}
}
cout << ans << '\n';
}
int main()
{
solve();
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |