Submission #969983

#	Time	Username	Problem	Language	Result	Execution time	Memory
969983		TranGiaHuy1508	Palindromes (APIO14_palindrome)	C++17	100 / 100	57 ms	66152 KiB

palindrome

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

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

template <class T, class Adj>
struct PalindromeTree {
	vector<int> len, link, occur;
	vector<Adj> nxt;

	PalindromeTree(){
		len = vector<int>{0, -1};
		link = vector<int>{1, 0};
		occur = vector<int>{1, 0};
		nxt = vector<Adj>(2);
	}
	PalindromeTree(const vector<T> &str): PalindromeTree() {
		add(str);
	}

	int new_node(int length, int sfx_link){
		len.push_back(length);
		link.push_back(sfx_link);
		nxt.emplace_back();
		occur.push_back(0);
		return (int)len.size() - 1;
	}

	vector<T> s = {-1};
	int last = 0;

	void add(T c){
		s.push_back(c);
		int crr = last;
		while (s[(int)s.size() - len[crr] - 2] != c) crr = link[crr];
		if (!nxt[crr][c]){
			int u = link[crr];
			while (s[(int)s.size() - len[u] - 2] != c) u = link[u];
			int v = new_node(len[crr] + 2, nxt[u][c]);
			nxt[crr][c] = v;
		}
		last = nxt[crr][c];
		occur[last]++;
	}
	void add(const vector<T> &str){
		for (auto c: str) add(c);
	}

	vector<int> cnt;
	vector<vector<int>> inv_link;

	void dfs(int x){
		for (auto child: inv_link[x]){
			dfs(child);
			cnt[x] += cnt[child];
		}
	}

	int size() const { return len.size(); }

	void init_count(){
		cnt = occur;
		inv_link.assign(size(), {});

		for (int i = 2; i < size(); i++) inv_link[link[i]].push_back(i);
		dfs(0);
	}
};

void main_program(){
	string s; cin >> s;

	vector<int> v(s.size());
	for (int i = 0; i < (int)s.size(); i++){
		v[i] = s[i] - 'a';
	}

	PalindromeTree<int, array<int, 26>> tree(v);
	tree.init_count();

	long long res = 0;
	for (int i = 2; i < (int)tree.size(); i++){
		res = max(res, 1LL * tree.len[i] * tree.cnt[i]);
	}

	cout << res << "\n";
}

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