#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
using namespace std;
const int MAXN = (int) 3e5;
const int B = 53;
char str[MAXN + 1];
ull pw[MAXN + 1], hsh[MAXN + 1];
inline ull get_hsh(int l, int r) {
return hsh[r] - hsh[l - 1] * pw[r - l + 1];
}
int len[2 * MAXN + 5];
inline void manacher(int n) {
vector <char> aux(2 * n + 5);
int i, sz = 0;
for(i = 1; i <= n; i++) {
aux[++sz] = '*';
aux[++sz] = str[i];
}
aux[++sz] = '*';
int p = 0;
for(i = 1; i <= sz; i++) {
if(p + len[p] >= i) {
len[i] = min(len[2 * p - i], p + len[p] - i);
}
while(i - len[i] > 0 && i + len[i] <= sz && aux[i - len[i]] == aux[i + len[i]]) {
len[i]++;
}
if(i + len[i] > p + len[p]) {
p = i;
}
}
}
map <ull, int> mp;
struct Trie {
vector <int> sons;
int lvl, sz;
};
vector <Trie> v;
void dfs(int nod, ll &ans) {
for(auto it : v[nod].sons) {
dfs(it, ans);
v[nod].sz += v[it].sz;
}
ans = max(ans, 1LL * v[nod].lvl * v[nod].sz);
//cerr << nod << " " << v[nod].lvl << " " << v[nod].sz << "\n";
}
int main() {
//ifstream cin("B.in");
//ofstream cout("B.out");
int i;
ios::sync_with_stdio(false);
cin >> str + 1;
int n = strlen(str + 1);
manacher(n);
pw[0] = 1;
for(i = 1; i <= n; i++) {
pw[i] = pw[i - 1] * B;
hsh[i] = hsh[i - 1] * B + str[i] - 'a' + 1;
}
int id = 0;
mp[0] = ++id;
v.resize(2);
v[1].lvl = 0;
for(i = 2; i <= 2 * n; i++) {
int last = 0, j;
for(j = len[i] / 2; j >= 1; j--) {
ull cur = get_hsh(i / 2 - j + 1, i / 2 + j - (1 - i % 2));
int l = 2 * j - (1 - i % 2);
bool ok = 0;
if(mp[cur] == 0) {
//cerr << i / 2 - j + 1 << " " << i / 2 + j - (1 - i % 2) << "\n";
ok = 1;
mp[cur] = ++id;
Trie aux;
aux.lvl = l;
aux.sz = 0;
v.push_back(aux);
}
if(last != 0) {
v[mp[cur]].sons.push_back(last);
}
else {
v[mp[cur]].sz++;
}
last = mp[cur];
if(!ok) {
break;
}
}
if(j == 0 && last > 0) {
v[1].sons.push_back(last);
}
}
ll ans = 0;
dfs(1, ans);
cout << ans;
//cin.close();
//cout.close();
return 0;
}
Compilation message
palindrome.cpp: In function 'int main()':
palindrome.cpp:68:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
cin >> str + 1;
~~~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
516 KB |
Output is correct |
3 |
Correct |
2 ms |
516 KB |
Output is correct |
4 |
Correct |
2 ms |
616 KB |
Output is correct |
5 |
Correct |
2 ms |
616 KB |
Output is correct |
6 |
Correct |
2 ms |
620 KB |
Output is correct |
7 |
Correct |
2 ms |
624 KB |
Output is correct |
8 |
Correct |
2 ms |
628 KB |
Output is correct |
9 |
Correct |
2 ms |
632 KB |
Output is correct |
10 |
Correct |
2 ms |
636 KB |
Output is correct |
11 |
Correct |
2 ms |
640 KB |
Output is correct |
12 |
Correct |
2 ms |
644 KB |
Output is correct |
13 |
Correct |
2 ms |
668 KB |
Output is correct |
14 |
Correct |
2 ms |
800 KB |
Output is correct |
15 |
Correct |
2 ms |
800 KB |
Output is correct |
16 |
Correct |
2 ms |
800 KB |
Output is correct |
17 |
Correct |
2 ms |
800 KB |
Output is correct |
18 |
Correct |
2 ms |
800 KB |
Output is correct |
19 |
Correct |
2 ms |
800 KB |
Output is correct |
20 |
Correct |
2 ms |
800 KB |
Output is correct |
21 |
Correct |
2 ms |
800 KB |
Output is correct |
22 |
Correct |
2 ms |
800 KB |
Output is correct |
23 |
Correct |
2 ms |
800 KB |
Output is correct |
24 |
Correct |
2 ms |
800 KB |
Output is correct |
25 |
Correct |
2 ms |
800 KB |
Output is correct |
26 |
Correct |
3 ms |
800 KB |
Output is correct |
27 |
Correct |
2 ms |
868 KB |
Output is correct |
28 |
Correct |
2 ms |
868 KB |
Output is correct |
29 |
Correct |
2 ms |
868 KB |
Output is correct |
30 |
Correct |
2 ms |
868 KB |
Output is correct |
31 |
Correct |
2 ms |
868 KB |
Output is correct |
32 |
Correct |
2 ms |
868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
892 KB |
Output is correct |
2 |
Correct |
3 ms |
896 KB |
Output is correct |
3 |
Correct |
3 ms |
900 KB |
Output is correct |
4 |
Correct |
3 ms |
948 KB |
Output is correct |
5 |
Correct |
3 ms |
948 KB |
Output is correct |
6 |
Correct |
3 ms |
964 KB |
Output is correct |
7 |
Correct |
3 ms |
968 KB |
Output is correct |
8 |
Correct |
3 ms |
968 KB |
Output is correct |
9 |
Correct |
4 ms |
968 KB |
Output is correct |
10 |
Correct |
2 ms |
968 KB |
Output is correct |
11 |
Correct |
2 ms |
968 KB |
Output is correct |
12 |
Correct |
3 ms |
968 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
2520 KB |
Output is correct |
2 |
Correct |
14 ms |
2520 KB |
Output is correct |
3 |
Correct |
17 ms |
2624 KB |
Output is correct |
4 |
Correct |
17 ms |
2624 KB |
Output is correct |
5 |
Correct |
11 ms |
2624 KB |
Output is correct |
6 |
Correct |
12 ms |
2624 KB |
Output is correct |
7 |
Correct |
14 ms |
2624 KB |
Output is correct |
8 |
Correct |
4 ms |
2624 KB |
Output is correct |
9 |
Correct |
4 ms |
2624 KB |
Output is correct |
10 |
Incorrect |
5 ms |
2624 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
199 ms |
18420 KB |
Output is correct |
2 |
Correct |
191 ms |
18420 KB |
Output is correct |
3 |
Correct |
275 ms |
18628 KB |
Output is correct |
4 |
Correct |
250 ms |
18628 KB |
Output is correct |
5 |
Correct |
131 ms |
18628 KB |
Output is correct |
6 |
Correct |
105 ms |
18628 KB |
Output is correct |
7 |
Correct |
157 ms |
18628 KB |
Output is correct |
8 |
Correct |
16 ms |
18628 KB |
Output is correct |
9 |
Correct |
53 ms |
18628 KB |
Output is correct |
10 |
Incorrect |
44 ms |
18628 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
845 ms |
54320 KB |
Output is correct |
2 |
Correct |
781 ms |
54320 KB |
Output is correct |
3 |
Execution timed out |
1051 ms |
54860 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |