oj.uz

Submission #48354

# Submission time Handle Problem Language Result Execution time Memory
48354 2018-05-11T19:38:18 Z octopuses Palindromes (APIO14_palindrome) C++17
65 / 100
 1000 ms 68876 KB 
#include <bits/stdc++.h>

#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];
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 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 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();

// 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;
  for(int k = n / 2; k >= 1; -- k)
  {
    for(int i = 0; i < G[k].size(); ++ i)
    {
      int v = G[k][i], u;
      it = S.lower_bound(c[v]);
      if(it != S.end())
      {
        u = fnd(v, d[(*it)]);
        if(u >= k)
          DSU(v, d[(*it)]);
        else
          g[u].push_back({v, d[(*it)]});
      }
      if(it != S.begin())
      {
        it --;
        u = fnd(v, d[(*it)]);
        if(u >= k)
          DSU(v, d[(*it)]);
        else
          g[u].push_back({v, d[(*it)]});
      }
      S.insert(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();
  for(int i = 1; i <= n; ++ i)
    G[B[i]].push_back(i);
  S.clear();
  ans = 0;
  for(int k = n / 2 + 1; k >= 1; -- k)
  {
    for(int i = 0; i < G[k].size(); ++ i)
    {
      int v = G[k][i], u;
      it = S.lower_bound(c[v]);
      if(it != S.end())
      {
        u = fnd(v, d[(*it)]);
        if(u >= k)
          DSU(v, d[(*it)]);
        else
          g[u].push_back({v, d[(*it)]});
      }
      if(it != S.begin())
      {
        it --;
        u = fnd(v, d[(*it)]);
        if(u >= k)
          DSU(v, d[(*it)]);
        else
          g[u].push_back({v, d[(*it)]});
      }
      S.insert(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 * (2ll * k));
  }
  printf("%lld", answer);
}

Compilation message

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14696 KB Output is correct
2 Correct 13 ms 14696 KB Output is correct
3 Correct 13 ms 14696 KB Output is correct
4 Correct 13 ms 14696 KB Output is correct
5 Correct 13 ms 14696 KB Output is correct
6 Correct 13 ms 14764 KB Output is correct
7 Correct 13 ms 14804 KB Output is correct
8 Correct 13 ms 14804 KB Output is correct
9 Correct 13 ms 14804 KB Output is correct
10 Correct 13 ms 14804 KB Output is correct
11 Correct 13 ms 14804 KB Output is correct
12 Correct 13 ms 14896 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16432 KB Output is correct
2 Correct 21 ms 16432 KB Output is correct
3 Correct 23 ms 16432 KB Output is correct
4 Correct 23 ms 16432 KB Output is correct
5 Correct 23 ms 16432 KB Output is correct
6 Correct 24 ms 16432 KB Output is correct
7 Correct 22 ms 16464 KB Output is correct
8 Correct 24 ms 16464 KB Output is correct
9 Correct 25 ms 16464 KB Output is correct
10 Correct 26 ms 16464 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 32880 KB Output is correct
2 Correct 147 ms 32880 KB Output is correct
3 Correct 184 ms 32880 KB Output is correct
4 Correct 185 ms 32880 KB Output is correct
5 Correct 205 ms 32880 KB Output is correct
6 Correct 154 ms 32880 KB Output is correct
7 Correct 174 ms 32880 KB Output is correct
8 Correct 205 ms 32880 KB Output is correct
9 Correct 190 ms 32880 KB Output is correct
10 Correct 234 ms 32880 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 68700 KB Output is correct
2 Correct 573 ms 68876 KB Output is correct
3 Correct 688 ms 68876 KB Output is correct
4 Correct 689 ms 68876 KB Output is correct
5 Execution timed out 1087 ms 68876 KB Time limit exceeded
6 Halted 0 ms 0 KB -