Submission #100231

#	Time	Username	Problem	Language	Result	Execution time	Memory
100231		TadijaSebez	Palindromes (APIO14_palindrome)	C++11	100 / 100	104 ms	59768 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=300050;
struct EERTREE
{
	char s[N];
	int link[N],at,go[N][26],len[N],cnt[N],ZERO,IMAG,tsz,sz;
	vector<int> E[N];
	void init()
	{
		IMAG=++tsz;link[IMAG]=IMAG;len[IMAG]=-1;
		ZERO=++tsz;link[ZERO]=IMAG;len[ZERO]=0;
		E[IMAG].push_back(ZERO);
		at=IMAG;
	}
	EERTREE(){ init();}
	void Grow()
	{
		++sz;
		while(s[sz]!=s[sz-len[at]-1]) at=link[at];
		if(!go[at][s[sz]-'a'])
		{
			tsz++;link[tsz]=link[at];go[at][s[sz]-'a']=tsz;len[tsz]=len[at]+2;
			while(s[sz]!=s[sz-len[link[tsz]]-1]) link[tsz]=link[link[tsz]];
			if(len[tsz]==1) link[tsz]=ZERO;
			else link[tsz]=go[link[tsz]][s[sz]-'a'];
			E[link[tsz]].push_back(tsz);
		}
		at=go[at][s[sz]-'a'];cnt[at]++;
	}
	void DFS(int u)
	{
		for(int v:E[u]) DFS(v),cnt[u]+=cnt[v];
	}
	ll Solve()
	{
		DFS(IMAG);
		ll ans=0;
		for(int i=1;i<=tsz;i++) if(len[i]>0) ans=max(ans,(ll)len[i]*cnt[i]);
		return ans;
	}
} TREE;
int main()
{
	int n;
	scanf("%s",TREE.s+1);
	n=strlen(TREE.s+1);
	for(int i=1;i<=n;i++) TREE.Grow();
	printf("%lld\n",TREE.Solve());
	return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",TREE.s+1);
  ~~~~~^~~~~~~~~~~~~~~

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