oj.uz

Submission #78466

# Submission time Handle Problem Language Result Execution time Memory
78466 2018-10-05T11:47:45 Z aminra Palindromes (APIO14_palindrome) C++14
0 / 100
 755 ms 24888 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)3e5 + 3;
const int infint = (int)1e9;
string s;
int n, gap, sa[MAXN], pos[MAXN], tmp[MAXN], lcp[MAXN], par[MAXN], home[MAXN];
vector<int> oc[MAXN];
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;
}
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;
	}
}
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--;
		}
}
int get(int u)
{
	return par[u] < 0 ? u : par[u] = get(par[u]);
}
void merge(int u, int v)
{
	if((u = get(u)) == (v = get(v)))
		return;
	if(par[u] > par[v])
		swap(u, v); //par[u] > par[v]
	par[u] += par[v];
	par[v] = u;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> s;
	buildSA();
	buildLCP();
	memset(par, -1, sizeof par);
	ll ans = 0, cnt = 0;
	for (int i = 0; i < n - 1; i++)
		oc[lcp[i]].push_back(i);
	for (int i = n; i >= 0; i--)
	{
		for (auto u : oc[i])
		{
			home[u] = 1, cnt = max(1LL, cnt);
			if(u && home[u - 1] == 1)
			{
				merge(u, u - 1);
				cnt = max(cnt, (ll)-par[get(u)]);
			}
			if(home[u + 1] == 1)
			{
				merge(u, u + 1);
				cnt = max(cnt, (ll)-par[get(u)]);
			}
		}
		ans = max(ans, i * (cnt + 1));
	}
	cout << ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8568 KB Output is correct
2 Correct 9 ms 8632 KB Output is correct
3 Correct 9 ms 8772 KB Output is correct
4 Correct 10 ms 8772 KB Output is correct
5 Incorrect 8 ms 8772 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 8772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 9216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 189 ms 13944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 24300 KB Output is correct
2 Correct 523 ms 24300 KB Output is correct
3 Correct 755 ms 24888 KB Output is correct
4 Correct 550 ms 24888 KB Output is correct
5 Incorrect 697 ms 24888 KB Output isn't correct
6 Halted 0 ms 0 KB -