oj.uz

Submission #234386

# Submission time Handle Problem Language Result Execution time Memory
234386 2020-05-24T06:45:41 Z kartel Lozinke (COCI17_lozinke) C++14
15 / 100
 449 ms 16248 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];
ll i, n, ans, j, hsh, p[N], l, r;
map <ll, ll> mp;
map <string, ll> 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 6 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 7 ms 3584 KB Output isn't correct
5 Incorrect 15 ms 3840 KB Output isn't correct
6 Incorrect 21 ms 3840 KB Output isn't correct
7 Incorrect 25 ms 4352 KB Output isn't correct
8 Correct 36 ms 4984 KB Output is correct
9 Incorrect 85 ms 5112 KB Output isn't correct
10 Incorrect 182 ms 9336 KB Output isn't correct
11 Incorrect 130 ms 6520 KB Output isn't correct
12 Incorrect 449 ms 16248 KB Output isn't correct
13 Incorrect 254 ms 5260 KB Output isn't correct
14 Incorrect 291 ms 14968 KB Output isn't correct
15 Incorrect 445 ms 16120 KB Output isn't correct
16 Incorrect 286 ms 3840 KB Output isn't correct
17 Correct 78 ms 3584 KB Output is correct
18 Correct 56 ms 3584 KB Output is correct
19 Incorrect 259 ms 9852 KB Output isn't correct
20 Incorrect 142 ms 3840 KB Output isn't correct