oj.uz

Submission #444217

# Submission time Handle Problem Language Result Execution time Memory
444217 2021-07-13T11:20:40 Z BeanZ Lozinke (COCI17_lozinke) C++14
100 / 100
 386 ms 15972 KB 
// I_Love_LPL 1y0m3d
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 1e5 + 5;
long long mod = 2038074751;
long long mod2 = 1e9 + 7;
const int lim = 4e5 + 5;
const int lg = 20;
const int base = 37;
const int base2 = 311;
const long double eps = 1e-6;
string s[N];
ll h[N], p[N], h2[N], p2[N];
map<pair<ll, ll>, ll> mem;
ll get(ll l, ll r){
    return (h[r] - h[l - 1] * p[r - l + 1] + mod * mod) % mod;
}
ll get2(ll l, ll r){
    return (h2[r] - h2[l - 1] * p2[r - l + 1] + mod2 * mod2) % mod2;
}
bool cmp(string x, string y){
    return x.length() < y.length();
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("tests.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> s[i];
    }
    sort(s + 1, s + n + 1, cmp);
    p[0] = 1;
    p2[0] = 1;
    ll ans = 0;
    for (int i = 1; i <= 10; i++) p[i] = p[i - 1] * base % mod;
    for (int i = 1; i <= 10; i++) p2[i] = p2[i - 1] * base2 % mod2;
    for (int i = 1; i <= n; i++){
        ll x = s[i].length();
        for (int j = 1; j <= x; j++){
            h[j] = (h[j - 1] * base + (s[i][j - 1] - 'a' + 1)) % mod;
            h2[j] = (h2[j - 1] * base2 + (s[i][j - 1] - 'a' + 1)) % mod2;
        }
        map<pair<ll, ll>, ll> eat;
        for (int j = 1; j <= x; j++){
            for (int k = j; k <= x; k++){
                if (j == 1 && k == x) continue;
                if (!eat[{get(j, k), get2(j, k)}]) ans = ans + mem[{get(j, k), get2(j, k)}];
                eat[{get(j, k), get2(j, k)}] = 1;
            }
        }
        mem[{h[x], h2[x]}]++;
    }
    for (auto j : mem){
        ans = ans + j.second * (j.second - 1);
    }
    cout << ans;
}
/*
Ans:

Out:
*/

Compilation message

lozinke.cpp: In function 'int main()':
lozinke.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 3 ms 3404 KB Output is correct
4 Correct 4 ms 3404 KB Output is correct
5 Correct 8 ms 3712 KB Output is correct
6 Correct 15 ms 3716 KB Output is correct
7 Correct 16 ms 4300 KB Output is correct
8 Correct 27 ms 4896 KB Output is correct
9 Correct 67 ms 4796 KB Output is correct
10 Correct 171 ms 8876 KB Output is correct
11 Correct 94 ms 6160 KB Output is correct
12 Correct 382 ms 15972 KB Output is correct
13 Correct 165 ms 4840 KB Output is correct
14 Correct 248 ms 14628 KB Output is correct
15 Correct 386 ms 15684 KB Output is correct
16 Correct 172 ms 3524 KB Output is correct
17 Correct 54 ms 3456 KB Output is correct
18 Correct 41 ms 3452 KB Output is correct
19 Correct 190 ms 9536 KB Output is correct
20 Correct 85 ms 3472 KB Output is correct