oj.uz

답안 #444210

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
444210 2021-07-13T11:09:05 Z BeanZ Lozinke (COCI17_lozinke) C++14
95 / 100
 297 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 = 2038074751;
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
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 3 ms 3404 KB Output is correct
4 Correct 3 ms 3404 KB Output is correct
5 Correct 7 ms 3696 KB Output is correct
6 Correct 10 ms 3676 KB Output is correct
7 Correct 14 ms 4300 KB Output is correct
8 Correct 24 ms 4952 KB Output is correct
9 Correct 51 ms 4824 KB Output is correct
10 Correct 154 ms 8856 KB Output is correct
11 Correct 83 ms 6124 KB Output is correct
12 Correct 288 ms 15892 KB Output is correct
13 Correct 133 ms 4784 KB Output is correct
14 Incorrect 238 ms 14656 KB Output isn't correct
15 Correct 297 ms 15640 KB Output is correct
16 Correct 138 ms 3500 KB Output is correct
17 Correct 41 ms 3404 KB Output is correct
18 Correct 29 ms 3452 KB Output is correct
19 Correct 166 ms 9512 KB Output is correct
20 Correct 70 ms 3540 KB Output is correct