Submission #849273

#	Time	Username	Problem	Language	Result	Execution time	Memory
849273		IBory	Palindromes (APIO14_palindrome)	C++17	73 / 100	1064 ms	96044 KiB

palindrome

#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const ll MAX = 600006, MOD1 = 998244353, MOD2 = 846545669;
char C[MAX];
int P[MAX];
ll D[2][MAX], IP[2][MAX], ans;
map<ll, ll> cnt, Z;
map<ll, vector<ll>> G;

ll Pow(ll N, ll K, const ll MOD) {
	ll ret = 1;
	while (K) {
		if (K & 1) ret = ret * N % MOD;
		N = N * N % MOD;
		K >>= 1LL;
	}
	return ret;
}

ll Hash(int L, int R) {
	if (L > R) return -1;
	R++;
	ll a = (D[0][R] - D[0][L] + MOD1) * IP[0][L] % MOD1;
	ll b = (D[1][R] - D[1][L] + MOD2) * IP[1][L] % MOD2;
	return (a << 31LL) + b;
}

ll DFS(ll cur) {
	ll n = cnt[cur];
	for (ll next : G[cur]) n += DFS(next);
	ans = max(ans, n * Z[cur]);
	return n;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	string A, B;
	cin >> A;
	for (char c : A) {
		B.push_back(c);
		B.push_back('_');
	}
	B.pop_back();

	int N = A.size(), M = B.size();
	D[0][0] = D[1][0] = IP[0][0] = IP[1][0] = 1;
	ll p1 = 1, p2 = 1, ip1 = Pow(313, MOD1 - 2, MOD1), ip2 = Pow(479, MOD2 - 2, MOD2);
	for (int i = 0; i < N; ++i) {
		C[i] = A[i];
		D[0][i + 1] = (D[0][i] + C[i] * p1) % MOD1;
		D[1][i + 1] = (D[1][i] + C[i] * p2) % MOD2;
		IP[0][i + 1] = IP[0][i] * ip1 % MOD1;
		IP[1][i + 1] = IP[1][i] * ip2 % MOD2;
		p1 = p1 * 313 % MOD1;
		p2 = p2 * 479 % MOD2;
	}
	
	int R = -1, K = -1;
	for (int i = 0; i < M; ++i) {
		if (i <= R) P[i] = min(R - i, P[2 * K - i]);
		while (i - P[i] - 1 >= 0 && i + P[i] + 1 < M && B[i - P[i] - 1] == B[i + P[i] + 1]) P[i]++;
		if (R < i + P[i]) R = i + P[i], K = i;
	}

	for (int i = 0; i < M; ++i) {
		int l = i - P[i], r = i + P[i];
		if (l & 1) l++;
		if (r & 1) r--;
		if (l > r) continue;
		l >>= 1, r >>= 1;
		ll pv = 0, cur = Hash(l, r), cut = Z.find(cur) != Z.end();
		cnt[cur]++;
		Z[cur] = r - l + 1;
		do {
			if (pv) G[cur].push_back(pv);
			if (cut) break;
			pv = cur;
			l++; r--;
			if (l <= r) {
				cur = Hash(l, r);
				if (Z.find(cur) != Z.end()) cut = 1;
				else Z[cur] = r - l + 1;
			}
		} while (l <= r);
		if (l > r) G[0].push_back(cur);
	}

	DFS(0);
	cout << ans;
	return 0;
}

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