Submission #1077337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077337		komasan	Lozinke (COCI17_lozinke)	C++14	100 / 100	25 ms	21984 KiB

lozinke

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