Submission #868510

#	Time	Username	Problem	Language	Result	Execution time	Memory
868510		Amdadul	Palindromes (APIO14_palindrome)	C++14	100 / 100	23 ms	37580 KiB

palindrome

#include<iostream>
#include<string>
#include<vector>
using namespace std;

const int N = 300000 + 10;

int tree[N][26];
int idx, len[N], link[N], cnt[N], t;
string s;
long long oc[N];

void add(int p)
{
	while (s[p - len[t] - 1] != s[p])t = link[t];
	int x = link[t];
	int c = s[p] - 'a';

	while (s[p - len[x] - 1] != s[p])x = link[x];

	if (tree[t][c] == 0)
	{
		tree[t][c] = ++idx;
		len[idx] = len[t] + 2;
		link[idx] = len[idx] == 1 ? 2 : tree[x][c];
		oc[idx]++;
	}
	else oc[tree[t][c]]++;
	t = tree[t][c];


}



int main()
{

	len[1] = -1, link[1] = 1;
	len[2] = 0, link[2] = 1;
	idx = t = 2;
	cin >> s;
	s = '$' + s;
	for (int i = 1; i < (int)s.size(); i++)
	{
		add(i);
	}
	long long ans = 0;
	vector<bool>fre(idx + 1, 0);

	for (int i = idx; i >= 3; --i)  {
		oc[link[i]] += oc[i];
		ans = max(ans, (1ll * len[i] * oc[i]));
	}
	
	cout << ans << "\n";

}

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