oj.uz

Submission #48359

# Submission time Handle Problem Language Result Execution time Memory
48359 2018-05-11T20:02:26 Z octopuses Palindromes (APIO14_palindrome) C++17
58 / 100
 1000 ms 63500 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Correct 12 ms 14696 KB Output is correct
3 Correct 12 ms 14696 KB Output is correct
4 Correct 12 ms 14696 KB Output is correct
5 Correct 12 ms 14696 KB Output is correct
6 Correct 12 ms 14696 KB Output is correct
7 Correct 12 ms 14700 KB Output is correct
8 Correct 12 ms 14700 KB Output is correct
9 Correct 13 ms 14700 KB Output is correct
10 Correct 12 ms 14700 KB Output is correct
11 Correct 12 ms 14700 KB Output is correct
12 Correct 12 ms 14700 KB Output is correct
13 Correct 13 ms 14700 KB Output is correct
14 Correct 12 ms 14700 KB Output is correct
15 Correct 13 ms 14700 KB Output is correct
16 Correct 12 ms 14700 KB Output is correct
17 Correct 12 ms 14700 KB Output is correct
18 Correct 12 ms 14700 KB Output is correct
19 Correct 12 ms 14700 KB Output is correct
20 Correct 12 ms 14700 KB Output is correct
21 Correct 12 ms 14700 KB Output is correct
22 Correct 12 ms 14700 KB Output is correct
23 Correct 12 ms 14700 KB Output is correct
24 Correct 12 ms 14704 KB Output is correct
25 Correct 12 ms 14704 KB Output is correct
26 Correct 12 ms 14704 KB Output is correct
27 Correct 12 ms 14704 KB Output is correct
28 Correct 12 ms 14704 KB Output is correct
29 Correct 12 ms 14704 KB Output is correct
30 Correct 13 ms 14748 KB Output is correct
31 Correct 12 ms 14748 KB Output is correct
32 Correct 12 ms 14748 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14924 KB Output is correct
2 Correct 13 ms 14952 KB Output is correct
3 Correct 12 ms 14952 KB Output is correct
4 Correct 13 ms 14952 KB Output is correct
5 Correct 13 ms 14952 KB Output is correct
6 Correct 13 ms 14952 KB Output is correct
7 Correct 12 ms 14952 KB Output is correct
8 Correct 13 ms 14956 KB Output is correct
9 Correct 13 ms 14956 KB Output is correct
10 Correct 12 ms 14956 KB Output is correct
11 Correct 13 ms 14956 KB Output is correct
12 Incorrect 13 ms 14956 KB Output isn't correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16380 KB Output is correct
2 Correct 20 ms 16436 KB Output is correct
3 Correct 20 ms 16436 KB Output is correct
4 Correct 20 ms 16436 KB Output is correct
5 Correct 20 ms 16436 KB Output is correct
6 Correct 20 ms 16436 KB Output is correct
7 Correct 20 ms 16436 KB Output is correct
8 Correct 21 ms 16436 KB Output is correct
9 Correct 20 ms 16508 KB Output is correct
10 Correct 20 ms 16508 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 30836 KB Output is correct
2 Correct 95 ms 30836 KB Output is correct
3 Correct 97 ms 30836 KB Output is correct
4 Correct 111 ms 30836 KB Output is correct
5 Correct 126 ms 30836 KB Output is correct
6 Correct 107 ms 30836 KB Output is correct
7 Correct 106 ms 30836 KB Output is correct
8 Correct 131 ms 30836 KB Output is correct
9 Correct 115 ms 30836 KB Output is correct
10 Correct 144 ms 30836 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 63500 KB Output is correct
2 Correct 365 ms 63500 KB Output is correct
3 Correct 361 ms 63500 KB Output is correct
4 Correct 420 ms 63500 KB Output is correct
5 Correct 962 ms 63500 KB Output is correct
6 Correct 426 ms 63500 KB Output is correct
7 Correct 490 ms 63500 KB Output is correct
8 Execution timed out 1090 ms 63500 KB Time limit exceeded
9 Halted 0 ms 0 KB -