제출 #994095

#제출 시각아이디문제언어결과실행 시간메모리
994095vjudge1Rima (COCI17_rima)C++17
0 / 140
559 ms89800 KiB
#include <bits/stdc++.h> using namespace std; const long long mod = 1LL<<58; const int M = 3e6, N = M/30; long long pw[M]; bool not_pr[N]; signed main() { ios::sync_with_stdio(0); cin.tie(NULL),cout.tie(NULL); vector<long long> hashes; for (int i=2;i<N;i++) for (int j=i+i;j<N;j+=i) not_pr[j]=true; for (int i=100;i<N;i++) if (!not_pr[i]) { hashes.push_back(i); i+=100; } srand(time(NULL)); long long h=hashes[rand()%265]; 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); } unordered_map<long long,int> ans; for (auto what:mp) { unordered_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...