Submission #344219

#	Time	Username	Problem	Language	Result	Execution time	Memory
344219		aZvezda	Palindromes (APIO14_palindrome)	C++14	100 / 100	84 ms	73844 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

const ll MAX_N = 1e6 + 10;
struct PalindromicTree {
	map<char, ll> mp[MAX_N];
	ll link[MAX_N], len[MAX_N], times[MAX_N];
	ll cnt, last;
	void init() {
		for(ll i = 0; i < cnt; i ++) {
			mp[i].clear();
		}
		cnt = 2;
		last = 1;
		len[0] = -1; link[0] = 0;
		len[1] = 0; link[1] = 0;
	}
	void build(const string &text) {
		for(ll i = 0; i < text.size(); i ++) {
			while(true) {
				if(text[i - len[last] - 1] == text[i]) {
					ll curr;
					if(mp[last].find(text[i]) == mp[last].end()) {
						curr = cnt ++;
						mp[last][text[i]] = curr;
					} else {
						curr = mp[last][text[i]];
					}
					len[curr] = len[last] + 2;

					while(true) {
						if(text[i - len[last] - 1] == text[i] && mp[last].find(text[i]) != mp[last].end() && mp[last][text[i]] != curr) {
							link[curr] = mp[last][text[i]];
							break;
						} else if(last == 0) {
							link[curr] = 1;
							break;
						} else {
							last = link[last];
						}
					}
					last = curr;

					break;
				} else {
					last = link[last];
				}
			}
			times[last] ++;
		}
	}
	void dfs(int x, string out) {
		for(auto it : mp[x]) {
			if(x == 0) {
				dfs(it.second, string(1, it.first));
			} else {
				dfs(it.second, string(1, it.first) + out + string(1, it.first));
			}
		}
	}
	ll getAns() {
		ll ret = -1;
		for(ll i = cnt - 1; i >= 0; i --) {
			times[link[i]] += times[i];
			chkmax(ret, (ll)times[i] * (ll)len[i]);
		}
		return ret;
	}
};

PalindromicTree pt;

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	string in;
	cin >> in;
	pt.init();
	pt.build(in);
	cout << pt.getAns() << endl;
	return 0;	
	pt.dfs(0, "");
	pt.dfs(1, "");
	return 0;
}

Compilation message (stderr)

palindrome.cpp: In member function 'void PalindromicTree::build(const string&)':
palindrome.cpp:29:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(ll i = 0; i < text.size(); i ++) {
      |                 ~~^~~~~~~~~~~~~

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