oj.uz

Submission #80048

# Submission time Handle Problem Language Result Execution time Memory
80048 2018-10-18T13:16:23 Z Mahdi_Jfri Palindromes (APIO14_palindrome) C++14
0 / 100
 1000 ms 50124 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back

const int maxn = 6e5 + 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;
		}

	cout << 1/0;

	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;
}

Compilation message

palindrome.cpp: In function 'void buildTrie(int, int, int, int)':
palindrome.cpp:126:11: warning: division by zero [-Wdiv-by-zero]
  cout << 1/0;
          ~^~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 14 ms 14588 KB Output is correct
3 Correct 14 ms 14588 KB Output is correct
4 Correct 14 ms 14588 KB Output is correct
5 Incorrect 18 ms 14588 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

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

Subtask #3
0 / 24.0

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

Subtask #4
0 / 26.0

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

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 42600 KB Output is correct
2 Correct 937 ms 42600 KB Output is correct
3 Correct 643 ms 50124 KB Output is correct
4 Correct 927 ms 50124 KB Output is correct
5 Execution timed out 1084 ms 50124 KB Time limit exceeded
6 Halted 0 ms 0 KB -