Submission #46629

#	Time	Username	Problem	Language	Result	Execution time	Memory
46629		aome	Palindromes (APIO14_palindrome)	C++17	73 / 100	1051 ms	53752 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

const int N = 300005;
const int base = 5102000;
const int mod[] = {(int)1e9 + 7, (int)1e9 + 123};

int n;
int cnt;
int f[N];
int sz[N];
int pw[2][N];
int hsh[2][2][N];
long long res;
vector<int> G[N];
string s;
map< pair<int, int>, int > label;

inline int get0(int t, int l, int r) {
	int ret = hsh[t][0][r] - 1LL * hsh[t][0][l - 1] * pw[t][r - l + 1] % mod[t];
	if (ret < 0) ret += mod[t]; return ret;
}

inline int get1(int t, int l, int r) {
	int ret = hsh[t][1][l] - 1LL * hsh[t][1][r + 1] * pw[t][r - l + 1] % mod[t];
	if (ret < 0) ret += mod[t]; return ret;
}

inline pair<int, int> get0(int l, int r) {
	return make_pair(get0(0, l, r), get0(1, l, r));
}

inline pair<int, int> get1(int l, int r) {
	return make_pair(get1(0, l, r), get1(1, l, r));
}

void go(int l, int r) {
	// cout << "# " << l << ' ' << r << '\n';
	pair<int, int> tmp;
	int id, lst;
	tmp = get0(l, r), id = label[tmp];
	if (!id) {
		label[tmp] = id = ++cnt;
		sz[id] = r - l + 1, f[id]++;
		lst = id, l++, r--;
	}
	else {
		f[id]++; return;
	}
	while (l <= r) {
		tmp = get0(l, r), id = label[tmp];
		if (!id) {
			label[tmp] = id = ++cnt;
			sz[id] = r - l + 1;		
			G[id].push_back(lst);
			lst = id, l++, r--;
		}
		else {
			G[id].push_back(lst);
			return;
		}
	}
	if (l > r) G[0].push_back(lst);
}

void dfs(int u) {
	for (auto v : G[u]) {
		dfs(v), f[u] += f[v];
	}
	res = max(res, 1LL * sz[u] * f[u]);
}

int main() {
	ios::sync_with_stdio(false);
	cin >> s, n = s.size();
	for (int t = 0; t <= 1; ++t) {
		pw[t][0] = 1;
		for (int i = 1; i <= n; ++i) {
			pw[t][i] = 1LL * pw[t][i - 1] * base % mod[t];
		}
		for (int i = 1; i <= n; ++i) {
			hsh[t][0][i] = (1LL * hsh[t][0][i - 1] * base + s[i - 1] - 'a' + 1) % mod[t];
		}
		for (int i = n; i >= 1; --i) {
			hsh[t][1][i] = (1LL * hsh[t][1][i + 1] * base + s[i - 1] - 'a' + 1) % mod[t];
		}
	}
	for (int i = 1; i <= n; ++i) {
		int l, r; 
		l = 1, r = min(i, n - i + 1);
		while (l < r) {
			int mid = (l + r + 1) >> 1;
			if (get0(i - mid + 1, i) == get1(i, i + mid - 1)) l = mid;
			else r = mid - 1;
		}
		go(i - l + 1, i + l - 1);
		l = 0, r = min(i, n - i);
		while (l < r) {
			int mid = (l + r + 1) >> 1;
			if (get0(i - mid + 1, i) == get1(i + 1, i + mid)) l = mid;
			else r = mid - 1;
		}
		if (l) go(i - l + 1, i + l);
	}
	assert(cnt <= n);
	dfs(0);
	cout << res;
}

Compilation message (stderr)

palindrome.cpp: In function 'int get0(int, int, int)':
palindrome.cpp:22:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (ret < 0) ret += mod[t]; return ret;
  ^~
palindrome.cpp:22:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (ret < 0) ret += mod[t]; return ret;
                              ^~~~~~
palindrome.cpp: In function 'int get1(int, int, int)':
palindrome.cpp:27:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (ret < 0) ret += mod[t]; return ret;
  ^~
palindrome.cpp:27:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (ret < 0) ret += mod[t]; return ret;
                              ^~~~~~

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