Submission #734377

#	Time	Username	Problem	Language	Result	Execution time	Memory
734377		SanguineChameleon	Palindromes (APIO14_palindrome)	C++17	100 / 100	121 ms	105044 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct node {
	int len = 0;
	node *ch[26] = {};
	node *suf = nullptr;
	vector<node*> ch_suf;
	int cnt = 0;

	node() {};

	node(int _len): len(_len) {};
};

node *root0 = new node(0);
node *root1 = new node(-1);
const int maxn = 3e5 + 20;
int a[maxn];
long long res;

void dfs(node *u) {
	for (auto v: u->ch_suf) {
		dfs(v);
		u->cnt += v->cnt;
	}
	res = max(res, 1LL * u->len * u->cnt);
}

void just_do_it() {
	root0->suf = root1;
	root1->suf = root1;
	root1->ch_suf.push_back(root0);
	string s;
	cin >> s;
	int n = s.size();
	for (int i = 1; i <= n; i++) {
		a[i] = s[i - 1] - 'a';
	}
	a[0] = -1;
	node *cur = root0;
	for (int i = 1; i <= n; i++) {
		while (a[i - cur->len - 1] != a[i]) {
			cur = cur->suf;
		}
		if (!cur->ch[a[i]]) {
			cur->ch[a[i]] = new node(cur->len + 2);
			if (cur == root1) {
				cur->ch[a[i]]->suf = root0;
			}
			else {
				node *cur_suf = cur->suf;
				while (a[i - cur_suf->len - 1] != a[i]) {
					cur_suf = cur_suf->suf;
				}
				cur->ch[a[i]]->suf = cur_suf->ch[a[i]];
			}
			cur->ch[a[i]]->suf->ch_suf.push_back(cur->ch[a[i]]);
		}
		cur = cur->ch[a[i]];
		cur->cnt++;
	}
	dfs(root1);
	cout << res;
}

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