oj.uz

Submission #46673

# Submission time Handle Problem Language Result Execution time Memory
46673 2018-04-22T14:27:38 Z aome Palindromes (APIO14_palindrome) C++17
47 / 100
 806 ms 40168 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 300005;
const int base = 404;
const int mod = 1e9 + 9;
 
int n;
int cnt;
int f[N];
int sz[N];
int pw[N];
int hsh[2][N];
long long res;
vector<int> G[N];
string s;
map<int, int> label;
 
inline int get0(int l, int r) {
	int ret = hsh[0][r] - 1LL * hsh[0][l - 1] * pw[r - l + 1] % mod;
	if (ret < 0) ret += mod; return ret;
}
 
inline int get1(int l, int r) {
	int ret = hsh[1][l] - 1LL * hsh[1][r + 1] * pw[r - l + 1] % mod;
	if (ret < 0) ret += mod; return ret;
}

inline int get2(int l, int r) {
	return 1LL * get0(l, r) * get1(l, r) % mod;
}

bool check(int l, int r) {
	return get0(l, r) == get1(l, r);
}
 
void go(int l, int r) {
	// cout << "# " << l << ' ' << r << '\n';
	int tmp, id, lst;
	tmp = get2(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 = get2(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();
	pw[0] = 1;
	for (int i = 1; i <= n; ++i) {
		pw[i] = 1LL * pw[i - 1] * base % mod;
	}
	for (int i = 1; i <= n; ++i) {
		hsh[0][i] = (1LL * hsh[0][i - 1] * base + s[i - 1] - 'a' + 1) % mod;
	}
	for (int i = n; i >= 1; --i) {
		hsh[1][i] = (1LL * hsh[1][i + 1] * base + s[i - 1] - 'a' + 1) % mod;
	}
	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 (check(i - mid + 1, 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 (check(i - mid + 1, i + mid)) l = mid;
			else r = mid - 1;
		}
		if (l) go(i - l + 1, i + l);
	}
	dfs(0);
	cout << res;
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 7 ms 7416 KB Output is correct
3 Correct 7 ms 7448 KB Output is correct
4 Correct 7 ms 7448 KB Output is correct
5 Correct 7 ms 7508 KB Output is correct
6 Correct 7 ms 7508 KB Output is correct
7 Correct 7 ms 7584 KB Output is correct
8 Correct 7 ms 7600 KB Output is correct
9 Correct 7 ms 7600 KB Output is correct
10 Correct 8 ms 7604 KB Output is correct
11 Correct 7 ms 7604 KB Output is correct
12 Correct 7 ms 7604 KB Output is correct
13 Correct 7 ms 7604 KB Output is correct
14 Correct 15 ms 7604 KB Output is correct
15 Correct 7 ms 7604 KB Output is correct
16 Correct 7 ms 7604 KB Output is correct
17 Correct 7 ms 7604 KB Output is correct
18 Correct 7 ms 7604 KB Output is correct
19 Correct 7 ms 7604 KB Output is correct
20 Correct 7 ms 7604 KB Output is correct
21 Correct 7 ms 7776 KB Output is correct
22 Correct 7 ms 7776 KB Output is correct
23 Correct 7 ms 7776 KB Output is correct
24 Correct 7 ms 7776 KB Output is correct
25 Correct 7 ms 7776 KB Output is correct
26 Correct 7 ms 7776 KB Output is correct
27 Correct 7 ms 7776 KB Output is correct
28 Correct 7 ms 7776 KB Output is correct
29 Correct 7 ms 7776 KB Output is correct
30 Correct 7 ms 7776 KB Output is correct
31 Correct 7 ms 7776 KB Output is correct
32 Correct 7 ms 7776 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7780 KB Output is correct
2 Correct 8 ms 7780 KB Output is correct
3 Correct 8 ms 7780 KB Output is correct
4 Correct 7 ms 7780 KB Output is correct
5 Correct 8 ms 7780 KB Output is correct
6 Correct 8 ms 7824 KB Output is correct
7 Correct 7 ms 7824 KB Output is correct
8 Correct 10 ms 7824 KB Output is correct
9 Correct 9 ms 7824 KB Output is correct
10 Correct 8 ms 7824 KB Output is correct
11 Correct 7 ms 7824 KB Output is correct
12 Correct 8 ms 7840 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8852 KB Output is correct
2 Correct 19 ms 8852 KB Output is correct
3 Correct 20 ms 8852 KB Output is correct
4 Correct 33 ms 8852 KB Output is correct
5 Correct 15 ms 8852 KB Output is correct
6 Correct 19 ms 8852 KB Output is correct
7 Correct 17 ms 8852 KB Output is correct
8 Correct 11 ms 8852 KB Output is correct
9 Correct 10 ms 8852 KB Output is correct
10 Correct 14 ms 8852 KB Output is correct

Subtask #4
0 / 26.0

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

Subtask #5
0 / 27.0

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