oj.uz

Submission #95383

# Submission time Handle Problem Language Result Execution time Memory
95383 2019-01-31T07:49:52 Z teomrn Lozinke (COCI17_lozinke) C++14
80 / 100
 401 ms 13408 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long i64;
const int p = 37;
const i64 MOD = 1000000009 * 666013;
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()
{
    map <i64, int> Hash, act;
    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[h];
                }
            }
        }
    }

    cout << ans << '\n';
}

int main()
{
    solve();
    return 0;
}

Compilation message

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

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 9 ms 632 KB Output is correct
7 Correct 14 ms 1272 KB Output is correct
8 Correct 24 ms 1916 KB Output is correct
9 Correct 50 ms 2040 KB Output is correct
10 Correct 141 ms 6136 KB Output is correct
11 Correct 90 ms 3564 KB Output is correct
12 Incorrect 401 ms 13408 KB Output isn't correct
13 Correct 142 ms 2552 KB Output is correct
14 Incorrect 291 ms 12300 KB Output isn't correct
15 Incorrect 331 ms 13280 KB Output isn't correct
16 Correct 118 ms 1144 KB Output is correct
17 Correct 37 ms 1116 KB Output is correct
18 Correct 22 ms 892 KB Output is correct
19 Incorrect 248 ms 7148 KB Output isn't correct
20 Correct 60 ms 1016 KB Output is correct