제출 #1283218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283218		StefanSebez	회문 (APIO14_palindrome)	C++20	100 / 100	49 ms	59764 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=3e5+50;
struct PalindromicTree{
   string s;int len[N];
   int link[N],go[N][26],cnt[N],nc,Im,Nula,sada;
   vector<int>E[N];
   PalindromicTree(){
       Im=++nc;link[Im]=Im;len[Im]=-1;
       Nula=++nc;link[Nula]=Im;
       sada=Im;
   }
   void Insert(char x){
        s.pb(x);int n=s.size();
        while(s[n-1]!=s[n-2-len[sada]]) sada=link[sada];
        if(!go[sada][x-'a']){
            nc++;
            go[sada][x-'a']=nc;
            len[nc]=len[sada]+2;
            int u=link[sada];
            while(s[n-1]!=s[n-2-len[u]]) u=link[u];
            if(len[nc]==1) u=Nula;
            else u=go[u][x-'a'];
            link[nc]=u;
        }
        sada=go[sada][x-'a'];cnt[sada]++;
   }
   void DFS(int u){
       for(auto i:E[u]) DFS(i),cnt[u]+=cnt[i];
   }
   ll Solve(){
       ll res=0;
       for(int i=2;i<=nc;i++) E[link[i]].pb(i);
       DFS(Im);
       for(int i=2;i<=nc;i++) res=max(res,(ll)len[i]*cnt[i]);
       return res;
   }
}st;
int main(){
    string s;cin>>s;
    for(auto i:s) st.Insert(i);
    ll res=st.Solve();
    printf("%lld\n",res);
    return 0;
}

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