Submission #234390

#	Time	Username	Problem	Language	Result	Execution time	Memory
234390		VEGAnn	Lozinke (COCI17_lozinke)	C++14	100 / 100	67 ms	17552 KiB

lozinke

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int N = 20100;
string s[N];
int n, tt = 0;
ll ans = 0;

bool cmp(string _x, string _y){
    return sz(_x) < sz(_y);
}

struct trie{
    trie *next[26];
    int kol;

    trie(): kol(0) {
        for (int i = 0; i < 26; i++)
            next[i] = 0;
    }

    void insert(string &s, int pos){
        if (pos == sz(s)) {
            kol++;
            return;
        }

        int ch = (s[pos] - 'a');

        if (next[ch] == 0)
            next[ch] = new trie();

        next[ch] -> insert(s, pos + 1);
    }
};

trie *root;

unordered_map<trie*, int> mem;

void check(trie* cur, string &s, int pos){
    if (pos == sz(s)) return;

    int ch = (s[pos] - 'a');

    if (cur -> next[ch] == 0)
        return;
    else {
        if (mem[cur -> next[ch]] < tt) {
            ans += cur -> next[ch] -> kol;
            mem[cur -> next[ch]] = tt;
        }

        check(cur -> next[ch], s, pos + 1);
    }
}

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

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

    sort(s, s + n, cmp);

    root = new trie();

    for (int i = 0; i < n; i++){
        tt++;

        for (int j = 0; j < sz(s[i]); j++)
            check(root, s[i], j);

        root -> insert(s[i], 0);
    }

    sort(s, s + n);

    for (int i = 0; i < n; ){
        int j = i;

        while (j < n && s[i] == s[j])
            j++;

        ll cur = j - i;

        ans += cur * (cur - 1ll) / 2ll;

        i = j;
    }

    cout << ans;

    return 0;
}

• Subtask 1: 100 / 100