Submission #1195632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195632		boclobanchat	Palindromes (APIO14_palindrome)	C++20	100 / 100	21 ms	37652 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
struct node
{
	int nex[26],len,sufflink,last,child,cnt;
};
node ptree[MAXN];
char c[MAXN];
int cchar=0,cnt=2,suff=2,ans[MAXN];
void ins(char w)
{
	c[++cchar]=w;
	int v=w-'a';
	while(true)
	{
		if(c[cchar-ptree[suff].len-1]==w) break;
		else suff=ptree[suff].sufflink;
	}
	int sus=suff;
	if(!ptree[suff].nex[v]) ptree[suff].nex[v]=++cnt;
	suff=ptree[suff].nex[v],ptree[suff].child=sus;
	ptree[suff].len=ptree[sus].len+2;
	ptree[suff].last=v,ptree[suff].cnt++;
	if(ptree[suff].len==1)
	{
		ptree[suff].sufflink=2;
		return ;
	}
	while(true)
	{
		sus=ptree[sus].sufflink;
		if(c[cchar-ptree[sus].len-1]==w) break;
	}
	ptree[suff].sufflink=ptree[sus].nex[v];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin>>s;
    int n=s.length();
    ptree[1].len=-1,ptree[2].sufflink=1;
    for(auto v:s) ins(v);
    long long ans=0;
    for(int i=cnt;i;i--)
    {
    	ans=max(ans,(long long)ptree[i].len*ptree[i].cnt);
    	ptree[ptree[i].sufflink].cnt+=ptree[i].cnt;
	}
	cout<<ans;
}

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