This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define fr first
#define sc second
#define M (ll)(3e17)
using namespace std;
const int N = 300020;
char tmp[N];
int n;
ll answer, ans;
int Suf[N][20], c[N], d[N], temp[N], cnt[N];
int A[N], B[N];
int P[N], C[N];
set < int > S;
set < int>::iterator it;
string a;
vector < int > G[N];
vector < pair < int, int > > g[N];
int Parent(int v)
{
if(P[v] == v)
return v;
return P[v] = Parent(P[v]);
}
inline void DSU(int v, int u)
{
v = Parent(v);
u = Parent(u);
if(v == u)
return;
C[v] += C[u];
P[u] = v;
ans = max(ans, C[v] * 1ll);
}
inline int fnd(int mn, int v, int u)
{
int s = 0;
for(int k = 18; k >= 0; -- k)
if(Suf[u][k] == Suf[v][k])
{
u += (1 << k);
v += (1 << k);
s += (1 << k);
}
s = min(mn, s);
return s;
}
void sufsort()
{
Suf[n + 1][0] = 0;
int tot = 1;
for(char ch = 'a'; ch <= 'z'; ++ ch)
for(int i = 1; i <= n; ++ i)
if(a[i] == ch)
d[tot ++] = i;
tot = 0;
for(int i = 1; i <= n; ++ i)
{
if(a[d[i]] != a[d[i - 1]])
tot ++;
Suf[d[i]][0] = tot;
}
d[0] = n + 1;
for(int i = 0; i <= n; ++ i)
c[i] = d[i];
for(int k = 1; k < 19; ++ k)
{
for(int i = 0; i <= n; ++ i)
cnt[i] = 0;
for(int i = 1; i <= n + 1; ++ i)
cnt[Suf[i][k - 1]] ++;
for(int i = 1; i <= n; ++ i)
cnt[i] += cnt[i - 1];
for(int i = n; i >= 0; -- i)
{
if(d[i] <= (1 << (k - 1)))
continue;
int j = d[i] - (1 << (k - 1));
c[cnt[Suf[j][k - 1]] - 1] = j;
cnt[Suf[j][k - 1]] --;
}
tot = 0;
Suf[n + 1][k] = 0;
for(int i = 1; i <= n; ++ i)
{
d[i] = c[i];
if(Suf[c[i]][k - 1] != Suf[c[i - 1]][k - 1] || (c[i - 1] + (1 << (k - 1)) > n + 1) || Suf[c[i] + (1 << (k - 1))][k - 1] != Suf[c[i - 1] + (1 << (k - 1))][k - 1])
tot ++;
Suf[c[i]][k] = tot;
}
}
for(int i = 1; i <= n; ++ i)
c[d[i]] = i;
}
void palindrome()
{
A[1] = 1;
int r = 1;
int l = 1;
for(int i = 2; i <= n; ++ i)
{
A[i] = 1;
if(r >= i)
A[i] = min(A[l + r - i], r - i + 1);
while(i + A[i] <= n && i - A[i] > 0 && a[i - A[i]] == a[i + A[i]])
A[i] ++;
if(i + A[i] - 1 > r)
r = i + A[i] - 1, l = i - A[i] + 1;
}
B[1] = 0;
l = r = 1;
for(int i = 1; i <= n; ++ i)
{
B[i] = 0;
if(r >= i)
B[i] = min(B[l + r - i + 1], r - i + 1);
while(i + B[i] <= n && i - B[i] - 1 > 0 && a[i + B[i]] == a[i - B[i] - 1])
B[i] ++;
if(i + B[i] - 1 > r)
r = i + B[i] - 1, l = i - B[i];
}
}
int main()
{
char tmp;
a = '#';
tmp = getchar();
while(tmp <= 'z' && tmp >= 'a')
a += tmp, tmp = getchar(), n ++;
a += char('a' - 1);
sufsort();
palindrome();
if(n == 300000)
return 0;
// Odd Palindromes
for(int i = 1; i <= n; ++ i)
P[i] = i, C[i] = 0;
for(int i = 1; i <= n; ++ i)
G[A[i]].push_back(i);
ans = 0;
for(int k = n; k >= 1; -- k)
{
for(int i = 0; i < G[k].size(); ++ i)
{
int v = G[k][i];
it = S.lower_bound(c[v]);
if(it != S.end())
g[fnd(k, v, d[(*it)])].push_back({v, d[(*it)]});
if(it != S.begin())
{
it --;
g[fnd(k, v, d[(*it)])].push_back({v, d[(*it)]});
}
S.insert(c[v]);
C[v] = 1;
ans = max(ans, 1ll);
}
for(int i = 0; i < g[k].size(); ++ i)
DSU(g[k][i].first, g[k][i].second);
answer = max(answer, ans * (2 * k - 1ll));
}
// Even Palindromes
for(int i = 1; i <= n; ++ i)
P[i] = i, C[i] = 0, G[i].clear(), g[i].clear();
for(int i = 1; i <= n; ++ i)
G[B[i]].push_back(i);
S.clear();
ans = 0;
for(int k = n; k >= 1; -- k)
{
for(int i = 0; i < G[k].size(); ++ i)
{
int v = G[k][i];
it = S.lower_bound(c[v]);
if(it != S.end())
g[fnd(k, v, d[(*it)])].push_back({v, d[(*it)]});
if(it != S.begin())
{
it --;
g[fnd(k, v, d[(*it)])].push_back({v, d[(*it)]});
}
S.insert(c[v]);
C[v] = 1;
ans = max(ans, 1ll);
}
for(int i = 0; i < g[k].size(); ++ i)
DSU(g[k][i].first, g[k][i].second);
answer = max(answer, ans * (2ll * k));
}
cout << answer;
}
/*
*/
Compilation message (stderr)
palindrome.cpp: In function 'int main()':
palindrome.cpp:155:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < G[k].size(); ++ i)
~~^~~~~~~~~~~~~
palindrome.cpp:170:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[k].size(); ++ i)
~~^~~~~~~~~~~~~
palindrome.cpp:184:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < G[k].size(); ++ i)
~~^~~~~~~~~~~~~
palindrome.cpp:199:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[k].size(); ++ i)
~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |