Submission #1203016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203016		user736482	Palindromes (APIO14_palindrome)	C++20	100 / 100	135 ms	78752 KiB

palindrome

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
ll n,a,b,c,d,e,ans;
string s;
ll moj[300007],ile[300007],licz[300007];
vector<ll>lnk,sz;
vector<unordered_map<char,ll>>prz;
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>s;
    n=s.size();
    lnk.pb(-1);lnk.pb(0);
    sz.pb(-1);sz.pb(0);
    prz.pb({});prz.pb({});
    moj[0]=1;
    for(ll i=1;i<=n;i++){
        ll ak=moj[i-1];
        while(s[i-1]!=s[i-2-sz[ak]])ak=lnk[ak];
        if(prz[ak][s[i-1]]!=0){
            moj[i]=prz[ak][s[i-1]];
        }
        else{
            moj[i]=sz.size();
            prz[ak][s[i-1]]=sz.size();
            sz.pb(sz[ak]+2);
            prz.pb({});
            ak=lnk[ak];
            while(ak!=-1 && s[i-1]!=s[i-2-sz[ak]])ak=lnk[ak];
            if(ak==-1)lnk.pb(1);
            else lnk.pb(prz[ak][s[i-1]]);
            ile[lnk.back()]++;
        }
        licz[moj[i]]++;
    }
    queue<ll>q;
    ile[0]=INFL;
    ile[1]=INFL;
    for(ll i=2;i<sz.size();i++ ){
        if(ile[i]==0)q.push(i);
    }
    while(q.size()){
        ll pom=q.front();
        q.pop();
        ans=max(ans,sz[pom]*licz[pom]);
        ile[lnk[pom]]--;
        licz[lnk[pom]]+=licz[pom];
        if(ile[lnk[pom]]==0)q.push(lnk[pom]);
    }
    cout<<ans;
}

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