Submission #959974

#	Time	Username	Problem	Language	Result	Execution time	Memory
959974		KasymK	Palindromes (APIO14_palindrome)	C++17	100 / 100	60 ms	74080 KiB

palindrome

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Node {
	int nxt[26], sufflink;
	ll len, cnt;
	vector<int> edges;
} tree[303030];

string s;
int suff, num;
ll ans = 0;

void add_letter(int pos) {
	int curr = suff, curr_len = 0;
	int letter = s[pos] - 'a';

	while (true) {
		curr_len = tree[curr].len;
		if (pos - 1 - curr_len > -1 && s[pos - 1 - curr_len] == s[pos]) break;
		curr = tree[curr].sufflink;
	}
	if (tree[curr].nxt[letter]) {
		suff = tree[curr].nxt[letter];
		tree[suff].cnt++;
		return;
	}

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

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

	while (true) {
		curr = tree[curr].sufflink;
		curr_len = tree[curr].len;
		if (pos - 1 - curr_len > -1 && s[pos - 1 - curr_len] == s[pos]) {
			tree[num].sufflink = tree[curr].nxt[letter];
			tree[tree[curr].nxt[letter]].edges.push_back(num);
			break;
		}
	}
}

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

void dfs(int node = 1) {
	for (int i : tree[node].edges) {
		dfs(i);
		tree[node].cnt += tree[i].cnt;
	}
	ans = max(ans, tree[node].len * tree[node].cnt);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> s;
	init();
	FOR(i, 0, s.size()) add_letter(i);
	dfs();
	cout << ans;
	return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:2:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define FOR(i, x, y) for (int i = x; i < y; i++)
......
   73 |  FOR(i, 0, s.size()) add_letter(i);
      |      ~~~~~~~~~~~~~~                     
palindrome.cpp:73:2: note: in expansion of macro 'FOR'
   73 |  FOR(i, 0, s.size()) add_letter(i);
      |  ^~~

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