oj.uz

Submission #116926

# Submission time Handle Problem Language Result Execution time Memory
116926 2019-06-14T05:51:22 Z FutymyClone Lozinke (COCI17_lozinke) C++14
70 / 100
 648 ms 65536 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);
                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
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 6 ms 2176 KB Output is correct
4 Correct 7 ms 2816 KB Output is correct
5 Correct 30 ms 13440 KB Output is correct
6 Correct 42 ms 12536 KB Output is correct
7 Correct 73 ms 35704 KB Output is correct
8 Correct 113 ms 62872 KB Output is correct
9 Correct 243 ms 59052 KB Output is correct
10 Runtime error 172 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 268 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 155 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Correct 648 ms 58892 KB Output is correct
14 Runtime error 176 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 172 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Correct 586 ms 6480 KB Output is correct
17 Correct 478 ms 1272 KB Output is correct
18 Correct 311 ms 1148 KB Output is correct
19 Runtime error 244 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Correct 291 ms 5800 KB Output is correct