Submission #1219401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219401		leo020630	Palindromes (APIO14_palindrome)	C++20	0 / 100	0 ms	324 KiB

palindrome

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef long double ld;

const int MX = 26;
struct eerTree {
    struct Node {
        int link, len, par, pos, num;
        int ch[MX];
        Node() {
            link=len=par=pos=num=0;
            fill(ch,ch+MX,-1);
        }
    };

    vector<Node> T;
    vector<int> suf;

    void init(const string &S) {
        T.push_back(Node()); T.push_back(Node());
        T[0].len=-1;

        int prv=0;
        for(int i=0;i<S.size();i++)
        {
            while(prv!=0 && (i==T[prv].len || S[i-1-T[prv].len]!=S[i])) prv=T[prv].link;

            int c=S[i]-'a';

            if(T[prv].ch[c]==-1)
            {
                int now=T.size(); T.push_back(Node());

                int pp=T[prv].link;
                while(pp!=0 && (i==T[pp].len || S[i-1-T[pp].len]!=S[i])) pp=T[pp].link;
                
                T[now].link=(T[pp].ch[c]==-1?1:T[pp].ch[c]);

                T[now].len=T[prv].len+2;
                T[now].par=prv;
                T[now].pos=i;
                T[now].num=1;

                T[prv].ch[c]=now;
            }
            else T[T[prv].ch[c]].num++;

            suf.push_back(prv = T[prv].ch[c]);
        }
    }

};

eerTree ET;

void dfs(int x)
{
    for(int i=0;i<MX;i++) if(ET.T[x].ch[i]!=-1)
    {
        int y=ET.T[x].ch[i];
        dfs(y);
        ET.T[x].num+=ET.T[y].num;
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    string s; cin>>s;
    ET.init(s);

    dfs(1);

    ll ans=0;

    for(int i=1;i<ET.T.size();i++)
        ans=max(ans,(ll)ET.T[i].len*ET.T[i].num);

    cout<<ans;
    return 0;
}

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