Submission #259195

#	Time	Username	Problem	Language	Result	Execution time	Memory
259195		EntityIT	Palindromes (APIO14_palindrome)	C++14	100 / 100	454 ms	18752 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) static_cast<int>((x).size())

template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
      : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
      : vector<T>(args...) {}
};

template<class T>
inline bool Minimize(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool Maximize(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int Next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int Prev(int i, int n) { return !i ? n - 1 : i - 1; }

mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));

vec<pair<int, int>, 1> Manacher(const string& s) {
  vec<pair<int, int>, 1> max_palindromes(SZ(s));

  for (int i = 0, l = -1, r = -1; i < SZ(s); ++i) {
    if (i > r) {
      for (l = i - 1, r = i; ~l && r < SZ(s) && s[l] == s[r]; --l, ++r);
      max_palindromes[i].first = r - i; ++l; --r;
    } else {
      if (max_palindromes[l + r - (i - 1)].first < r - i + 1) {
        max_palindromes[i].first = max_palindromes[l + r - (i - 1)].first;
      } else {
        for (++r, l = (i << 1) - 1 - r; ~l && r < SZ(s) && s[l] == s[r]; --l, ++r);
        max_palindromes[i].first = r - i; ++l; --r;
      }
    }
  }

  for (int i = 0, l = -1, r = -1; i < SZ(s); ++i) {
    if (i > r) {
      for (l = i - 1, r = i + 1; ~l && r < SZ(s) && s[l] == s[r]; --l, ++r);
      max_palindromes[i].second = r - i; ++l; --r;
    } else {
      if (max_palindromes[l + r - i].second < r - i + 1) {
        max_palindromes[i].second = max_palindromes[l + r - i].second;
      } else {
        for (++r, l = (i << 1) - r; ~l && r < SZ(s) && s[l] == s[r]; --l, ++r);
        max_palindromes[i].second = r - i; ++l; --r;
      }
    }
  }

  return max_palindromes;
}

struct SuffixArray {
  vec<int, 1> ordered_suffixes, ranks, lcps;
  SuffixArray(const string& s) {
    int n = SZ(s);

    ordered_suffixes = vec<int, 1>(n); iota(ALL(ordered_suffixes), 0);
    sort(ALL(ordered_suffixes), [&](int i, int j) {
      return s[i] < s[j];
    });
    ranks = vec<int, 1>(n);
    for (int i = 1; i < n; ++i) {
      ranks[ordered_suffixes[i]] = ranks[ordered_suffixes[i - 1]] + (s[ordered_suffixes[i - 1]] < s[ordered_suffixes[i]]);
    }

    vec<int, 1> counters(n), next_ordered_suffixes(n), next_ranks(n);
    for (int i = 1; ranks[ordered_suffixes.back()] < n - 1; i <<= 1) {
      for (int j = 0; j < n; ++j) {
        counters[ranks[ordered_suffixes[j]]] = j;
      }
      for (int j = n - 1; ~j; --j) {
        if (ordered_suffixes[j] >= i) {
          next_ordered_suffixes[counters[ranks[ordered_suffixes[j] - i]]--] = ordered_suffixes[j] - i;
        }
      }
      for (int j = n - i; j < n; ++j) {
        next_ordered_suffixes[counters[ranks[j]]--] = j;
      }
      ordered_suffixes.swap(next_ordered_suffixes);

      next_ranks[ordered_suffixes[0]] = 0;
      for (int j = 1; j < n; ++j) {
        next_ranks[ordered_suffixes[j]] = next_ranks[ordered_suffixes[j - 1]] + (ranks[ordered_suffixes[j - 1]] != ranks[ordered_suffixes[j]] || ordered_suffixes[j - 1] + i >= n || ranks[ordered_suffixes[j - 1] + i] != ranks[ordered_suffixes[j] + i]);
      }
      ranks.swap(next_ranks);
    }

    lcps = vec<int, 1>(n - 1);
    for (int i = 0, j = 0; i < n; ++i, j = max(j - 1, 0)) {
      if (ranks[i] < n - 1) {
        for (int k = ordered_suffixes[ranks[i] + 1]; max(k, i) + j < n && s[k + j] == s[i + j]; ++j);
        lcps[ranks[i]] = j;
      }
    }
  }
};

struct DSU {
  int n_sets;
  vec<int, 1> parents, cardinalities;
  DSU(int t_n_sets)
    : n_sets(t_n_sets),
      parents(n_sets),
      cardinalities(n_sets, 1) {
    iota(ALL(parents), 0);
  }

