oj.uz

Submission #234385

# Submission time Handle Problem Language Result Execution time Memory
234385 2020-05-24T06:44:54 Z kartel Lozinke (COCI17_lozinke) C++14
15 / 100
 422 ms 13048 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define N +100500
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;

string s[N];
int i, n, ans, j, hsh, p[N], l, r;
map <int, int> mp;
map <string, int> mk;

ll mult(ll x, ll y) {return (x * y) % M;}
ll sm(ll x, ll y) {return (x + y) % M;}

int main()
{
    srand(time(0));
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

//    in("input.txt");
//    out("output.txt");

    cin >> n;

    p[0] = 1;
    for (i = 1; i <= n; i++) p[i] = mult(p[i - 1], 31);

    for (i = 1; i <= n; i++)
    {
        cin >> s[i];

        hsh = 0;

        for (j = 0; j < sz(s[i]); j++)
                hsh = sm(hsh, mult(s[i][j] - 'a' + 1, p[j]));

        mp[hsh]++;
    }

    for (i = 1; i <= n; i++)
    {
        mk.clear();
        for (l = 0; l < sz(s[i]); l++)
        {
            hsh = 0;
            string t = "";
            for (r = l; r < sz(s[i]); r++)
            {
                t += s[i][r];
                if (mk[t]) continue;

                mk[t] = 1;

                hsh = sm(hsh, mult(s[i][r] - 'a' + 1, p[r - l]));
                ans += mp[hsh];
            }
        }
    }

    cout << ans - n;
}

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 3456 KB Output isn't correct
2 Incorrect 6 ms 3456 KB Output isn't correct
3 Incorrect 7 ms 3456 KB Output isn't correct
4 Incorrect 8 ms 3584 KB Output isn't correct
5 Incorrect 14 ms 3712 KB Output isn't correct
6 Incorrect 20 ms 3712 KB Output isn't correct
7 Incorrect 23 ms 4224 KB Output isn't correct
8 Correct 35 ms 4728 KB Output is correct
9 Incorrect 83 ms 4728 KB Output isn't correct
10 Incorrect 171 ms 7860 KB Output isn't correct
11 Incorrect 131 ms 5756 KB Output isn't correct
12 Incorrect 407 ms 12976 KB Output isn't correct
13 Incorrect 244 ms 4916 KB Output isn't correct
14 Incorrect 270 ms 12024 KB Output isn't correct
15 Incorrect 422 ms 13048 KB Output isn't correct
16 Incorrect 277 ms 3712 KB Output isn't correct
17 Correct 88 ms 3832 KB Output is correct
18 Correct 57 ms 3584 KB Output is correct
19 Incorrect 240 ms 8260 KB Output isn't correct
20 Incorrect 136 ms 3712 KB Output isn't correct