Submission #565616

#	Time	Username	Problem	Language	Result	Execution time	Memory
565616		Forested	Palindromes (APIO14_palindrome)	C++17	100 / 100	68 ms	64184 KiB

palindrome

// ===== template.hpp =====
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define OVERRIDE(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32) (n); ++i)
#define REP3(i, m, n) for (i32 i = (i32) (m); i < (i32) (n); ++i)
#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER(i, n) for (i32 i = (i32) (n) - 1; i >= 0; --i)
#define ALL(x) begin(x), end(x)

using namespace std;

using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = __uint128_t;
using i32 = signed int;
using i64 = signed long long;
using i128 = __int128_t;
using f64 = double;
using f80 = long double;

template <typename T>
using Vec = vector<T>;

template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

istream &operator>>(istream &is, i128 &x) {
    i64 v;
    is >> v;
    x = v;
    return is;
}
ostream &operator<<(ostream &os, i128 x) {
    os << (i64) x;
    return os;
}
istream &operator>>(istream &is, u128 &x) {
    u64 v;
    is >> v;
    x = v;
    return is;
}
ostream &operator<<(ostream &os, u128 x) {
    os << (u64) x;
    return os;
}

template <typename F, typename Comp = less<>>
Vec<i32> sort_index(i32 n, F f, Comp comp = Comp()) {
    Vec<i32> idx(n);
    iota(ALL(idx), 0);
    sort(ALL(idx), [&](i32 i, i32 j) -> bool {
        return comp(f(i), f(j));
    });
    return idx;
}

[[maybe_unused]] constexpr i32 INF = 1000000100;
[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;

struct FastIO {
    FastIO() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout << fixed << setprecision(10);
    }
} fast_io;
// ===== template.hpp =====

#ifdef DEBUGF
#include "cpl/template/debug.hpp"
#else
#define DBG(x) (void) 0
#endif

// ===== eertree.hpp =====

#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <cassert>

template <int SIGMA = 26>
class Eertree {
    std::vector<int> seq;
    std::vector<std::pair<int, int>> range;
    std::vector<int> suf_link;
    std::vector<std::array<int, SIGMA>> ext;
    std::vector<int> freq;
    int longest_suffix;
    
public:
    Eertree() : seq(), range(2), suf_link(2), ext(2), freq(2), longest_suffix(1) {
        range[0] = std::pair<int, int>(0, -1);
        suf_link[0] = -1;
        std::fill(ext[0].begin(), ext[0].end(), -1);
        freq[0] = 0;
        range[1] = std::pair<int, int>(0, 0);
        suf_link[1] = 0;
        std::fill(ext[1].begin(), ext[1].end(), -1);
        freq[1] = 0;
    }
    
    void reserve(int n) {
        seq.reserve(n);
    }
    
    // amortized O(SIGMA)
    bool push(int c) {
        assert(c < SIGMA);
        seq.push_back(c);
        int cur = longest_suffix;
        while (true) {
            bool is_palindrome = false;
            {
                int len = range[cur].second - range[cur].first;
                is_palindrome = ((int) seq.size() >= len + 2 && seq[(int) seq.size() - len - 2] == c);
            }
            if (is_palindrome) {
                if (ext[cur][c] != -1) {
                    ++freq[ext[cur][c]];
                    longest_suffix = ext[cur][c];
                    return false;
                }
                break;
            }
            cur = suf_link[cur];
        }
        int this_node = (int) range.size();
        ext[cur][c] = this_node;
        {
            int len = range[cur].second - range[cur].first + 2;
            range.emplace_back((int) seq.size() - len, (int) seq.size());
        }
        ext.emplace_back(std::array<int, SIGMA>());
        std::fill(ext.back().begin(), ext.back().end(), -1);
        freq.push_back(1);
        longest_suffix = this_node;
        if (range[this_node].second - range[this_node].first == 1) {
            suf_link.push_back(1);
            return true;
        }
        cur = suf_link[cur];
        while (true) {
            bool is_palindrome = false;
            {
                int len = range[cur].second - range[cur].first;
                is_palindrome = ((int) seq.size() >= len + 2 && seq[(int) seq.size() - len - 2] == c);
            }
            if (is_palindrome && ext[cur][c] != -1) {
                suf_link.push_back(ext[cur][c]);
                return true;
            }
            cur = suf_link[cur];
        }
        assert(false);
    }
    
    int num_palindromes() const {
        return (int) range.size() - 2;
    }
    
    const std::pair<int, int> &operator[](int i) const {
        return range[i + 2];
    }
    
    std::vector<std::pair<int, int>> palindromes() const {
        return std::vector<std::pair<int, int>>(range.begin() + 2, range.end());
    }
    
    // O(|S|)
    std::vector<int> frequencies() const {
        std::vector<int> ret(freq.size() - 2, 0);
        for (int i = (int) freq.size() - 1; i >= 2; --i) {
            ret[i - 2] += freq[i];
            if (suf_link[i] >= 2) {
                ret[suf_link[i] - 2] += ret[i - 2];
            }
        }
        return ret;
    }
};
// ===== eertree.hpp =====

int main() {
    string s;
    cin >> s;
    Eertree<> eertree;
    for (char c : s) {
        eertree.push(c - 'a');
    }
    Vec<i32> freq = eertree.frequencies();
    i64 ans = 0;
    REP(i, freq.size()) {
        auto [l, r] = eertree[i];
        chmax(ans, (i64) freq[i] * (r - l));
        //cout << s.substr(l, r - l) << ' ' << freq[i] << '\n';
    }
    cout << ans << '\n';
}

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