  int Parent(int i) {
    return i == parents[i] ? i : parents[i] = Parent(parents[i]);
  }
  bool SameSet(int i, int j) {
    return Parent(i) == Parent(j);
  }
  bool Unite(int i, int j) {
    i = Parent(i); j = Parent(j);
    if (i == j) {
      return false;
    }
    if (cardinalities[i] > cardinalities[j]) {
      swap(i, j);
    }
    --n_sets;
    parents[i] = j;
    cardinalities[j] += cardinalities[i];
    return true;
  }
};

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  string s; cin >> s;

  auto max_palindromes = Manacher(s);

  SuffixArray sa(s);

  int64_t answer = 0;

  for (int i = SZ(s) >> 1; i; --i) {
    static vec<int, 1> ordered_positions;
    static auto ordered_position = ordered_positions.begin();
    if (!SZ(ordered_positions)) {
      ordered_positions = vec<int, 1>(SZ(s));
      ordered_position = ordered_positions.begin();
      iota(ALL(ordered_positions), 0);
      sort(ALL(ordered_positions), [&](const auto& x, const auto& y) {
        return max_palindromes[sa.ordered_suffixes[x]].first > max_palindromes[sa.ordered_suffixes[y]].first;
      });
    }

    static vec<int, 1> ordered_links;
    static auto ordered_link = ordered_links.begin();
    if (!SZ(ordered_links)) {
      ordered_links = vec<int, 1>(SZ(s) - 1);
      ordered_link = ordered_links.begin();
      iota(ALL(ordered_links), 0);
      sort(ALL(ordered_links), [&](const auto& x, const auto& y) {
        return sa.lcps[x] > sa.lcps[y];
      });
    }

    static DSU dsu(SZ(s));

    static vec<int, 1> values(SZ(s));
    static int max_value = 0;

    for (; ordered_link != ordered_links.end() && sa.lcps[*ordered_link] >= i; ++ordered_link) {
      int u = dsu.Parent(*ordered_link), v = dsu.Parent((*ordered_link) + 1);
      dsu.Unite(u, v);
      Maximize(max_value, (values[dsu.Parent(u)] += values[u ^ v ^ dsu.Parent(u)]));
    }

    for (; ordered_position != ordered_positions.end() && max_palindromes[sa.ordered_suffixes[*ordered_position]].first >= i; ++ordered_position) {
      int u = dsu.Parent(*ordered_position);
      Maximize(max_value, (++values[u]));
    }

    Maximize(answer, static_cast<int64_t>(max_value) * (i << 1));
  }

  for (int i = (SZ(s) + 1) >> 1; i; --i) {
    static vec<int, 1> ordered_positions;
    static auto ordered_position = ordered_positions.begin();
    if (!SZ(ordered_positions)) {
      ordered_positions = vec<int, 1>(SZ(s));
      ordered_position = ordered_positions.begin();
      iota(ALL(ordered_positions), 0);
      sort(ALL(ordered_positions), [&](const auto& x, const auto& y) {
        return max_palindromes[sa.ordered_suffixes[x]].second > max_palindromes[sa.ordered_suffixes[y]].second;
      });
    }

    static vec<int, 1> ordered_links;
    static auto ordered_link = ordered_links.begin();
    if (!SZ(ordered_links)) {
      ordered_links = vec<int, 1>(SZ(s) - 1);
      ordered_link = ordered_links.begin();
      iota(ALL(ordered_links), 0);
      sort(ALL(ordered_links), [&](const auto& x, const auto& y) {
        return sa.lcps[x] > sa.lcps[y];
      });
    }

    static DSU dsu(SZ(s));

    static vec<int, 1> values(SZ(s));
    static int max_value = 0;

    for (; ordered_link != ordered_links.end() && sa.lcps[*ordered_link] >= i; ++ordered_link) {
      int u = dsu.Parent(*ordered_link), v = dsu.Parent((*ordered_link) + 1);
      dsu.Unite(u, v);
      Maximize(max_value, (values[dsu.Parent(u)] += values[u ^ v ^ dsu.Parent(u)]));
    }

    for (; ordered_position != ordered_positions.end() && max_palindromes[sa.ordered_suffixes[*ordered_position]].second >= i; ++ordered_position) {
      int u = dsu.Parent(*ordered_position);
      Maximize(max_value, (++values[u]));
    }

    Maximize(answer, static_cast<int64_t>(max_value) * ((i << 1) - 1));
  }

  cout << answer << '\n';

  return 0;
}

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