oj.uz

Submission #95364

# Submission time Handle Problem Language Result Execution time Memory
95364 2019-01-30T18:42:51 Z teomrn Lozinke (COCI17_lozinke) C++14
75 / 100
 92 ms 61896 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long i64;
const int p = 37;
const int MOD = 1000000009 * 137;
const int SZMAX = 666013 * 13;
const int NMAX = 21010;

struct Hashmap {
    int head[SZMAX];
    int h[NMAX];
    i64 val[NMAX];
    int urm[NMAX], cnt = 0;
    i64 NIL = 0;

    i64 & end() {
        return NIL;
    }
    void clear() {
        while (cnt) {
            head[h[cnt] % SZMAX] = 0;
            cnt--;
        }
    }
    i64 & find(int x) {
        for (int i = head[x % SZMAX]; i; i = urm[i])
            if (h[i] == x)
                return val[i];
        return NIL;
    }
    i64 & operator[](int x) {
        i64 & 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;
    i64 ans = -n;
    vector <string> v(n);

    for (auto & i: v) {
        cin >> i;
        i64 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++) {
            i64 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

lozinke.cpp:6:28: warning: integer overflow in expression [-Woverflow]
 const int MOD = 1000000009 * 137;
                 ~~~~~~~~~~~^~~~~
lozinke.cpp: In function 'void solve()':
lozinke.cpp:62:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int beg = 0; beg < s.size(); beg++) {
                           ~~~~^~~~~~~~~~
lozinke.cpp:64:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = beg; i < s.size(); i++) {
                               ~~^~~~~~~~~~

Subtask #1
75.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 1656 KB Output is correct
4 Correct 3 ms 1528 KB Output is correct
5 Correct 13 ms 10360 KB Output is correct
6 Correct 12 ms 9976 KB Output is correct
7 Correct 27 ms 22648 KB Output is correct
8 Correct 38 ms 31736 KB Output is correct
9 Correct 44 ms 34168 KB Output is correct
10 Incorrect 68 ms 52472 KB Output isn't correct
11 Correct 63 ms 48632 KB Output is correct
12 Incorrect 86 ms 58616 KB Output isn't correct
13 Correct 54 ms 33656 KB Output is correct
14 Incorrect 84 ms 61432 KB Output isn't correct
15 Incorrect 92 ms 61896 KB Output isn't correct
16 Correct 25 ms 4572 KB Output is correct
17 Correct 19 ms 1016 KB Output is correct
18 Correct 26 ms 1144 KB Output is correct
19 Incorrect 89 ms 57016 KB Output isn't correct
20 Correct 21 ms 4984 KB Output is correct