Submission #369724

#TimeUsernameProblemLanguageResultExecution timeMemory
369724Atill83Rima (COCI17_rima)C++14
140 / 140
408 ms145004 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define endl '\n' using namespace std; const long long INF = (long long) 1e18; const int mod = (int) 1e9+7; const int MAXN = (int) 5e5+5; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; ll n; struct node { bool mark; int chain, ans; node * p[26]; node(){ chain = 0; mark = 0; ans = 0; for(int i = 0; i < 26; i++) p[i] = NULL; } }; typedef node * pn; pn root = new node; void add(string & s){ reverse(s.begin(), s.end()); pn cur = root; for(char c: s){ if(cur->p[c - 'a'] == NULL){ cur->p[c - 'a'] = new node; } cur = cur->p[c - 'a']; } cur->mark = 1; } void dp(pn cur){ vector<int> chain; int ths = 0; for(int i = 0; i < 26; i++){ if(cur->p[i] != NULL){ dp(cur->p[i]); cur->ans = max(cur->ans, cur->p[i]->ans); cur->ans = max(cur->ans, cur->p[i]->chain); if(cur->p[i]->mark){ ths++; chain.push_back(cur->p[i]->chain); } } } sort(chain.begin(), chain.end()); if(chain.size() >= 2){ cur->ans = max(cur->ans, chain.back() + chain[chain.size() - 2] + ths + cur->mark); } if(!chain.empty()){ cur->chain = max(cur->chain, chain.back() + ths); } cur->ans = max(cur->ans, cur->chain + cur->mark); } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); #ifdef Local freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin); freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout); #endif cin>>n; for(int i = 0; i < n; i++){ string s; cin>>s; add(s); } dp(root); cout<<root->ans<<endl; #ifdef Local cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "; #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...