oj.uz

Submission #444208

# Submission time Handle Problem Language Result Execution time Memory
444208 2021-07-13T11:07:00 Z BeanZ Lozinke (COCI17_lozinke) C++14
90 / 100
 343 ms 15992 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 = 2038074743;
const int lim = 4e5 + 5;
const int lg = 20;
const int base = 37;
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
90.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 3660 KB Output is correct
6 Correct 10 ms 3660 KB Output is correct
7 Correct 14 ms 4304 KB Output is correct
8 Correct 23 ms 4968 KB Output is correct
9 Correct 50 ms 4748 KB Output is correct
10 Correct 115 ms 8856 KB Output is correct
11 Correct 80 ms 6188 KB Output is correct
12 Correct 343 ms 15992 KB Output is correct
13 Correct 136 ms 4728 KB Output is correct
14 Incorrect 226 ms 14612 KB Output isn't correct
15 Incorrect 300 ms 15684 KB Output isn't correct
16 Correct 138 ms 3568 KB Output is correct
17 Correct 43 ms 3432 KB Output is correct
18 Correct 30 ms 3452 KB Output is correct
19 Correct 188 ms 9500 KB Output is correct
20 Correct 71 ms 3464 KB Output is correct