Submission #95364

#	Time	Username	Problem	Language	Result	Execution time	Memory
95364		teomrn	Lozinke (COCI17_lozinke)	C++14	75 / 100	92 ms	61896 KiB

lozinke

#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 (stderr)

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 / 100