Submission #80045

#	Time	Username	Problem	Language	Result	Execution time	Memory
80045		Mahdi_Jfri	Palindromes (APIO14_palindrome)	C++14	0 / 100	755 ms	53280 KiB

palindrome

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

#define ll long long
#define pb push_back

const int maxn = 3e5 + 20;

string S;
int N, gap;
int sa[maxn], pos[maxn], tmp[maxn], lcp[maxn] , mn[maxn * 4];

vector<int> adj[maxn];

int sz[maxn] , w[maxn] , id = 1;

inline bool sufCmp(int i, int j)
{
	if (pos[i] != pos[j])
		return pos[i] < pos[j];
	i += gap;
	j += gap;
	return (i < N && j < N) ? pos[i] < pos[j] : i > j;
}

inline void buildSA()
{
	N = S.size();
	for(int i = 0; i < N; i++) sa[i] = i, pos[i] = S[i];
	for (gap = 1;; gap *= 2)
	{
		sort(sa, sa + N, sufCmp);
		for(int i = 0; i < N - 1; i++) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]);
		for(int i = 0; i < N; i++) pos[sa[i]] = tmp[i];
		if (tmp[N - 1] == N - 1) break;
	}
}

inline void buildLCP()
{
	for (int i = 0, k = 0; i < N; ++i) if (pos[i] != N - 1)
	{
		for (int j = sa[pos[i] + 1]; S[i + k] == S[j + k];)
			++k;
		lcp[pos[i]] = k;
		if (k)--k;
	}
}

void buildSeg(int s = 0 , int e = N - 1 , int v = 1)
{
	if(e - s < 2)
	{
		mn[v] = lcp[s];

		return;
	}

	int m = (s + e) / 2;

	buildSeg(s , m , 2 * v);
	buildSeg(m , e , 2 * v + 1);

	mn[v] = min(mn[2 * v] , mn[2 * v + 1]);
}

int GetLcp(int l , int r , int s = 0 , int e = N - 1 , int v = 1)
{
	if(l <= s && e <= r)
		return mn[v];
	if(r <= s || e <= l)
		return maxn;

	int m = (s + e) / 2;

	return min(GetLcp(l , r , s , m , 2 * v) , GetLcp(l , r , m , e , 2 * v + 1));
}

void buildTrie(int l = 0 , int r = N - 1 , int root = 0 , int K = 0)
{
	if(l == r)
	{
		if(N - sa[l] != K)
		{
			adj[root].pb(id);
			w[id] = N - sa[l] - K;
			sz[id++] = 1;
		}
		else
			sz[root]++;

		return;
	}

	int lcp = GetLcp(l , r) - K;

	if(lcp != 0)
	{
		adj[root].pb(id);
		w[id] = lcp;
		id++;
		buildTrie(l , r , id - 1 , K + lcp);

		return;
	}

	if(GetLcp(l , l + 1) - K == 0)
	{
		buildTrie(l , l , root , K);
		buildTrie(l + 1 , r , root , K);

		return;
	}

	int L = l + 1 , R = r;

	for(int i = r - 1; i >= l; i--)
		if(GetLcp(l , i) - K != 0)
		{
			buildTrie(l , i , root , K);
			buildTrie(i + 1 , r , root , K);

			return;
		}

	while(R - L > 1)
	{
		int M = (L + R) / 2;

		if(GetLcp(l , M) - K == 0)
			R = M;
		else
			L = M;
	}

	buildTrie(l , L , root , K);
	buildTrie(L + 1 , r , root , K);
}

ll res;

void dfs(int v , int d = 0)
{
	for(auto u : adj[v])
	{
		dfs(u , d + w[u]);
		sz[v] += sz[u];
	}

	res = max(res , 1LL * d * sz[v]);
}

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

	cin >> S;

	buildSA();
	buildLCP();
	buildSeg();
	buildTrie();
	
	dfs(0);
	cout << res << endl;
}

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