oj.uz

Submission #95363

# Submission time Handle Problem Language Result Execution time Memory
95363 2019-01-30T18:35:34 Z teomrn Lozinke (COCI17_lozinke) C++14
75 / 100
 93 ms 62072 KB 
#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

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
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 1784 KB Output is correct
4 Correct 3 ms 1656 KB Output is correct
5 Correct 12 ms 9848 KB Output is correct
6 Correct 13 ms 9464 KB Output is correct
7 Correct 27 ms 22264 KB Output is correct
8 Correct 39 ms 31736 KB Output is correct
9 Correct 42 ms 32348 KB Output is correct
10 Incorrect 68 ms 52444 KB Output isn't correct
11 Correct 60 ms 45048 KB Output is correct
12 Incorrect 87 ms 58616 KB Output isn't correct
13 Correct 56 ms 33144 KB Output is correct
14 Incorrect 85 ms 61476 KB Output isn't correct
15 Incorrect 93 ms 62072 KB Output isn't correct
16 Correct 25 ms 4600 KB Output is correct
17 Correct 20 ms 1144 KB Output is correct
18 Correct 16 ms 1016 KB Output is correct
19 Incorrect 82 ms 56696 KB Output isn't correct
20 Correct 20 ms 5112 KB Output is correct