oj.uz

Submission #1077337

# Submission time Handle Problem Language Result Execution time Memory
1077337 2024-08-27T05:31:12 Z komasan Lozinke (COCI17_lozinke) C++14
100 / 100
 25 ms 21984 KB 
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define ll long long

const long long INF = 1e18;
const long long mod = 1e9 + 7;
const int N = 2e5 + 10;

struct TrieNode {

    TrieNode * child[26];
    int cnt;
    int t;

    TrieNode() {
        for (int i = 0; i < 26; i++)
            child[i] = NULL;
        cnt = t = 0;
    }

} * root = new TrieNode();

void update(string s) {
    int n = s.size();
    TrieNode * p = root;

    for (int i = 0; i < n; i++) {
        if (p->child[s[i] - 'a'] == NULL)
            p->child[s[i] - 'a'] = new TrieNode();

        p = p->child[s[i] - 'a'];
    }

    p->cnt++;
}

int get(string s, int tm) {
    int n = s.size();
    TrieNode * p = root;
    int res = 0;

    for (int i = 0; i < n; i++) {
        if (p->child[s[i] - 'a'] == NULL)
            return res;

        p = p->child[s[i] - 'a'];
        if (p->t < tm)
            res += p->cnt;
        p->t = tm;
    }

    return res;
}

string s[N];

void komasan() {
    int n;

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i];

    sort(s + 1, s + n + 1, [&](string a, string b) {
        if (a.size() != b.size())
            return a.size() < b.size();
    
        return a < b;
    });

    ll res = 0;

    for (int i = 1; i <= n; i++) {
        int sz = s[i].size();

        for (int j = 0; j < sz; j++) {
            string x = "";
        
            for (int k = j; k < sz; k++)
                x.push_back(s[i][k]);
            res += get(x, i);
        }

        update(s[i]);
    }

    int cnt = 0;
    for (int i = n; i >= 1; i--) {
        cnt++;
        if (s[i] != s[i + 1])
            cnt = 0;

        res += cnt;
    }

    cout << res;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);



    komasan();
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6756 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 3 ms 7260 KB Output is correct
7 Correct 4 ms 7772 KB Output is correct
8 Correct 4 ms 8536 KB Output is correct
9 Correct 10 ms 9820 KB Output is correct
10 Correct 13 ms 13764 KB Output is correct
11 Correct 13 ms 12124 KB Output is correct
12 Correct 21 ms 20612 KB Output is correct
13 Correct 21 ms 10836 KB Output is correct
14 Correct 22 ms 21080 KB Output is correct
15 Correct 25 ms 21984 KB Output is correct
16 Correct 18 ms 7260 KB Output is correct
17 Correct 20 ms 6940 KB Output is correct
18 Correct 15 ms 6748 KB Output is correct
19 Correct 20 ms 15964 KB Output is correct
20 Correct 15 ms 7260 KB Output is correct