#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7, N = 3e5;
#define int long long
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=200;i<N;i++)
if (!not_pr[i])
{
hashes.push_back(i);
i+=100;
}
srand(time(NULL));
long long h=hashes[rand()%1372];
int n;
cin>>n;
map<int,vector<string>> mp;
set<int> se;
for (int i=0;i<n;i++)
{
string s;
cin>>s;
reverse(s.begin(),s.end());
mp[s.size()].push_back(s);
int m=s.size(),hs=0;
for (int j=0;j<m;j++)
hs=(hs*h+s[j])%mod;
se.insert(hs);
}
vector<string> v;
for (auto i:mp)
for (auto j:i.second)
v.push_back(j);
reverse(v.begin(),v.end());
map<int,int> ans;
while (!v.empty())
{
string s=v.back();
v.pop_back();
int m=s.size();
int hs=0,mx=0;
for (int i=0;i<m-1;i++)
hs=(hs*h+s[i])%mod;
if (ans.find(hs)!=ans.end())
mx=ans[hs];
for (int c='a';c<='z';c++)
{
if (se.find((hs*h+c)%mod)!=se.end())
mx++;
}
ans[(hs*h+s[m-1])%mod]=mx;
}
int res=0;
for (auto i:ans)
res=max(res,i.second);
cout<<res<<endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
604 KB |
Output is correct |
| 2 |
Correct |
2 ms |
604 KB |
Output is correct |
| 3 |
Correct |
3 ms |
748 KB |
Output is correct |
| 4 |
Execution timed out |
1089 ms |
81512 KB |
Time limit exceeded |
| 5 |
Correct |
44 ms |
9808 KB |
Output is correct |
| 6 |
Incorrect |
13 ms |
3488 KB |
Output isn't correct |
| 7 |
Incorrect |
12 ms |
3156 KB |
Output isn't correct |
| 8 |
Incorrect |
10 ms |
2760 KB |
Output isn't correct |
| 9 |
Incorrect |
62 ms |
12360 KB |
Output isn't correct |
| 10 |
Incorrect |
10 ms |
2872 KB |
Output isn't correct |
