oj.uz

Submission #1078161

# Submission time Handle Problem Language Result Execution time Memory
1078161 2024-08-27T13:27:03 Z ntnq Lozinke (COCI17_lozinke) C++17
100 / 100
 162 ms 17236 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
#define reset(mang , giatri) memset(mang , giatri , sizeof(mang))
#define sz size
#define el '\n'

const int N = 2 * 1e4 + 123;
const int mod = 1e9 + 7;

struct node {
    node* child[27];
    int cnt , exist;

    node() {
        reset(child , 0);
        cnt = exist = 0;
    }
};

node* root = new node();

ll ans;

void add(string s) {
    node* u = root;

    for (char ch : s) {
        int k = ch - 'a';

        if (u -> child[k] == 0) u -> child[k] = new node();

        u = u -> child[k];
        u -> cnt++;
    }

    u -> exist++;
}

int n;
string s[N];

bool cmp(string a , string b) {
    if (a.sz() < b.sz()) return true;
    return false;
}

void input() {
    cin >> n;

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

    sort(s + 1 , s + n + 1 , cmp);
}

ll get(string s) {
    node* u = root;

    for (char ch : s) {
        int k = ch - 'a';

        if (u -> child[k] == 0) return 0;

        u = u -> child[k];
    }

    return u -> exist;
}

void solve() {
    ans = 0;

    map<string , int> mp;

    for (int i = 1 ; i <= n ; i++) {
        string t = "";

        mp.clear();

        for (int k = 0 ; k < s[i].sz() ; k++) {
            t = "";
            for (int j = k ; j < s[i].sz() ; j++) {
                t = t + s[i][j];

                if (mp[t] == 0) {
                    ll g = get(t);

                    if (t == s[i]) ans += g;

                    ans += g;
                }

                mp[t] = 1;
            }
        }

        //cout << s[i] << " " << ans << el;

        add(s[i]);
    }

    cout << ans;
}

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

    input();
    solve();

    return 0;
}

Compilation message

lozinke.cpp: In function 'void solve()':
lozinke.cpp:86:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for (int k = 0 ; k < s[i].sz() ; k++) {
      |                          ~~^~~~~~~~~~~
lozinke.cpp:88:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |             for (int j = k ; j < s[i].sz() ; j++) {
      |                              ~~^~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 1 ms 1088 KB Output is correct
4 Correct 1 ms 1200 KB Output is correct
5 Correct 4 ms 1436 KB Output is correct
6 Correct 7 ms 1628 KB Output is correct
7 Correct 8 ms 2364 KB Output is correct
8 Correct 12 ms 2792 KB Output is correct
9 Correct 33 ms 4188 KB Output is correct
10 Correct 54 ms 8532 KB Output is correct
11 Correct 49 ms 6740 KB Output is correct
12 Correct 107 ms 15872 KB Output is correct
13 Correct 102 ms 5428 KB Output is correct
14 Correct 71 ms 16476 KB Output is correct
15 Correct 109 ms 17236 KB Output is correct
16 Correct 162 ms 1432 KB Output is correct
17 Correct 63 ms 860 KB Output is correct
18 Correct 45 ms 1068 KB Output is correct
19 Correct 118 ms 10836 KB Output is correct
20 Correct 62 ms 1352 KB Output is correct