oj.uz

Submission #474027

# Submission time Handle Problem Language Result Execution time Memory
474027 2021-09-16T15:43:27 Z jangwonyoung Palindromes (APIO14_palindrome) C++14
100 / 100
 210 ms 98904 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=3e5+5;
int n;
string s;
int f[226];

int sz=1;
const int ts=6e5+5;
int ch[ts][26];
int fa[ts],len[ts];
int mp[ts];
int king[N];
vector<int>adj[ts];
int rsz[ts];

int fi[ts],pl[ts];
void dfs(int id){
	for(auto c:adj[id]){
		dfs(c);
		rsz[id]+=rsz[c];
	}
}
void dfs2(int id){
	for(auto c:adj[id]){
		dfs2(c);
		if(fi[c]!=0){
			int i=fi[c];
			int cl=len[id];
			int x=id;
			if(i+cl-1>=mp[x]){
				if(mp[x]-i+1>len[fa[x]]){
					pl[x]=mp[x]-i+1;
				}
			}
			fi[id]=max(fi[id],fi[c]);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	for(int i='a'; i<='z' ;i++) f[i]=i-'a';
	cin >> s;n=s.size();s='?'+s;
	int x=1;
	for(int i=1; i<=n ;i++){
		char c=s[i];
		int y=++sz;len[y]=i;
		while(x && !ch[x][f[c]]){
			ch[x][f[c]]=y;
			x=fa[x];
		}
		if(!x){
			fa[y]=1;
		}
		else if(len[x]+1==len[ch[x][f[c]]]){
			fa[y]=ch[x][f[c]];
		}
		else{
			int w=ch[x][f[c]];
			int z=++sz;len[z]=len[x]+1;
			for(int j=0; j<26 ;j++) ch[z][j]=ch[w][j];
			fa[z]=fa[w];fa[w]=z;
			while(ch[x][f[c]]==w){
				ch[x][f[c]]=z;
				x=fa[x];
			}
			fa[y]=z;
		}
		king[i]=x=y;
	}
	for(int i=2; i<=ts ;i++){
		adj[fa[i]].push_back(i);
	}
	for(int i=n; i>=1 ;i--){
		int x=king[i];
		while(!mp[x]){
			mp[x]=i;x=fa[x];
		}
		rsz[king[i]]++;
	}
	dfs(1);
	x=1;
	int cl=0;
	for(int i=n; i>=1 ;i--){
		char c=s[i];
		while(ch[x][f[c]]==0){
			x=fa[x];
			cl=len[x];
		}
		x=ch[x][f[c]];
		cl++;
		if(fi[x]==0) fi[x]=i;
		if(i+cl-1>=mp[x]){
			if(mp[x]-i+1>len[fa[x]]){
				pl[x]=mp[x]-i+1;
			}
		}
	}
	dfs2(1);
	ll ans=0;
	for(int i=1; i<=sz ;i++){
		//cout << pl[i] << '\n';
		if(pl[i]!=0) ans=max(ans,1LL*pl[i]*rsz[i]);
	}
	cout << ans << '\n';
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:51:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   51 |   while(x && !ch[x][f[c]]){
      |                       ^
palindrome.cpp:52:12: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |    ch[x][f[c]]=y;
      |            ^
palindrome.cpp:58:33: warning: array subscript has type 'char' [-Wchar-subscripts]
   58 |   else if(len[x]+1==len[ch[x][f[c]]]){
      |                                 ^
palindrome.cpp:59:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   59 |    fa[y]=ch[x][f[c]];
      |                  ^
palindrome.cpp:62:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |    int w=ch[x][f[c]];
      |                  ^
palindrome.cpp:66:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   66 |    while(ch[x][f[c]]==w){
      |                  ^
palindrome.cpp:67:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   67 |     ch[x][f[c]]=z;
      |             ^
palindrome.cpp:89:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   89 |   while(ch[x][f[c]]==0){
      |                 ^
palindrome.cpp:93:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   93 |   x=ch[x][f[c]];
      |             ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 18628 KB Output is correct
2 Correct 16 ms 18584 KB Output is correct
3 Correct 16 ms 18628 KB Output is correct
4 Correct 19 ms 18628 KB Output is correct
5 Correct 19 ms 18628 KB Output is correct
6 Correct 16 ms 18628 KB Output is correct
7 Correct 17 ms 18628 KB Output is correct
8 Correct 16 ms 18628 KB Output is correct
9 Correct 16 ms 18628 KB Output is correct
10 Correct 16 ms 18636 KB Output is correct
11 Correct 17 ms 18644 KB Output is correct
12 Correct 16 ms 18628 KB Output is correct
13 Correct 17 ms 18636 KB Output is correct
14 Correct 16 ms 18628 KB Output is correct
15 Correct 16 ms 18628 KB Output is correct
16 Correct 16 ms 18628 KB Output is correct
17 Correct 17 ms 18628 KB Output is correct
18 Correct 16 ms 18696 KB Output is correct
19 Correct 16 ms 18700 KB Output is correct
20 Correct 16 ms 18620 KB Output is correct
21 Correct 17 ms 18624 KB Output is correct
22 Correct 16 ms 18624 KB Output is correct
23 Correct 16 ms 18624 KB Output is correct
24 Correct 16 ms 18624 KB Output is correct
25 Correct 19 ms 18704 KB Output is correct
26 Correct 16 ms 18616 KB Output is correct
27 Correct 16 ms 18628 KB Output is correct
28 Correct 16 ms 18712 KB Output is correct
29 Correct 17 ms 18708 KB Output is correct
30 Correct 16 ms 18628 KB Output is correct
31 Correct 17 ms 18632 KB Output is correct
32 Correct 17 ms 18660 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 18892 KB Output is correct
2 Correct 16 ms 18884 KB Output is correct
3 Correct 16 ms 18756 KB Output is correct
4 Correct 17 ms 18836 KB Output is correct
5 Correct 16 ms 18756 KB Output is correct
6 Correct 16 ms 18756 KB Output is correct
7 Correct 17 ms 18748 KB Output is correct
8 Correct 16 ms 18740 KB Output is correct
9 Correct 18 ms 18900 KB Output is correct
10 Correct 18 ms 18756 KB Output is correct
11 Correct 19 ms 18804 KB Output is correct
12 Correct 18 ms 18880 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 20156 KB Output is correct
2 Correct 19 ms 21012 KB Output is correct
3 Correct 19 ms 20168 KB Output is correct
4 Correct 20 ms 21016 KB Output is correct
5 Correct 18 ms 19940 KB Output is correct
6 Correct 20 ms 20820 KB Output is correct
7 Correct 19 ms 21180 KB Output is correct
8 Correct 19 ms 20260 KB Output is correct
9 Correct 19 ms 20288 KB Output is correct
10 Correct 19 ms 20428 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 35856 KB Output is correct
2 Correct 41 ms 39728 KB Output is correct
3 Correct 37 ms 38948 KB Output is correct
4 Correct 45 ms 41152 KB Output is correct
5 Correct 39 ms 30728 KB Output is correct
6 Correct 47 ms 36996 KB Output is correct
7 Correct 47 ms 42744 KB Output is correct
8 Correct 61 ms 34188 KB Output is correct
9 Correct 53 ms 38060 KB Output is correct
10 Correct 61 ms 38244 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 74200 KB Output is correct
2 Correct 114 ms 98904 KB Output is correct
3 Correct 79 ms 83548 KB Output is correct
4 Correct 94 ms 95652 KB Output is correct
5 Correct 131 ms 59940 KB Output is correct
6 Correct 134 ms 93992 KB Output is correct
7 Correct 142 ms 98340 KB Output is correct
8 Correct 179 ms 69288 KB Output is correct
9 Correct 192 ms 69392 KB Output is correct
10 Correct 210 ms 78008 KB Output is correct
11 Correct 84 ms 67924 KB Output is correct
12 Correct 171 ms 73648 KB Output is correct