#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
const int mod = 1e9 + 7;
const int mod1 = 1e9 + 409;
const int mod2 = 1e9 + 433;
typedef pair<int, int> pi;
lint get_hash(string &s, int st, int ed){
lint h1 = 0;
lint h2 = 0;
for(int i=st; i<ed; i++){
h1 = h1 * 257 + s[i];
h2 = h2 * 257 + s[i];
h1 %= mod1;
h2 %= mod2;
}
return h1 * mod2 + h2;
}
int n, vtx[500005], par[500005], cst[500005];
string s[500005];
char buf[3000005];
map<lint, int> hsh[3000005];
vector<int> gph[500005];
int lcp(string &a, string &b){
for(int i=0; i<a.size(); i++){
if(a[i] != b[i]) return i;
}
return a.size();
}
bool vis[500005];
int dp[500005], check[500005];
pi dfs(int x, int p){
vis[x] = 1;
pi ret(0, x);
for(auto &i : gph[x]){
if(i != p){
ret = max(ret, dfs(i, x));
}
}
ret.first += cst[x];
return ret;
}
int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%s", buf);
s[i] = buf;
reverse(s[i].begin(), s[i].end());
}
sort(s+1, s+n+1, [&](const string &a, const string &b){
return make_pair(a.size(), a) < make_pair(b.size(), b);
});
for(int i=1; i<=n; i++){
hsh[s[i].size()][get_hash(s[i], 0, s[i].size())] = i;
}
for(int i=1; i<=n; ){
int p = hsh[s[i].size() - 1][get_hash(s[i], 0, s[i].size() - 1)];
if(p > 0){
gph[vtx[p]].push_back(i);
gph[i].push_back(vtx[p]);
check[i] = 1;
}
int e = i;
while(e <= n && s[e].size() == s[i].size() && lcp(s[i], s[e]) >= s[i].size() - 1) e++;
for(int j=i; j<e; j++){
vtx[j] = i;
cst[j] = e - i;
}
i = e;
}
int ans = 0;
for(int i=n; i; i--){
if(vtx[i] != i) continue;
vector<int> v;
for(auto &j : gph[i]){
v.push_back(dp[j]);
}
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
if(v.size() >= 2) ans = max(ans, v[0] + v[1] + check[i] + cst[i]);
if(v.size() >= 1) ans = max(ans, v[0] + check[i] + cst[i]);
dp[i] = (v.size() ? v[0] : 0) + cst[i];
}
cout << ans << endl;
}
Compilation message
rima.cpp: In function 'int lcp(std::__cxx11::string&, std::__cxx11::string&)':
rima.cpp:29:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<a.size(); i++){
^
rima.cpp: In function 'int main()':
rima.cpp:71:65: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(e <= n && s[e].size() == s[i].size() && lcp(s[i], s[e]) >= s[i].size() - 1) e++;
^
rima.cpp:51:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
rima.cpp:53:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", buf);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
29 ms |
183184 KB |
Output is correct |
| 2 |
Correct |
43 ms |
183184 KB |
Output is correct |
| 3 |
Correct |
66 ms |
183184 KB |
Output is correct |
| 4 |
Correct |
786 ms |
225424 KB |
Output is correct |
| 5 |
Correct |
119 ms |
186220 KB |
Output is correct |
| 6 |
Correct |
59 ms |
184204 KB |
Output is correct |
| 7 |
Correct |
73 ms |
184084 KB |
Output is correct |
| 8 |
Correct |
63 ms |
184000 KB |
Output is correct |
| 9 |
Correct |
203 ms |
187520 KB |
Output is correct |
| 10 |
Correct |
63 ms |
184016 KB |
Output is correct |
