oj.uz

답안 #80044

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
80044 2018-10-18T12:56:34 Z Mahdi_Jfri 회문 (APIO14_palindrome) C++14
0 / 100
 1000 ms 36220 KB 
#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;

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

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;

	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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7716 KB Output is correct
3 Correct 8 ms 7800 KB Output is correct
4 Correct 8 ms 7800 KB Output is correct
5 Incorrect 8 ms 7800 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 8948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 223 ms 16960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 746 ms 36220 KB Output is correct
2 Execution timed out 1078 ms 36220 KB Time limit exceeded
3 Halted 0 ms 0 KB -