Submission #95362

#	Time	Username	Problem	Language	Result	Execution time	Memory
95362		teomrn	Lozinke (COCI17_lozinke)	C++14	70 / 100	100 ms	66560 KiB

lozinke

#include <bits/stdc++.h>
using namespace std;

const int p = 37;
const int MOD = 1000000009;
const int SZMAX = 666013 * 137;
const int NMAX = 100010;

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)

lozinke.cpp: In function 'void solve()':
lozinke.cpp:59:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int beg = 0; beg < s.size(); beg++) {
                           ~~~~^~~~~~~~~~
lozinke.cpp:61:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = beg; i < s.size(); i++) {
                               ~~^~~~~~~~~~

• Subtask 1: 70 / 100