Submission #1219402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219402		leo020630	Palindromes (APIO14_palindrome)	C++20	100 / 100	75 ms	74496 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 ALPHA = 26;
struct eerTree {
    struct Node {
        int link, len, par, pos, num;
        int ch[ALPHA];
        Node() {
            link=len=par=pos=num=0;
            fill(ch,ch+ALPHA,-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;

const int MX = 3e5 + 5;
vector<int> G[MX];

void dfs(int x)
{
    for(auto &y:G[x])
    {
        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);
    for(int i=1;i<ET.T.size();i++) G[ET.T[i].link].push_back(i);
    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: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27