Submission #1078161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078161		ntnq	Lozinke (COCI17_lozinke)	C++17	100 / 100	162 ms	17236 KiB

lozinke

#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 (stderr)

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 / 100