oj.uz

Submission #95362

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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 3 ms 2296 KB Output is correct
4 Correct 3 ms 1656 KB Output is correct
5 Correct 15 ms 12536 KB Output is correct
6 Correct 16 ms 11896 KB Output is correct
7 Correct 40 ms 30584 KB Output is correct
8 Correct 63 ms 52744 KB Output is correct
9 Correct 59 ms 48252 KB Output is correct
10 Runtime error 96 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 83 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 96 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Correct 74 ms 48208 KB Output is correct
14 Runtime error 91 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 100 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Correct 27 ms 5496 KB Output is correct
17 Correct 20 ms 1272 KB Output is correct
18 Correct 17 ms 1316 KB Output is correct
19 Runtime error 95 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Correct 22 ms 6000 KB Output is correct