oj.uz

Submission #47732

# Submission time Handle Problem Language Result Execution time Memory
47732 2018-05-06T23:49:26 Z IvanC Savez (COCI15_savez) C++17
120 / 120
 204 ms 20696 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 564 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 616 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 20 ms 11032 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 11032 KB Output is correct
2 Correct 57 ms 11032 KB Output is correct
3 Correct 74 ms 11032 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11032 KB Output is correct
2 Correct 58 ms 11032 KB Output is correct
3 Correct 59 ms 11032 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 11032 KB Output is correct
2 Correct 60 ms 11032 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 11032 KB Output is correct
2 Correct 93 ms 11032 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 11144 KB Output is correct
2 Correct 68 ms 12004 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 13116 KB Output is correct
2 Correct 79 ms 14724 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 14816 KB Output is correct
2 Correct 91 ms 16004 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 17392 KB Output is correct
2 Correct 115 ms 18784 KB Output is correct
3 Correct 204 ms 20696 KB Output is correct