oj.uz

Submission #341928

# Submission time Handle Problem Language Result Execution time Memory
341928 2020-12-31T13:35:28 Z phathnv Lozinke (COCI17_lozinke) C++11
100 / 100
 23 ms 16376 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct trieTree{
    struct node{
        int last, cnt;
        node* nxt[26];
        node(){
            last = cnt = 0;
            for(int i = 0; i < 26; i++)
                nxt[i] = NULL;
        }
    };

    node *root = new node;
    int insert(const string &s){
        node *cur = root;
        for(char ch : s){
            int id = ch - 'a';
            if (cur -> nxt[id] == NULL)
                cur -> nxt[id] = new node;
            cur = cur -> nxt[id];
        }
        cur -> cnt++;
        return cur -> cnt - 1;
    }
    int count(const string &s, int t){
        int res = 0;
        node *cur = root;
        for(char ch : s){
            int id = ch - 'a';
            if (cur -> nxt[id] == NULL)
                return res;
            cur = cur -> nxt[id];
            if (cur -> last != t){
                res += cur -> cnt;
                cur -> last = t;
            }
        }
        return res;
    }
};

int n;
vector <string> s;
trieTree trie;

void ReadInput(){
    cin >> n;
    s.resize(n);
    for(string &str : s)
        cin >> str;
}

void Solve(){
    sort(s.begin(), s.end(), [](const string &a, const string &b){
            return a.size() < b.size();
         });
    int res = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < (int) s[i].size(); j++)
            res += trie.count(s[i].substr(j), i);
        res += trie.insert(s[i]);
    }
    cout << res;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ReadInput();
    Solve();
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 2 ms 1004 KB Output is correct
7 Correct 2 ms 1644 KB Output is correct
8 Correct 3 ms 2156 KB Output is correct
9 Correct 7 ms 3820 KB Output is correct
10 Correct 11 ms 7788 KB Output is correct
11 Correct 11 ms 6252 KB Output is correct
12 Correct 20 ms 14828 KB Output is correct
13 Correct 16 ms 5376 KB Output is correct
14 Correct 19 ms 15484 KB Output is correct
15 Correct 23 ms 16376 KB Output is correct
16 Correct 14 ms 1644 KB Output is correct
17 Correct 10 ms 1132 KB Output is correct
18 Correct 9 ms 1132 KB Output is correct
19 Correct 18 ms 10348 KB Output is correct
20 Correct 10 ms 1516 KB Output is correct