Submission #994052

#TimeUsernameProblemLanguageResultExecution timeMemory
994052vjudge1Rima (COCI17_rima)C++17
14 / 140
297 ms134708 KiB
#include<bits/stdc++.h> using namespace std; struct node { node * ch[26] = {NULL}; bool e = false; int dp; int dfs() { //cerr << "I'm" << endl; int ans = 0; int mx[2] = {0}; dp = e; for(int i = 0; i < 26; i++) { if(ch[i] == NULL) continue; // cerr << "---> " << char(i + 'a') << endl; ans = max(ans, ch[i]->dfs()); // cerr << ch[i] -> dp << endl; // cerr << "<---" << char(i + 'a') << endl; if(ch[i] -> e) { mx[1] = max(mx[1], ch[i]->dp - 1); if(mx[0] < mx[1]) swap(mx[0], mx[1]); dp++; } } dp += mx[1]; ans = max(ans, dp + mx[0]); return ans; } }; struct Trie { node * root; Trie() { root = new node(); } void insert(string &s) { node *cur = root; for(int i = s.size() - 1; i >= 0; i--) { int idx = s[i] - 'a'; if(cur -> ch[idx] == NULL) cur -> ch[idx] = new node(); cur = cur -> ch[idx]; } cur -> e = true; } int compute() { return root->dfs(); } } T; int main() { int n; cin >> n; for(int i = 0; i < n; i ++) { string s; cin >> s; T.insert(s); } cout << T.compute() << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...