Submission #7554

#	Time	Username	Problem	Language	Result	Execution time	Memory
7554		hongjun7	Palindromes (APIO14_palindrome)	C++98	73 / 100	1000 ms	28740 KiB

palindrome

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdlib>
using namespace std;
#define rep(i,n) for(int (i)=(0);(i)<(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
#define fi first
#define se second
typedef long long ll;
char s[300010];
char tmp[600020];
int rad[600020];
int N;
void manacher() {
	rep(i,N*2+1)tmp[i]='#';
	rep(i,N)tmp[i*2+1]=s[i];
	int i=0,j=0;
	int n=N*2+1;
	for(int i=0;i<n;) {
		while(i-j>=0&&i+j<n&&tmp[i-j]==tmp[i+j])j++;
		rad[i]=j;
		int k=1;
		while(rad[i-k]<rad[i]-k)rad[i+k]=rad[i-k],k++;
		i+=k;
		j=max(0,j-k);
	}
}
int sa[300001],ra[300001],sak;
int ti[300001];
int lcp[300001];
bool cmp_sa(int a,int b) {
	if(ra[a]!=ra[b])return ra[a]<ra[b];
	int cha=(a+sak<=N)?ra[a+sak]:-1;
	int chb=(b+sak<=N)?ra[b+sak]:-1;
	return cha<chb;
}
void construct_sa(int n) {
	rep(i,n+1) {
		sa[i]=i;
		ra[i]=(i<n)?s[i]:-1;
	}
	for(sak=1;sak<n;sak*=2) {
		sort(sa,sa+n+1,cmp_sa);
		ti[sa[0]]=0;
		for(int i=1;i<=n;i++)ti[sa[i]]=ti[sa[i-1]]+cmp_sa(sa[i-1],sa[i]);
		rep(i,n+1)ra[i]=ti[i];
	}
}
void construct_lcp(int n) {
	rep(i,n+1)ti[sa[i]]=i;
	int h=0, j;
	rep(i,n) {
		j=sa[ti[i]-1];
		if(h>0)h--;
		while(i+h<n&&j+h<n&&s[i+h]==s[j+h])h++;
		lcp[ti[i]]=h;
	}
}
struct UnionFind {
	int par[300001],ra[300001],sz[300001];
	void init(){rep(i,300001)par[i]=i,ra[i]=0,sz[i]=0;}
	int find(int x){return par[x]==x?x:par[x]=find(par[x]);}
	bool same(int a,int b){return find(a)==find(b);}
	void unite(int a,int b){if((a=find(a))!=(b=find(b))){if(ra[a]<ra[b])swap(ra[a],ra[b]);sz[a]+=sz[b];par[b]=a,ra[a]+=ra[a]==ra[b];}}
} uf;
int main() {
	gets(s);
	ll ans=0;
	N=strlen(s);
	manacher();
	construct_sa(N);
	construct_lcp(N);
	vector<pip> lun;
	repn(i,1,N+1)lun.pb(mp(lcp[i],mp(sa[i-1],sa[i])));
	sort(lun.rbegin(),lun.rend());
	uf.init();
	vector<pii> aq;
	rep(i,N)aq.pb(mp(rad[i*2+1]/2,i));
	sort(aq.rbegin(),aq.rend());
	int ptr=0, ppuf;
	rep(i,N) {
		while(ptr<N&&lun[ptr].fi>=aq[i].fi) {
			uf.unite(lun[ptr].second.first,lun[ptr].second.second);
			ptr++;
		}
		ppuf=uf.find(aq[i].se);
		uf.sz[ppuf]++;
		ans=max(ans,ll(uf.sz[ppuf])*(aq[i].first*2-1));
	}
	uf.init();
	aq.clear();
	rep(i,N)aq.pb(mp(rad[i*2]/2,i));
	sort(aq.rbegin(),aq.rend());
	ptr=0;
	rep(i,N) {
		while(ptr<N&&lun[ptr].fi>=aq[i].fi) {
			uf.unite(lun[ptr].second.first,lun[ptr].second.second);
			ptr++;
		}
		ppuf=uf.find(aq[i].se);
		uf.sz[ppuf]++;
		ans=max(ans,ll(uf.sz[ppuf])*(aq[i].first*2));
	}
	printf("%lld",ans);
}

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