oj.uz

Submission #144786

# Submission time Handle Problem Language Result Execution time Memory
144786 2019-08-17T17:59:24 Z alexandra_udristoiu Lozinke (COCI17_lozinke) C++14
100 / 100
 82 ms 47608 KB 
#include<iostream>
#include<cstring>
using namespace std;
int n, i, sol, m, j;
char s[15];
struct trie{
    int nr, nrt, lst;
    trie *f[26];
    trie(){
        nr = nrt = lst = 0;
        for(int i = 0; i < 26; i++){
            f[i] = NULL;
        }
    }
};
trie *r;
void adaug(trie *r, char *s, int ok){
    if(*s == 0){
        if(ok == 1){
            sol += r->nr - 1;
            r->nrt++;
        }
        return;
    }
    if(r->f[*s - 'a'] == NULL){
        r->f[*s - 'a'] = new trie;
    }
    if(r->f[*s - 'a']->lst != i){
        r->f[*s - 'a']->lst = i;
        r->f[*s - 'a']->nr++;
        sol += r->f[*s - 'a']->nrt;
    }
    adaug(r->f[*s - 'a'], s + 1, ok);
}
int main(){
    r = new trie;
    cin>> n;
    for(i = 1; i <= n; i++){
        cin>> s + 1;
        m = strlen(s + 1);
        adaug(r, s + 1, 1);
        for(j = 2; j <= m; j++){
            adaug(r, s + j, 0);
        }
    }
    cout<< sol;
}

Compilation message

lozinke.cpp: In function 'int main()':
lozinke.cpp:39:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin>> s + 1;
               ~~^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 4 ms 1400 KB Output is correct
6 Correct 5 ms 1400 KB Output is correct
7 Correct 7 ms 3576 KB Output is correct
8 Correct 10 ms 6136 KB Output is correct
9 Correct 16 ms 5752 KB Output is correct
10 Correct 37 ms 20984 KB Output is correct
11 Correct 25 ms 10748 KB Output is correct
12 Correct 81 ms 47608 KB Output is correct
13 Correct 33 ms 5724 KB Output is correct
14 Correct 65 ms 42404 KB Output is correct
15 Correct 82 ms 46712 KB Output is correct
16 Correct 32 ms 992 KB Output is correct
17 Correct 22 ms 504 KB Output is correct
18 Correct 19 ms 504 KB Output is correct
19 Correct 49 ms 23288 KB Output is correct
20 Correct 20 ms 888 KB Output is correct