oj.uz

Submission #116927

# Submission time Handle Problem Language Result Execution time Memory
116927 2019-06-14T05:53:02 Z FutymyClone Lozinke (COCI17_lozinke) C++14
100 / 100
 362 ms 43896 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e4 + 5;

int n, ans = 0;
map <string, bitset <N> > mm;
string a[N];
bitset <N> temp;
map <string, int> mm2;

bool cmp (string s, string t) {
    if (s.length() != t.length()) return s.length() < t.length();
    return s < t;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], mm2[a[i]]++;
    sort(a + 1, a + n + 1, cmp);
    //for (int i = 1; i <= n; i++) cout << a[i] << "\n";
    for (int i = 1; i <= n; i++) {
        temp.reset();
        for (int l = 0; l < a[i].length(); l++) {
            for (int r = 0; r < a[i].length(); r++) {
                string t = a[i].substr(l, r - l + 1);
                if (mm.count(t)) temp |= mm[t];
            }
        }

        ans += temp.count();
        mm[a[i]].set(i);
    }

    for (auto i: mm2) ans += i.second * (i.second - 1) / 2;
    cout << ans;
    return 0;
}

Compilation message

lozinke.cpp: In function 'int main()':
lozinke.cpp:26:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int l = 0; l < a[i].length(); l++) {
                         ~~^~~~~~~~~~~~~~~
lozinke.cpp:27:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int r = 0; r < a[i].length(); r++) {
                             ~~^~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1024 KB Output is correct
2 Correct 3 ms 1024 KB Output is correct
3 Correct 3 ms 1280 KB Output is correct
4 Correct 5 ms 1664 KB Output is correct
5 Correct 16 ms 2944 KB Output is correct
6 Correct 21 ms 4224 KB Output is correct
7 Correct 29 ms 5112 KB Output is correct
8 Correct 21 ms 4480 KB Output is correct
9 Correct 180 ms 16260 KB Output is correct
10 Correct 121 ms 18316 KB Output is correct
11 Correct 310 ms 25464 KB Output is correct
12 Correct 323 ms 27348 KB Output is correct
13 Correct 331 ms 34944 KB Output is correct
14 Correct 362 ms 43896 KB Output is correct
15 Correct 257 ms 35704 KB Output is correct
16 Correct 173 ms 4856 KB Output is correct
17 Correct 77 ms 1016 KB Output is correct
18 Correct 97 ms 1020 KB Output is correct
19 Correct 314 ms 32976 KB Output is correct
20 Correct 218 ms 5752 KB Output is correct