Submission #223992

#	Time	Username	Problem	Language	Result	Execution time	Memory
223992		lucas110550	Palindromes (APIO14_palindrome)	C++14	100 / 100	92 ms	65400 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

char str[300005];
int n;
int len[300005], ch[300005][26];
int r[300005], f[300005];
char s[101];
int h, t, cnt;
long long sum = 0;
int st, ed;
vector<int> E[300005];

void init() {
	for (int i = 0; i < 2; i ++) memset(ch[i], 0, sizeof(ch[i]));
	len[0] = 0; len[1] = -1;
	f[0] = 1; f[1] = 1;
	st = ed = 0;
	cnt = 1;
	sum = 0;
}

bool valid(int x) {
	return 1 <= x && x <= t;
}

void front_ins(int x) {
	while (str[x + len[st] + 1] != str[x]) st = f[st];
	if (!ch[st][str[x] - 'a']) {
		int j = f[st];
		while (str[x + len[j] + 1] != str[x]) j = f[j];
		len[++ cnt] = len[st] + 2;
		int ff = ch[j][str[x] - 'a'];
		f[cnt] = ff;
		E[ff].push_back(cnt);
		ch[st][str[x] - 'a'] = cnt;
		memset(ch[cnt], 0, sizeof(ch[cnt]));
	}
	st = ch[st][str[x] - 'a'];
	r[st] ++;
//	sum += r[st];
	if (len[st] == t - h) ed = st;
}

void back_ins(int x) {
	while (str[x - len[ed] - 1] != str[x]) ed = f[ed];
	if (!ch[ed][str[x] - 'a']) {
		int j = f[ed];
		while (str[x - len[j] - 1] != str[x]) j = f[j];
		len[++ cnt] = len[ed] + 2;
		int ff = ch[j][str[x] - 'a'];
		f[cnt] = ff;
		E[ff].push_back(cnt);
		ch[ed][str[x] - 'a'] = cnt;
		memset(ch[cnt], 0, sizeof(ch[cnt]));
	}
	ed = ch[ed][str[x] - 'a'];
	r[ed] ++;
//	sum += r[ed];
	if (len[ed] == t - h) st = ed;
}

void dfs(int x) {
	for (int i = 0; i < (int )E[x].size(); i ++) { 
		dfs(E[x][i]);
		r[x] += r[E[x][i]];
	}
}

int main( ) {
	init();
	scanf("%s", str + 1);
	n = (int )strlen(str + 1);
	for (int i = 1; i <= n; i ++) {
		++ t;
		back_ins(i);
	}
	dfs(0);
	for (int i = 2; i <= cnt; i ++) {
		sum = max(sum, 1LL * r[i] * len[i]);
	}
	printf("%lld\n", sum);
	return 0;
}

Compilation message (stderr)

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

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