oj.uz

Submission #1078645

# Submission time Handle Problem Language Result Execution time Memory
1078645 2024-08-28T02:40:57 Z khactrung1912 Lozinke (COCI17_lozinke) C++14
100 / 100
 133 ms 17488 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 1 ms 860 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1112 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 7 ms 1628 KB Output is correct
7 Correct 9 ms 2248 KB Output is correct
8 Correct 11 ms 2908 KB Output is correct
9 Correct 34 ms 4364 KB Output is correct
10 Correct 56 ms 8528 KB Output is correct
11 Correct 50 ms 6848 KB Output is correct
12 Correct 114 ms 16008 KB Output is correct
13 Correct 106 ms 5716 KB Output is correct
14 Correct 72 ms 16452 KB Output is correct
15 Correct 114 ms 17488 KB Output is correct
16 Correct 133 ms 1616 KB Output is correct
17 Correct 69 ms 1116 KB Output is correct
18 Correct 45 ms 1116 KB Output is correct
19 Correct 88 ms 11092 KB Output is correct
20 Correct 62 ms 1620 KB Output is correct