Submission #223994

#	Time	Username	Problem	Language	Result	Execution time	Memory
223994		lucas110550	Palindromes (APIO14_palindrome)	C++14	100 / 100	104 ms	95736 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

char str[300005];
int n;
int len[300005], ch[300005][26], q[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;
	for (int i = 0; i < 26; i ++) q[0][i] = 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) {
	if (str[x + len[st] + 1] != str[x]) st = q[st][str[x] - 'a'];
	if (!ch[st][str[x] - 'a']) {
		int j = f[st];
		if (str[x + len[j] + 1] != str[x]) j = q[j][str[x] - 'a'];
		//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;
		for (int k = 0; k < 26; k ++) q[cnt][k] = q[ff][k];
		char chx = str[x + len[ff]];
		q[cnt][chx - 'a'] = 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 (!valid(x - len[ed] - 1) || str[x - len[ed] - 1] != str[x]) ed = f[ed];
	if (str[x - 1 - len[ed]] != str[x]) ed = q[ed][str[x] - 'a'];
	if (!ch[ed][str[x] - 'a']) {
		int j = f[ed];
		if (str[x - 1 - len[j]] != str[x]) j = q[j][str[x] - 'a'];
	//	while (!valid(x - len[j] - 1) || 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;
		for (int k = 0; k < 26; k ++) q[cnt][k] = q[ff][k];
		char chx = str[x - len[ff]];
		q[cnt][chx - 'a'] = 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:84: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