Submission #994080

#TimeUsernameProblemLanguageResultExecution timeMemory
994080vjudge1Rima (COCI17_rima)C++17
14 / 140
1099 ms102624 KiB
#include <bits/stdc++.h> using namespace std; const long long mod = 1LL<<36; const int M = 3e6; long long pw[M]; signed main() { ios::sync_with_stdio(0); cin.tie(NULL),cout.tie(NULL); vector<long long> hashes={256,149,369,(long long)1e6+1,7369,8369}; srand(time(NULL)); long long h=hashes[rand()%6]; pw[0]=1; for (int i=1;i<M;i++) pw[i]=pw[i-1]*h%mod; int n; cin>>n; map<int,vector<string>> mp; for (int i=0;i<n;i++) { string s; cin>>s; mp[s.size()].push_back(s); } map<long long,int> ans; for (auto what:mp) { map<long long,int> temp,cnt; for (auto s:what.second) { long long hs=0; int m=s.size(); for (int i=1;i<m;i++) hs=hs*h+s[i],hs%=mod; int mx; if (ans.find(hs)!=ans.end()) mx=ans[hs]+1; else mx=1; for (int c='a';c<='z';c++) { if (ans.find((hs+pw[m-1]*c%mod)%mod)!=ans.end()) mx=max(mx,ans[(hs+pw[m-1]*c%mod)%mod]+1); } temp[hs]=mx; cnt[hs]++; } for (auto s:what.second) { long long hs=0; int m=s.size(); for (int i=1;i<m;i++) hs=hs*h+s[i],hs%=mod; char c=s[0]; ans[(hs+pw[m-1]*c%mod)%mod]=temp[hs]+cnt[hs]-1; } } int res=0; for (auto i:ans) res=max(res,i.second); cout<<res<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...