oj.uz

Submission #46629

# Submission time Handle Problem Language Result Execution time Memory
46629 2018-04-22T12:07:32 Z aome Palindromes (APIO14_palindrome) C++17
73 / 100
 1000 ms 53752 KB 
#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

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

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 9168 KB Output is correct
2 Correct 21 ms 9168 KB Output is correct
3 Correct 23 ms 9212 KB Output is correct
4 Correct 22 ms 9212 KB Output is correct
5 Correct 18 ms 9212 KB Output is correct
6 Correct 19 ms 9212 KB Output is correct
7 Correct 20 ms 9212 KB Output is correct
8 Correct 13 ms 9212 KB Output is correct
9 Correct 13 ms 9212 KB Output is correct
10 Correct 17 ms 9212 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 22708 KB Output is correct
2 Correct 239 ms 22708 KB Output is correct
3 Correct 304 ms 22708 KB Output is correct
4 Correct 275 ms 22708 KB Output is correct
5 Correct 193 ms 22708 KB Output is correct
6 Correct 155 ms 22708 KB Output is correct
7 Correct 207 ms 22708 KB Output is correct
8 Correct 78 ms 22708 KB Output is correct
9 Correct 97 ms 22708 KB Output is correct
10 Correct 161 ms 22708 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 921 ms 53028 KB Output is correct
2 Correct 864 ms 53028 KB Output is correct
3 Execution timed out 1051 ms 53752 KB Time limit exceeded
4 Halted 0 ms 0 KB -