oj.uz

답안 #444207

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
444207 2021-07-13T11:06:26 Z BeanZ Lozinke (COCI17_lozinke) C++14
95 / 100
 316 ms 15996 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 = 123;
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
95.0 / 100.0

# 결과 실행 시간 메모리 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 3456 KB Output is correct
5 Correct 8 ms 3708 KB Output is correct
6 Correct 11 ms 3692 KB Output is correct
7 Correct 15 ms 4300 KB Output is correct
8 Correct 26 ms 4952 KB Output is correct
9 Correct 50 ms 4852 KB Output is correct
10 Correct 117 ms 8880 KB Output is correct
11 Correct 84 ms 6184 KB Output is correct
12 Correct 316 ms 15996 KB Output is correct
13 Correct 142 ms 4760 KB Output is correct
14 Correct 202 ms 14532 KB Output is correct
15 Incorrect 312 ms 15740 KB Output isn't correct
16 Correct 149 ms 3504 KB Output is correct
17 Correct 38 ms 3404 KB Output is correct
18 Correct 30 ms 3452 KB Output is correct
19 Correct 169 ms 9540 KB Output is correct
20 Correct 69 ms 3496 KB Output is correct