Submission #561529

#	Time	Username	Problem	Language	Result	Execution time	Memory
561529		maximath_1	Palindromes (APIO14_palindrome)	C++11	100 / 100	69 ms	61140 KiB

palindrome

#include <iostream>
#include <vector>
using namespace std;

#define ll long long
const int MX = 3e5 + 5;

struct palindromic_tree{
	struct node{
		int nxt[26], suff_link, len, cnt;
		vector<int> edges;
	} tree[MX];

	string s;
	int suff, num;

	void add_letter(int pos){
		int cr = suff;
		int cr_len = 0;
		int letter = s[pos] - 'a';

		for(;;){
			cr_len = tree[cr].len;
			if(pos - 1 - cr_len >= 0 && s[pos - 1 - cr_len] == s[pos]) 
				break;
			cr = tree[cr].suff_link;
		}

		if(tree[cr].nxt[letter]){
			suff = tree[cr].nxt[letter];
			tree[suff].cnt ++;
			return;
		}

		suff = num + 1; num ++;
		tree[num].len = tree[cr].len + 2;
		tree[num].cnt = 1;
		tree[cr].nxt[letter] = num;

		if(tree[num].len == 1){
			tree[num].suff_link = 2;
			tree[2].edges.push_back(num);
			return;
		}

		for(;;){
			cr = tree[cr].suff_link;
			cr_len = tree[cr].len;

			if(pos - 1 - cr_len >= 0 && s[pos - 1 - cr_len] == s[pos]){
				tree[num].suff_link = tree[cr].nxt[letter];
				tree[tree[cr].nxt[letter]].edges.push_back(num);
				break;
			}
		}
	}

	void init(){
		num = 2; suff = 2;
		tree[1].len = -1; tree[1].suff_link = 1;
		tree[2].len = 0; tree[2].suff_link = 1;
		tree[1].edges.push_back(2);
	}

	void dfs_cnt(int nw = 1){
		for(int nx : tree[nw].edges){
			dfs_cnt(nx);
			tree[nw].cnt += tree[nx].cnt;
		}
	}
} pt;

string s;

int main(){
	cin.tie(0) -> sync_with_stdio(0);

	cin >> s;
	pt.s = s;
	pt.init();
	for(int i = 0; i < s.size(); i ++)
		pt.add_letter(i);
	pt.dfs_cnt();

	ll ans = 0ll;
	for(int i = 0; i < MX; i ++)
		ans = max(ans, pt.tree[i].len * 1ll * pt.tree[i].cnt);

	cout << ans << endl;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:81:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for(int i = 0; i < s.size(); i ++)
      |                 ~~^~~~~~~~~~

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