Submission #47732

#	Time	Username	Problem	Language	Result	Execution time	Memory
47732		IvanC	Savez (COCI15_savez)	C++17	120 / 120	204 ms	20696 KiB

savez

#include <bits/stdc++.h>
using namespace std;
typedef pair<char,char> dupla;
map<dupla,int> vazio;
vector<map<dupla,int> > Trie;
vector<int> fim,qtd;
int N,TriePtr;

int main(){
    fim.push_back(0);
    qtd.push_back(0);
    Trie.push_back(vazio);
    cin >> N;
    int best = 0;
    for(int palavra = 1;palavra<=N;palavra++){
        string s;
        cin >> s;
        int melhor = 1;
        int atual = 0;
        for(int i = 0, j = s.size()-1;j>=0;i++,j--){
            if(fim[atual]) melhor = max(melhor,qtd[atual]+1);
            dupla davez = dupla(s[i],s[j]);
            if(Trie[atual].count(davez)){
                atual = Trie[atual][davez];
            }
            else{
                break;
            }
        }
        if(fim[atual]) melhor = max(melhor,qtd[atual]+1);
        best = max(best,melhor);
        atual = 0;
        for(int i = 0, j = s.size()-1;j>=0;i++,j--){
            dupla davez = dupla(s[i],s[j]);
            if(Trie[atual].count(davez)){
                atual = Trie[atual][davez];
            }
            else{
                Trie[atual][davez] = ++TriePtr;
                fim.push_back(0);
                qtd.push_back(0);
                Trie.push_back(vazio);
                atual = TriePtr;
            }
        }
        fim[atual] = 1;
        qtd[atual] = max(qtd[atual],melhor);
    }
    cout << best << endl;
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12