제출 #341928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
341928		phathnv	Lozinke (COCI17_lozinke)	C++11	100 / 100	23 ms	16376 KiB

lozinke

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct trieTree{
    struct node{
        int last, cnt;
        node* nxt[26];
        node(){
            last = cnt = 0;
            for(int i = 0; i < 26; i++)
                nxt[i] = NULL;
        }
    };

    node *root = new node;
    int insert(const string &s){
        node *cur = root;
        for(char ch : s){
            int id = ch - 'a';
            if (cur -> nxt[id] == NULL)
                cur -> nxt[id] = new node;
            cur = cur -> nxt[id];
        }
        cur -> cnt++;
        return cur -> cnt - 1;
    }
    int count(const string &s, int t){
        int res = 0;
        node *cur = root;
        for(char ch : s){
            int id = ch - 'a';
            if (cur -> nxt[id] == NULL)
                return res;
            cur = cur -> nxt[id];
            if (cur -> last != t){
                res += cur -> cnt;
                cur -> last = t;
            }
        }
        return res;
    }
};

int n;
vector <string> s;
trieTree trie;

void ReadInput(){
    cin >> n;
    s.resize(n);
    for(string &str : s)
        cin >> str;
}

void Solve(){
    sort(s.begin(), s.end(), [](const string &a, const string &b){
            return a.size() < b.size();
         });
    int res = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < (int) s[i].size(); j++)
            res += trie.count(s[i].substr(j), i);
        res += trie.insert(s[i]);
    }
    cout << res;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ReadInput();
    Solve();
    return 0;
}

• Subtask 1: 100 / 100