oj.uz

Submission #7554

# Submission time Handle Problem Language Result Execution time Memory
7554 2014-08-11T07:03:48 Z hongjun7 Palindromes (APIO14_palindrome) C++
73 / 100
 1000 ms 28740 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12644 KB Output is correct - answer is '7'
2 Correct 0 ms 12644 KB Output is correct - answer is '4'
3 Correct 0 ms 12644 KB Output is correct - answer is '9'
4 Correct 0 ms 12644 KB Output is correct - answer is '1'
5 Correct 4 ms 12644 KB Output is correct - answer is '1'
6 Correct 0 ms 12644 KB Output is correct - answer is '2'
7 Correct 0 ms 12644 KB Output is correct - answer is '3'
8 Correct 0 ms 12644 KB Output is correct - answer is '3'
9 Correct 0 ms 12644 KB Output is correct - answer is '15'
10 Correct 0 ms 12644 KB Output is correct - answer is '24'
11 Correct 0 ms 12644 KB Output is correct - answer is '10'
12 Correct 0 ms 12644 KB Output is correct - answer is '24'
13 Correct 0 ms 12644 KB Output is correct - answer is '25'
14 Correct 0 ms 12644 KB Output is correct - answer is '28'
15 Correct 0 ms 12644 KB Output is correct - answer is '2'
16 Correct 0 ms 12644 KB Output is correct - answer is '1'
17 Correct 0 ms 12644 KB Output is correct - answer is '15'
18 Correct 0 ms 12644 KB Output is correct - answer is '18'
19 Correct 0 ms 12644 KB Output is correct - answer is '1176'
20 Correct 0 ms 12644 KB Output is correct - answer is '1225'
21 Correct 0 ms 12644 KB Output is correct - answer is '136'
22 Correct 0 ms 12644 KB Output is correct - answer is '45'
23 Correct 0 ms 12644 KB Output is correct - answer is '2500'
24 Correct 0 ms 12644 KB Output is correct - answer is '380'
25 Correct 4 ms 12644 KB Output is correct - answer is '2304'
26 Correct 0 ms 12644 KB Output is correct - answer is '110'
27 Correct 4 ms 12644 KB Output is correct - answer is '93'
28 Correct 0 ms 12644 KB Output is correct - answer is '729'
29 Correct 0 ms 12644 KB Output is correct - answer is '132'
30 Correct 0 ms 12644 KB Output is correct - answer is '7'
31 Correct 0 ms 12644 KB Output is correct - answer is '8'
32 Correct 4 ms 12644 KB Output is correct - answer is '64'

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12644 KB Output is correct - answer is '124251'
2 Correct 0 ms 12644 KB Output is correct - answer is '38226'
3 Correct 4 ms 12644 KB Output is correct - answer is '249500'
4 Correct 4 ms 12644 KB Output is correct - answer is '5778'
5 Correct 4 ms 12644 KB Output is correct - answer is '247506'
6 Correct 4 ms 12644 KB Output is correct - answer is '248004'
7 Correct 4 ms 12644 KB Output is correct - answer is '973'
8 Correct 4 ms 12644 KB Output is correct - answer is '123753'
9 Correct 0 ms 12644 KB Output is correct - answer is '2346'
10 Correct 4 ms 12644 KB Output is correct - answer is '53'
11 Correct 0 ms 12644 KB Output is correct - answer is '52'
12 Correct 4 ms 12644 KB Output is correct - answer is '976'

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13028 KB Output is correct - answer is '12497500'
2 Correct 16 ms 13028 KB Output is correct - answer is '6481800'
3 Correct 16 ms 13028 KB Output is correct - answer is '25000000'
4 Correct 16 ms 13028 KB Output is correct - answer is '17816841'
5 Correct 16 ms 13028 KB Output is correct - answer is '9945'
6 Correct 16 ms 13028 KB Output is correct - answer is '504100'
7 Correct 16 ms 13028 KB Output is correct - answer is '1512930'
8 Correct 16 ms 13028 KB Output is correct - answer is '413'
9 Correct 16 ms 13028 KB Output is correct - answer is '428'
10 Correct 20 ms 13028 KB Output is correct - answer is '7232'

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 16740 KB Output is correct - answer is '1249925001'
2 Correct 212 ms 16464 KB Output is correct - answer is '396337935'
3 Correct 208 ms 16236 KB Output is correct - answer is '2500050000'
4 Correct 212 ms 16236 KB Output is correct - answer is '1016525689'
5 Correct 372 ms 16236 KB Output is correct - answer is '99645'
6 Correct 316 ms 16236 KB Output is correct - answer is '78569380'
7 Correct 252 ms 16236 KB Output is correct - answer is '82810000'
8 Correct 220 ms 16236 KB Output is correct - answer is '3989'
9 Correct 232 ms 16236 KB Output is correct - answer is '125529616'
10 Correct 372 ms 16236 KB Output is correct - answer is '66664'

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 784 ms 28740 KB Output is correct - answer is '11250075000'
2 Correct 896 ms 27100 KB Output is correct - answer is '894243195'
3 Correct 724 ms 26988 KB Output is correct - answer is '22499400004'
4 Correct 772 ms 26988 KB Output is correct - answer is '2958163321'
5 Execution timed out 1000 ms 26988 KB Program timed out
6 Halted 0 ms 0 KB -