Submission #48358

#	Time	Username	Problem	Language	Result	Execution time	Memory
48358		octopuses	Palindromes (APIO14_palindrome)	C++17	58 / 100	1088 ms	63496 KiB

palindrome

#include <bits/stdc++.h>
#pragma 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);
}
/*

*/

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:173:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < G[k].size(); ++ i)
                    ~~^~~~~~~~~~~~~
palindrome.cpp:189:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < g[k].size(); ++ i)
                    ~~^~~~~~~~~~~~~
palindrome.cpp:204:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < G[k].size(); ++ i)
                    ~~^~~~~~~~~~~~~
palindrome.cpp:219:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < g[k].size(); ++ i)
                    ~~^~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 0 / 27