Submission #367135

#	Time	Username	Problem	Language	Result	Execution time	Memory
367135		alireza_kaviani	Palindromes (APIO14_palindrome)	C++11	100 / 100	85 ms	65524 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)						(x).begin(),(x).end()
#define X							first
#define Y							second
#define sep							' '
#define endl						'\n'
#define SZ(x)						ll(x.size())

const ll MAXN = 3e5 + 10;
const ll LOG = 26;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

int n , palPrv , nxt[MAXN][LOG] , par[MAXN] , len[MAXN] , val[MAXN];
ll ans = 0;
vector<int> adj[MAXN];
string s;

void DFS(int v){
	for(int u : adj[v]){
//		cout << v << sep << u << endl;
		DFS(u);
		val[v] += val[u];
	}
	ans = max(ans , 1ll * val[v] * len[v]);
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> s; n = SZ(s);
	len[0] = -1; len[1] = 0;
	par[1] = 0; palPrv = 1;
	adj[0].push_back(1);
	for(int i = 0 ; i < n ; i++){
		int prv = palPrv , ch = s[i] - 97;
//		cout << i << sep << prv << endl;
		while(1){
			int k = len[prv];
//			cout << i << sep << prv << sep << k << endl;
			if(0 <= i - k - 1 && s[i] == s[i - k - 1])	break;
			prv = par[prv];
		}
//		cout << i << sep << prv << endl;
		if(nxt[prv][ch] != 0){
			palPrv = nxt[prv][ch];
			val[palPrv]++;
			continue;
		}
		int cur = i + 2;
		//cout << prv << sep << cur << endl;
		palPrv = cur; val[cur]++;
		nxt[prv][ch] = cur;
		len[cur] = len[prv] + 2;
		if(len[cur] == 1){
			par[cur] = 1;
			adj[1].push_back(cur);
			continue;
		}
		while(1){
			prv = par[prv];
			int k = len[prv];
			if(0 <= i - k - 1 && s[i] == s[i - k - 1])	break;
		}
		par[cur] = nxt[prv][ch];
		adj[nxt[prv][ch]].push_back(cur);
	}
	DFS(0);
	cout << ans << endl;

    return 0;
}
/*

*/

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