Submission #1124180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124180		Lam_lai_cuoc_doi	Palindromes (APIO14_palindrome)	C++17	100 / 100	109 ms	95628 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

constexpr bool typetest = 0;
constexpr int N = 3e5 + 2;
constexpr ll Inf = 1e17;

struct node
{
    node *child[26], *sufflink;
    vector<node *> adj;
    int len, cnt;

    node()
    {
        len = 0;
        cnt = 0;
        for (int i = 0; i < 26; ++i)
            child[i] = NULL;
        sufflink = NULL;
    }
};

struct PalindromeTree
{
    node even, odd;
    PalindromeTree()
    {
        odd.len = -1;
        odd.sufflink = &odd;
        even.sufflink = &odd;
        odd.adj.emplace_back(&even);
        even.len = 0;
    }

    void Assign(string &s)
    {
        node *last = &even;
        for (int i = 1; i < (int)s.size(); ++i)
        {
            node *tmp = last;

            while (s[i - tmp->len - 1] != s[i])
                tmp = tmp->sufflink;

            if (tmp->child[s[i] - 'a'])
            {
                last = tmp->child[s[i] - 'a'];
                ++last->cnt;
                continue;
            }

            last = tmp->child[s[i] - 'a'] = new node;
            last->len = tmp->len + 2;
            ++last->cnt;

            if (last->len == 1)
            {
                last->sufflink = &even;
                even.adj.emplace_back(last);
                continue;
            }

            do
            {
                tmp = tmp->sufflink;
            } while (s[i - tmp->len - 1] != s[i]);

            last->sufflink = tmp->child[s[i] - 'a'];
            last->sufflink->adj.emplace_back(last);
        }
    }

    ll dfs(node *v)
    {
        ll res(-Inf);
        for (auto i : v->adj)
        {
            res = max(res, dfs(i));
            v->cnt += i->cnt;
        }
        return max(res, 1ll * v->len * v->cnt);
    }
} f;

string s;

void Read()
{
    cin >> s;
    s = " " + s;
}

void Solve()
{
    f.Assign(s);
    cout << f.dfs(&f.odd);
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

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