Submission #367171

#	Time	Username	Problem	Language	Result	Execution time	Memory
367171		Bill_00	Palindromes (APIO14_palindrome)	C++14	47 / 100	102 ms	131076 KiB

palindrome

#include <bits/stdc++.h>
#define NN 300005
#define pb push_back
typedef long long ll;
using namespace std;
ll ans;
struct pal{
	ll cnt;
	pal *a[26];
	pal *b[20];
	ll h;
}*root=new pal(),*root1=new pal();
pal *u,*ptr[NN];
void ins(pal *rt,ll k){
	if(rt->a[k]==NULL){
		rt->a[k]=new pal();
		for(ll i=0;i<20;i++){
			(rt->a[k])->b[i]=new pal();
		}
		(rt->a[k])->b[0]=rt;
		for(ll i=1;i<20;i++){
			(rt->a[k])->b[i]=((rt->a[k])->b[i-1])->b[i-1];
		}	
		(rt->a[k])->h=(rt->h)+1;
	} 
	u=rt->a[k];
}
void solve(pal *rt,ll length,bool b){
	// if(rt==root1) cout << "KK" << '\n';
	for(ll i=0;i<26;i++){
		if(rt->a[i]!=NULL){
			solve(rt->a[i],length+1,b);
			// cout << i << ' ' << (rt->a[i])->cnt << '\n';
			rt->cnt+=((rt->a[i])->cnt);
		}
	}
	ans=max(ans,(rt->cnt)*(b==1?(length*2-1):(length*2)));
}
int main(){
	for(ll i=0;i<20;i++){
		root->b[i]=new pal();
		root1->b[i]=new pal();
		root->b[i]=root;
		root1->b[i]=root1;
	}
	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];
    			// cout << i << '\n';
    		}
    		else{
    			// cout << "K" << '\n';
    			u=ptr[l+r-i];
    			for(ll j=19;j>=0;j--){
    				if(((u->b[j])->h)>=(r-i+1)){
    					u=u->b[j];	
    				} 
    			}
    		}
    	}
    	else ins(root,(s[i]-'a'));
    	while (0 <= i - k && i + k < n && s[i - k] == s[i + k]){
    		// cout << i << ' ' << k << '\n';
    		ins(u,(s[i-k]-'a'));
       		k++;
    	}
    	d1[i] = k--;
    	// cout << d1[i] << ' ' << i << '\n';
    	ptr[i]=u;
    	(u->cnt)++;
    	// cout << u->cnt << '\n';
    	if (i + k > r) {
       		l = i - k;
        	r = i + k;
    	}
	}
	solve(root,0,1);
	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{
				u=ptr[l+r-i+1];
				for(ll j=19;j>=0;j--){
					if(((u->b[j])->h)>=(r-i+1)){
    					u=u->b[j];	
    				} 
				}
			}
		} 
		else u=root1;
		while(0<=i-k-1 && i+k<n && s[i-k-1]==s[i+k]){
			// cout << i << ' ' << k << '\n';
			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: 0 / 26
• Subtask 5: 0 / 27