oj.uz

Submission #46622

# Submission time Handle Problem Language Result Execution time Memory
46622 2018-04-22T11:55:35 Z aome Palindromes (APIO14_palindrome) C++17
47 / 100
 733 ms 40452 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 300005;
const int base = 26;
const int mod = 1e9 + 7;

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

void go(int l, int r) {
	// cout << "# " << l << ' ' << r << '\n';
	int tmp, 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();
	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 (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

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 8 ms 7416 KB Output is correct
2 Correct 7 ms 7592 KB Output is correct
3 Correct 8 ms 7592 KB Output is correct
4 Correct 7 ms 7592 KB Output is correct
5 Correct 8 ms 7592 KB Output is correct
6 Correct 8 ms 7592 KB Output is correct
7 Correct 7 ms 7592 KB Output is correct
8 Correct 8 ms 7592 KB Output is correct
9 Correct 7 ms 7720 KB Output is correct
10 Correct 7 ms 7720 KB Output is correct
11 Correct 7 ms 7720 KB Output is correct
12 Correct 7 ms 7720 KB Output is correct
13 Correct 7 ms 7720 KB Output is correct
14 Correct 7 ms 7720 KB Output is correct
15 Correct 8 ms 7776 KB Output is correct
16 Correct 7 ms 7776 KB Output is correct
17 Correct 7 ms 7776 KB Output is correct
18 Correct 7 ms 7776 KB Output is correct
19 Correct 7 ms 7776 KB Output is correct
20 Correct 8 ms 7776 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 8 ms 7776 KB Output is correct
25 Correct 8 ms 7776 KB Output is correct
26 Correct 7 ms 7776 KB Output is correct
27 Correct 8 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 9 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 7804 KB Output is correct
2 Correct 8 ms 7804 KB Output is correct
3 Correct 8 ms 7804 KB Output is correct
4 Correct 9 ms 7804 KB Output is correct
5 Correct 9 ms 7808 KB Output is correct
6 Correct 8 ms 7808 KB Output is correct
7 Correct 8 ms 7808 KB Output is correct
8 Correct 8 ms 7808 KB Output is correct
9 Correct 8 ms 7808 KB Output is correct
10 Correct 7 ms 7808 KB Output is correct
11 Correct 9 ms 7808 KB Output is correct
12 Correct 8 ms 7808 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8828 KB Output is correct
2 Correct 17 ms 8828 KB Output is correct
3 Correct 19 ms 8828 KB Output is correct
4 Correct 25 ms 8828 KB Output is correct
5 Correct 20 ms 8828 KB Output is correct
6 Correct 15 ms 8876 KB Output is correct
7 Correct 17 ms 8876 KB Output is correct
8 Correct 10 ms 8876 KB Output is correct
9 Correct 11 ms 8876 KB Output is correct
10 Correct 13 ms 8876 KB Output is correct

Subtask #4
0 / 26.0

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

Subtask #5
0 / 27.0

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