Submission #1117484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117484		mat_jur	Palindromes (APIO14_palindrome)	C++17	73 / 100	119 ms	131072 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

const int A = 27;

struct trie_node {
	int depth; 
	trie_node* parent;
	trie_node* e[A];
	int cnt;

	trie_node() {
		depth = 0;
		parent = nullptr;
		for (int i = 0; i < A; ++i) e[i] = nullptr;
		cnt = 0;
	}
};

void add_edge(trie_node *v, char c) {
	assert(v != nullptr);
	int x = c - 'a';
	if (v->e[x] != nullptr) return;
	trie_node *u = v->e[x] = new trie_node;
	u->depth = v->depth + 1;
	u->parent = v;
}

ll dfs(trie_node *v) {
	ll res = 0;
	for (int i = 0; i < A; ++i) {
		if (v->e[i] != nullptr) {
			res = max(res, dfs(v->e[i]));
			v->cnt += v->e[i]->cnt;
			delete v->e[i];
		}
	}

	return max(res, ll(v->cnt) * ll(v->depth - 1));
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	string s;
	cin >> s;
	int n = ssize(s);

	char filler = 'z' + 1;
	string tmp;
	tmp.push_back(filler);
	for (char x : s) {
		tmp.push_back(x);
		tmp.push_back(filler);
	}

	s = tmp;
	n = ssize(s);

	vector<int> r(n);
	int f = 0;
	r[0] = 1;

	vector<trie_node*> Node(n+1);
	Node[0] = new trie_node;

	add_edge(Node[0], s[0]);
	Node[1] = Node[0]->e[s[0]-'a'];

	for (int i = 1; i < n; ++i) {
		int parent = 0;
		r[i] = 0;
		if (f + r[f] - 1 >= i) {
			int sym = 2*f - i;
			if (sym >= 0) {
				r[i] = max(r[i], min(r[sym], sym - (f - r[f])));
				parent = sym+1;	
			}
		}

		int v = i+1;
		Node[v] = Node[parent];
		while (Node[v]->depth != r[i]) Node[v] = Node[v]->parent;

		while (i - r[i] >= 0 && i + r[i] < n && s[i-r[i]] == s[i+r[i]]) {
			add_edge(Node[v], s[i+r[i]]);
			Node[v] = Node[v]->e[s[i+r[i]]-'a'];
			r[i]++;
		}

		Node[v]->cnt++;
 
		if (i + r[i] >= f + r[f]) f = i;
	}

	if (ssize(s) >= 2 * 100'001 + 1) {
		cout << 0 << '\n';
		return 0;
	}
	ll res = dfs(Node[0]);

	delete Node[0];

	cout << res << '\n';

	return 0;
}

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