oj.uz

Submission #444203

# Submission time Handle Problem Language Result Execution time Memory
444203 2021-07-13T10:57:51 Z BeanZ Lozinke (COCI17_lozinke) C++14
85 / 100
 320 ms 15892 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 = 1e9 + 7;
const int lim = 4e5 + 5;
const int lg = 20;
const int base = 311;
const long double eps = 1e-6;
string s[N];
ll h[N], p[N];
map<ll, ll> mem;
ll get(ll l, ll r){
    return (h[r] - h[l - 1] * p[r - l + 1] + mod * mod) % mod;
}
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;
    ll ans = 0;
    for (int i = 1; i <= 10; i++) p[i] = p[i - 1] * base % mod;
    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;
        }
        map<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)]) ans = ans + mem[get(j, k)];
                eat[get(j, k)] = 1;
            }
        }
        mem[h[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:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
85.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 2 ms 3404 KB Output is correct
4 Correct 3 ms 3404 KB Output is correct
5 Correct 7 ms 3644 KB Output is correct
6 Correct 11 ms 3660 KB Output is correct
7 Correct 15 ms 4232 KB Output is correct
8 Correct 25 ms 4868 KB Output is correct
9 Correct 51 ms 4756 KB Output is correct
10 Correct 118 ms 8900 KB Output is correct
11 Correct 84 ms 6084 KB Output is correct
12 Incorrect 310 ms 15892 KB Output isn't correct
13 Correct 146 ms 4844 KB Output is correct
14 Incorrect 209 ms 14504 KB Output isn't correct
15 Incorrect 320 ms 15832 KB Output isn't correct
16 Correct 150 ms 3512 KB Output is correct
17 Correct 38 ms 3404 KB Output is correct
18 Correct 29 ms 3456 KB Output is correct
19 Correct 174 ms 9504 KB Output is correct
20 Correct 71 ms 3484 KB Output is correct