Submission #89871

#	Time	Username	Problem	Language	Result	Execution time	Memory
89871		Alexa2001	Palindromes (APIO14_palindrome)	C++17	47 / 100	102 ms	79284 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Nmax = 1e6 + 5;

struct tr
{
    int len, sufflink, cnt;
    map<char, int> go;
};
string S;

class PalindromicTree
{
    int nodes, suff;
    tr a[Nmax];

public:
    void init()
    {
        nodes = 2;
        a[1].len = -1;
        a[1].sufflink = 1;
        a[1].cnt = 0;
        a[2].len = 0;
        a[2].sufflink = 1;
        a[2].cnt = 0;
        suff = 2;
    }

    void add(char c, int pos)
    {
        int act = a[suff].len, node = suff;

        while(pos-act-1<0 || S[pos] != S[pos - act - 1])
        {
            node = a[node].sufflink;
            act = a[node].len;
        }

        if(a[node].go[c])
        {
            suff = a[node].go[c];
            ++a[suff].cnt;
            return;
        }

        a[node].go[c] = ++nodes;
        a[nodes].len = a[node].len + 2;
        a[nodes].cnt = 1;
        suff = nodes;

        if(a[nodes].len == 1)
        {
            a[nodes].sufflink = 2;
            return;
        }

        node = a[node].sufflink;
        act = a[node].len;

        while(pos-act-1<0 || S[pos] != S[pos - act - 1])
        {
            node = a[node].sufflink;
            act = a[node].len;
        }

        a[nodes].sufflink = a[node].go[c];
    }

    int get_result()
    {
        int i;
        ll ans = 0;
        for(i=nodes; i; --i)
            a[a[i].sufflink].cnt += a[i].cnt;
        for(i=3; i<=nodes; ++i)
            ans = max(ans, (ll) a[i].cnt * a[i].len);
        return ans;
    }

} paltree;

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    paltree.init();

    cin >> S;
    int nr = 0;
    for(auto letter : S)
        paltree.add(letter, nr++);

    cout << paltree.get_result() << '\n';

    return 0;
}

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