| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 48357 | octopuses | 회문 (APIO14_palindrome) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#GCC optimize("O3")
#define ll long long
#define fr first
#define sc second
#define M (ll)(3e17)
#define MAX(a,b) (a>b?a:b)
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];
int L[N], R[N], F[N];
string a;
vector < int > G[N];
vector < pair < int, int > > g[N];
inline int get(int x)
{
int s = 0;
while(x > 0)
{
s = max(s, F[x]);
x -= x & (-x);
}
return s;
}
inline void upd(int x, int v)
{
while(x <= n)
{
F[x] = MAX(F[x], v);
x += x & (-x);
}
}
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);
}
return min(s, mn);
}
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();
// Odd Palindromes
for(int i = 1; i <= n; ++ i)
P[i] = i, C[i] = 1;
for(int i = 1; i <= n; ++ i)
G[A[i]].push_back(i);
ans = 0;
R[0] = n + 1;
L[n + 1] = 0;
for(int k = n / 2 + 1; k >= 1; -- k)
{
for(int i = 0; i < G[k].size(); ++ i)
{
int v = G[k][i];
int x = get(c[v]);
if(x != 0)
g[fnd(k, d[x], v)].push_back({d[x], v});
int y = R[x];
R[x] = c[v];
L[c[v]] = x;
if(y != n + 1)
g[fnd(k, d[y], v)].push_back({d[y], v});
R[c[v]] = y;
L[y] = c[v];
upd(c[v], c[v]);
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] = 1, G[i].clear(), g[i].clear(), F[i] = 0;
for(int i = 1; i <= n; ++ i)
G[B[i]].push_back(i);
ans = 0;
L[n + 1] = 0; R[0] = n + 1; F[0] = 0;
for(int k = n / 2; k >= 1; -- k)
{
for(int i = 0; i < G[k].size(); ++ i)
{
int v = G[k][i];
int x = get(c[v]);
if(x != 0)
g[fnd(k, d[x], v)].push_back({d[x], v});
int y = R[x];
R[x] = c[v];
L[c[v]] = x;
if(y != n + 1)
g[fnd(k, d[y], v)].push_back({d[y], v});
R[c[v]] = y;
L[y] = c[v];
upd(c[v], c[v]);
}
for(int i = 0; i < g[k].size(); ++ i)
DSU(g[k][i].first, g[k][i].second);
answer = MAX(answer, ans * (2ll * k));
}
printf("%lld\n", answer);
}
/*
*/