oj.uz

Submission #79940

# Submission time Handle Problem Language Result Execution time Memory
79940 2018-10-17T12:57:08 Z luckyboy Lozinke (COCI17_lozinke) C++14
100 / 100
 107 ms 17220 KB 
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxc 1000000007
#define maxn 20005
#define maxm 500005
#define pii pair <int,int>
#define Task "Lozinke"
using namespace std;
int n;
string s[maxn];
long long a[maxn][100],top[maxn],b[maxn],top1,ans;
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen(Task".inp", "r",stdin);
    //freopen(Task".out", "w",stdout);
    cin >> n;
    FOR(i,1,n)
    {
        cin >> s[i];
        int temp = s[i].size();
        FOR(j,0,temp-1)
           {
                long long cur = 0;
                FOR(k,1,temp - j)
                {
                    cur = cur * 27 + (s[i][j+k-1] - 'a' + 1);
                    a[i][++top[i]] = cur;
                }
           }
        sort(a[i] + 1,a[i] + top[i] + 1);
        top[i] = unique(a[i]+1 , a[i] + top[i] + 1) - a[i] - 1;
        b[++top1] = a[i][top[i]];
    }
    sort(b+1,b+top1+1);
    FOR(i,1,n)
    {
        FOR(j,1,top[i])
        {
            ans += upper_bound(b+1,b+top1+1,a[i][j]) - lower_bound(b+1,b+top1+1,a[i][j]);
        }
    }
    cout << ans - n;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1016 KB Output is correct
2 Correct 2 ms 1140 KB Output is correct
3 Correct 3 ms 1368 KB Output is correct
4 Correct 3 ms 1512 KB Output is correct
5 Correct 6 ms 1900 KB Output is correct
6 Correct 7 ms 2292 KB Output is correct
7 Correct 10 ms 2704 KB Output is correct
8 Correct 9 ms 2752 KB Output is correct
9 Correct 43 ms 9208 KB Output is correct
10 Correct 42 ms 9272 KB Output is correct
11 Correct 68 ms 13264 KB Output is correct
12 Correct 64 ms 13280 KB Output is correct
13 Correct 80 ms 17120 KB Output is correct
14 Correct 107 ms 17124 KB Output is correct
15 Correct 84 ms 17124 KB Output is correct
16 Correct 81 ms 17152 KB Output is correct
17 Correct 32 ms 17152 KB Output is correct
18 Correct 32 ms 17180 KB Output is correct
19 Correct 96 ms 17220 KB Output is correct
20 Correct 67 ms 17220 KB Output is correct