Submission #994065

#TimeUsernameProblemLanguageResultExecution timeMemory
994065vjudge1Rima (COCI17_rima)C++17
56 / 140
1076 ms102060 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int h = 727, mod = 1e9 + 7; const int h1 = 7369, mod1 = 998244353; const int enc = 8369, mod2 = 1LL<<36; const int M = 3e6; int pw[M],pw1[M]; inline int en(int has,int has1) { return (has1*enc+has)%mod2; } signed main() { pw[0]=pw1[0]=1; for (int i=1;i<M;i++) pw[i]=pw[i-1]*h%mod,pw1[i]=pw1[i-1]*h1%mod1; 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); } vector<string> v; for (auto i:mp) for (auto j:i.second) v.push_back(j); reverse(v.begin(),v.end()); unordered_map<int,int> ans; while (!v.empty()) { string s=v.back(); v.pop_back(); int hs=0,hs1=0,m=s.size(); for (int i=1;i<m;i++) { hs=hs*h+s[i],hs1=hs1*h1+s[i]; hs%=mod,hs1%=mod1; } int mx; if (ans.find(en(hs,hs1))!=ans.end()) mx=ans[en(hs,hs1)]+1; else mx=1; for (int c='a';c<='z';c++) { pair<int,int> p={hs,hs1}; p.first+=pw[m-1]*c%mod; p.second+=pw1[m-1]*c%mod1; p.first%=mod,p.second%=mod1; if (ans.find(en(p.first,p.second))!=ans.end()) mx=max(mx,ans[en(p.first,p.second)]+1); } for (int c='a';c<='z';c++) { pair<int,int> p={hs,hs1}; p.first+=pw[m-1]*c%mod; p.second+=pw1[m-1]*c%mod1; p.first%=mod,p.second%=mod1; if (ans.find(en(p.first,p.second))!=ans.end() or c==s[0]) ans[en(p.first,p.second)]=mx; } } int res=0; for (auto i:ans) res=max(res,i.second); cout<<res<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...