Submission #1086881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086881		Drifter24	Palindromes (APIO14_palindrome)	C++14	100 / 100	23 ms	36904 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
#define print(arr) for(auto& x:arr)cout<<x<<" ";cout<<"\n"
#define watch(x) cout<<#x<<"="<<x<<"\n"
#define all(x) x.begin(), x.end()
#define sz(x) ((int) x.size())
typedef long long ll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

const int alpha = 26;
const char fc = 'a';

struct Node{
    int next[alpha];
    int len,link,dep,cnt;
};

struct PalindromeTree{
	vector<Node> tree; 
	string s;
	int len,n;
	int size;            // node 1 - root with len -1, node 2 - root with len 0
	int suff;           // max suffix palindrome

	bool addLetter(int pos){
		int cur=suff,curlen=0;
		int let=s[pos]-fc;
		while(true){
			curlen=tree[cur].len;
			if(pos-1-curlen>=0 && s[pos-1-curlen]==s[pos])break;  
			cur=tree[cur].link;
		}      

		if(tree[cur].next[let]){  
			suff=tree[cur].next[let];
			tree[suff].cnt++;
			return false;
		}

		size++;
		suff=size;
		tree[size].len=tree[cur].len+2;
		tree[cur].next[let]=size;
		tree[size].cnt=1;

		if(tree[size].len==1){
			tree[size].link=2;
			tree[size].dep=1;
			return true;
		}

		while(true){
			cur=tree[cur].link;
			curlen=tree[cur].len;
			if(pos-1-curlen>=0 && s[pos-1-curlen]==s[pos]){
				tree[size].link=tree[cur].next[let];
				break;
			}       
		}           

		tree[size].dep=1+tree[tree[size].link].dep;
		return true;
	}

	void build(string s2, int n){
		tree.assign(n+4,Node());
		tree[1].len=-1;tree[1].link=1;
		tree[2].len=0;tree[2].link=1;
		size=2;suff=2;s=s2;

		for(int i=0;i<n;i++){
			addLetter(i);
		}

		for(int i=size;i>=3;i--){
			tree[tree[i].link].cnt+=tree[i].cnt;
		}
	}
};


int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
    string s;
	cin>>s;
	PalindromeTree pt;
	pt.build(s,sz(s));
	ll ans=0;
	for(int i=3;i<=pt.size;i++){
		ans=max(ans, 1ll*pt.tree[i].len*pt.tree[i].cnt);
		// cout<<i<<" "<<pt.tree[i].len<<" "<<pt.tree[i].link<<" "<<pt.tree[i].dep<<" "<<pt.tree[i].cnt<<"\n";
	}
	cout<<ans<<"\n";
    return 0;
}

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