oj.uz

Submission #262094

# Submission time Handle Problem Language Result Execution time Memory
262094 2020-08-12T10:46:57 Z mohamedsobhi777 Palindromes (APIO14_palindrome) C++14
100 / 100
 96 ms 41076 KB 
//#include "elephants.h"
#include<bits/stdc++.h>

#define I inline void 

using namespace std ; 

using ld = long double ; 
using ll = long long ; 

const int N = 3e5  + 7 , mod = 1e9 + 7 ; 

int n;
ll ans ; 
string s;
int num , suf ; 

struct node{
	int nxt[26] ; 
	int len ; 
	int num ; 
	int occ ; 
	int lazy ; 
	int suflnk ; 
} tree[N] ; 


bool addL(int pos){
	int cur = suf , curlen = 0 ; 
	int let = s[pos] - 'a' ; 

	while(1){
		curlen = tree[cur].len ;
		if(pos - 1 - curlen >=0 && s[pos - 1 - curlen ] == s[pos])
			break ; 
		cur = tree[cur].suflnk ;
	}

	if(tree[cur].nxt[let]){
		suf = tree[cur].nxt[let] ; 
		tree[suf].lazy++ ; 
		return 0 ; 
	}

	num ++ ;
	suf = num ;
	tree[num].len = tree[cur].len + 2 ; 
	
	tree[cur].nxt[let] = num ;

	tree[num].lazy ++ ;  

	if(tree[num].len == 1){
		tree[num].suflnk = 2 ; 
		tree[num].lazy = 1; 
		return 1 ; 
	}

	while(1){
		cur = tree[cur].suflnk ; 
		curlen = tree[cur].len ; 
		if(pos -1 - curlen >= 0 && s[pos] == s[pos - 1 - curlen ]){
			tree[num].suflnk = tree[cur].nxt[let] ; 
			break ;
		}
	}

	tree[num].num = 1 + tree[tree[num].suflnk].num ; 

	return 1 ; 
}

I init(){
	suf = num = 2 ; 
	tree[1].len = -1 ; 
	tree[2].len = 0 ; 
	tree[1].suflnk = 1 ; 
	tree[2].suflnk = 1 ; 
}

int pal[N] ; 
int vis[N] ; 

int main(){

	ios_base::sync_with_stdio(0) ; 
	cin.tie(0) ; 
	//freopen("in.in" , "r" , stdin) ; 
	init() ; 
	cin >> s ; 
	n = (int) s.size() ; 
	for(int i = 0 ;i < n ;i++){
		addL(i) ; 
	}	

	priority_queue<int> q ; 

	for(int i = 3 ;i <=num ;i++){
		q.push(i) ; 
	}
	while(q.size()){
		int ret = q.top() ; q.pop() ; 
		if(vis[ret]++)continue ; 
		pal[ret] = tree[ret].lazy ;
		if(tree[ret].suflnk > 2){
			tree[tree[ret].suflnk].lazy+=tree[ret].lazy ; 
			q.push(tree[ret].suflnk) ; 
		}
	}

	for(int i = 3 ;i <= num ;i++){
		ans = max(ans , 1ll * tree[i].len * pal[i] ) ; 
	}

	cout<< ans << endl; 
	return 0 ; 
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 0 ms 384 KB Output is correct
25 Correct 0 ms 384 KB Output is correct
26 Correct 0 ms 384 KB Output is correct
27 Correct 0 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 0 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 0 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 512 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1792 KB Output is correct
2 Correct 3 ms 1792 KB Output is correct
3 Correct 3 ms 1792 KB Output is correct
4 Correct 4 ms 1792 KB Output is correct
5 Correct 3 ms 1792 KB Output is correct
6 Correct 3 ms 1792 KB Output is correct
7 Correct 4 ms 1792 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 2 ms 1280 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 14012 KB Output is correct
2 Correct 27 ms 14012 KB Output is correct
3 Correct 28 ms 14012 KB Output is correct
4 Correct 39 ms 14004 KB Output is correct
5 Correct 31 ms 14012 KB Output is correct
6 Correct 23 ms 10556 KB Output is correct
7 Correct 29 ms 12092 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 8 ms 3840 KB Output is correct
10 Correct 29 ms 12092 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 40820 KB Output is correct
2 Correct 87 ms 40816 KB Output is correct
3 Correct 87 ms 40820 KB Output is correct
4 Correct 88 ms 40820 KB Output is correct
5 Correct 96 ms 40820 KB Output is correct
6 Correct 84 ms 36724 KB Output is correct
7 Correct 83 ms 34424 KB Output is correct
8 Correct 7 ms 1288 KB Output is correct
9 Correct 7 ms 1288 KB Output is correct
10 Correct 81 ms 33912 KB Output is correct
11 Correct 82 ms 41076 KB Output is correct
12 Correct 13 ms 4872 KB Output is correct