Submission #1117893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117893		mat_jur	Palindromes (APIO14_palindrome)	C++17	100 / 100	105 ms	79208 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];
	vector<pair<trie_node*, int>> e;
	int cnt;

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

int add_edge(trie_node *v, char c) {
	int x = c - 'a';
	int idx = 0;
	while (idx < ssize(v->e) && v->e[idx].se != x) idx++;
	if (idx != ssize(v->e)) return idx;
	trie_node *u = new trie_node;
	v->e.eb(mp(u, x));

	u->depth = v->depth + 1;
	u->parent = v;
	return idx;
}

ll dfs(trie_node *v) {
	ll res = 0;
	for (auto [u, x] : v->e) {
		res = max(res, dfs(u));
		v->cnt += u->cnt;
	}

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

const int N = 300'000;
trie_node* Node[2*N+3];

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;

	int idx = add_edge(Node[0], s[0]);
	Node[1] = Node[0]->e[idx].fi;

	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]]) {
			int j = add_edge(Node[v], s[i+r[i]]);
			Node[v] = Node[v]->e[j].fi;
			r[i]++;
		}

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

	ll res = dfs(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: 27 / 27