Submission #367261

#	Time	Username	Problem	Language	Result	Execution time	Memory
367261		Bill_00	Palindromes (APIO14_palindrome)	C++14	100 / 100	192 ms	110220 KiB

palindrome

#include <bits/stdc++.h>
#define NN 300000
#define pb push_back
typedef int ll;
using namespace std;
long long ans;
int w=0;
int b[20][NN];
struct pal{
	ll cnt;
	pal *a[26];
	ll h;
	ll id;
}*root=new pal(),*root1=new pal();
pal *u,*ptr[NN],*p[NN];
void ins(pal *rt,ll k){
	if(rt->a[k]==NULL){
		rt->a[k]=new pal();	
		(rt->a[k])->h=(rt->h)+1;
		rt->a[k]->id=++w;
		b[0][w]=rt->id;
		for(int i=1;i<20;i++){
			b[i][w]=b[i-1][b[i-1][w]];
		}
		p[w]=rt->a[k];
	} 
	u=rt->a[k];
}
int solve(pal *rt,ll length,bool b){
	for(ll i=0;i<26;i++){
		if(rt->a[i]!=NULL){
			rt->cnt+=(solve(rt->a[i],length+1,b));
		}
	}
	ans=max(ans,(long long)((long long)(rt->cnt)*(long long)(b==1?(length*2-1):(length*2))));
	int o=rt->cnt;
	delete(rt);
	rt=NULL;
	return o;
}
int main(){
	p[0]=root;
	string s;
	cin >> s;
	ll n=s.size();
	vector<ll>d1(n);
	for (ll i = 0, l = 0, r = -1; i < n; i++) {
    	ll k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
    	if(r>=i){
    		if(d1[l+r-i]<=(r-i+1)){
    			u=ptr[l+r-i];
    		}
    		else{
    			int y=ptr[l+r-i]->id;
    			for(ll j=19;j>=0;j--){
    				if(((p[b[j][y]])->h)>=(r-i+1)){
    					y=b[j][y];	
    				} 
    			}
    			u=p[y];
    		}
    	}
    	else ins(root,(s[i]-'a'));
    	while (0 <= i - k && i + k < n && s[i - k] == s[i + k]){
    		ins(u,(s[i-k]-'a'));
       		k++;
    	}
    	d1[i] = k--;
    	ptr[i]=u;
    	(u->cnt)++;
    	if (i + k > r) {
       		l = i - k;
        	r = i + k;
    	}
	}
	solve(root,0,1);
	p[0]=root1;
	vector<ll>d2(n);
	for(ll i=0,l=0,r=-1;i<n;i++){
		ll k=((i>r)?0:min(d2[l+r-i+1],r-i+1));
		if(r>=i){
			if(d2[l+r-i+1]<=r-i+1){
				u=ptr[l+r-i+1];
			}	
			else{
				int y=ptr[l+r-i+1]->id;
				for(ll j=19;j>=0;j--){
					if(((p[b[j][y]])->h)>=(r-i+1)){
    					y=b[j][y];	
    				} 
				}
				u=p[y];
			}
		} 
		else u=root1;
		while(0<=i-k-1 && i+k<n && s[i-k-1]==s[i+k]){
			ins(u,(s[i+k]-'a'));
			k++;
		}
		d2[i]=k--;
		ptr[i]=u;
		(u->cnt)++;
		if(i+k>r){
			l=i-k-1;
			r=i+k;
		}
	}
	solve(root1,0,0);
	cout << ans;
}

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