oj.uz

Submission #18117

# Submission time Handle Problem Language Result Execution time Memory
18117 2016-01-21T12:12:21 Z comet Palindromes (APIO14_palindrome) C++
23 / 100
 1000 ms 47644 KB 
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<int> vec;
typedef vector<vec> mat;
mat path;
#define pb push_back
#define MOD (ll)(1e9+9)
ll p=209;

int N;
char a[300010],b[600010];

ll d[600010];
ll pk[600010];
ll Hash[600010];

map<ll,ll> ID;
ll sz;

ll cnt[300010],len[300010];

void init(){

	for(int i=0;i<N;i++){
		b[2*i+1]=a[i];
	}

	int n=2*N+1;

	pk[0]=1;
	for(int i=1;i<n;i++){
		pk[i]=(pk[i-1]*p)%MOD;
	}

	ll sum=0;
	for(int i=0;i<n;i++){
		Hash[i]=(sum*p+b[i])%MOD;
		sum=Hash[i];
	}

	ID[0]=sz++;

	for(int i=0;i<N;i++){
		if(ID.find(a[i])==ID.end()){
			ID[a[i]]=sz++;
			len[sz-1]=1;
		}
	}

	for(int i=0;i<N;i++){
		path[0].pb(ID[a[i]]);
	}

}


ll query(int L,int R){
	if(L==0)return Hash[R];
	int dx=R-L+1;
	return (Hash[R]-(Hash[L-1]*pk[dx])%MOD+MOD)%MOD;
}

void output(int L,int R){
	for(int i=L;i<=R;i++){
		printf("%c ",b[i]);
	}
	printf(" : %lld\n",query(L,R));
}

void push(int L,int R){
	if(L%2==0)return;
	// printf("push %d~%d\n",L,R);

	// output(L,R);

	if(ID.find(query(L,R))==ID.end()){
		ID[query(L,R)]=sz++;
		len[ID[query(L,R)]]=(R-L+2)/2;
	}

	// printf("id : %lld\n",ID[query(L,R)]);

	if(L+2==R){
		path[0].pb(ID[query(L,R)]);
	}
	if(L+2<=R-2){
		path[ID[query(L+2,R-2)]].pb(ID[query(L,R)]);
	}

	// printf("len : %lld\n",len[ID[query(L,R)]]);
}

void add(int L,int R){
	if(L%2==0)return;
	// printf("add %d~%d\n",L,R);

	// output(L,R);
	cnt[ID[query(L,R)]]++;

	// printf("cnt : %lld\n",cnt[ID[query(L,R)]]);
}

void manacher(){

	int n=2*N+1,k=0,l,r;
	for(int i=0;i<n;i++){
		if(d[k]+k>i){
			d[i]=min(d[k]+k-i,d[2*k-i]);
			if(i+d[i]==d[k]+k){
				l=i+d[i],r=i-d[i];
				while(l>=0&&r<n&&b[l]==b[r]){
					l--,r++;
					d[i]++;
					push(i-d[i]+1,i+d[i]-1);
				}
			}
		}else{
			l=r=i;
			while(l>=0&&r<n&&b[l]==b[r]){
				l--,r++;
				d[i]++;
				push(i-d[i]+1,i+d[i]-1);
			}
		}

		if(d[i]>1){
			add(i-d[i]+2,i+d[i]-2);
		}
	}
/*
	for(int i=0;i<n;i++){
		printf("%c",b[i]);
	}
	puts("");

	for(int i=0;i<n;i++){
		printf("%d ",d[i]);
	}
	puts("");*/
}

bool chk[300010];
ll ans=0;

ll dfs(int v){
	chk[v]=1;
	ll z=cnt[v];
	for(int i=0;i<path[v].size();i++){
		int u=path[v][i];
		if(chk[u])continue;
		z+=dfs(u);
	}

	// printf("%d (%lld,%lld) : %lld \n",v,len[v],cnt[v],z);

	ans=max(ans,z*len[v]);
	return z;
}

int main(){

	scanf("%s",a);

	N=strlen(a);
	path.assign(N+1,vec());

	init();
	manacher();
	dfs(0);

	printf("%lld\n",ans);
	return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 22828 KB Output is correct - answer is '124251'
2 Correct 27 ms 22168 KB Output is correct - answer is '38226'
3 Correct 143 ms 24808 KB Output is correct - answer is '249500'
4 Correct 3 ms 21640 KB Output is correct - answer is '5778'
5 Correct 139 ms 24808 KB Output is correct - answer is '247506'
6 Correct 137 ms 24808 KB Output is correct - answer is '248004'
7 Correct 0 ms 21640 KB Output is correct - answer is '973'
8 Correct 70 ms 22828 KB Output is correct - answer is '123753'
9 Correct 0 ms 21640 KB Output is correct - answer is '2346'
10 Correct 0 ms 21508 KB Output is correct - answer is '53'
11 Correct 0 ms 21508 KB Output is correct - answer is '52'
12 Correct 0 ms 21508 KB Output is correct - answer is '976'

Subtask #3
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 47644 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -