oj.uz

Submission #238172

# Submission time Handle Problem Language Result Execution time Memory
238172 2020-06-10T05:58:10 Z 74TrAkToR Lozinke (COCI17_lozinke) C++17
100 / 100
 548 ms 17504 KB 
#include<bits/stdc++.h>

using namespace std;

map < string, int > cnt, d;
string s[20005];

main() {
#ifdef HOME
    //freopen("input.txt", "r", stdin);
#endif // HOME
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
    }
    sort(s + 1, s + n + 1, [](string f, string t) {
        return (int)f.size() > (int)t.size();
    });
    for (int i = 1; i <= n; ++i) {
        set < string > Q;
        ans += cnt[s[i]];
        for (int j = 0; j < (int)s[i].size(); ++j) {
            string t = "";
            for (int pos = j; pos < (int)s[i].size(); ++pos) {
                t += s[i][pos];
                Q.insert(t);
            }
        }
        for (auto key : Q) cnt[key]++;
        d[s[i]]++;
    }
    for (auto key : d) ans += key.second * (key.second - 1) / 2;
    cout << ans << '\n';
    return 0;
}

Compilation message

lozinke.cpp:8:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1024 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 6 ms 1024 KB Output is correct
4 Correct 6 ms 1024 KB Output is correct
5 Correct 15 ms 1408 KB Output is correct
6 Correct 24 ms 1456 KB Output is correct
7 Correct 29 ms 2176 KB Output is correct
8 Correct 42 ms 2944 KB Output is correct
9 Correct 109 ms 3220 KB Output is correct
10 Correct 210 ms 8312 KB Output is correct
11 Correct 178 ms 5112 KB Output is correct
12 Correct 465 ms 17480 KB Output is correct
13 Correct 320 ms 3832 KB Output is correct
14 Correct 350 ms 16372 KB Output is correct
15 Correct 548 ms 17504 KB Output is correct
16 Correct 321 ms 1400 KB Output is correct
17 Correct 86 ms 896 KB Output is correct
18 Correct 63 ms 896 KB Output is correct
19 Correct 329 ms 9464 KB Output is correct
20 Correct 158 ms 1400 KB Output is correct