oj.uz

Submission #106247

# Submission time Handle Problem Language Result Execution time Memory
106247 2019-04-17T16:20:14 Z ToMo01 Palindromes (APIO14_palindrome) C++17
100 / 100
 51 ms 36480 KB 
/*input
www
abacabaa
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 300005;
string s;
int link[N];
int val[N];
int len[N];
int adj[N][26];
int n, curNode = 1, treeSize = 1;

// 0 is even root, 1 is odd root
void build() {
	memset(adj, -1, sizeof adj);
	memset(link, -1, sizeof link);

	len[1] = -1;
	link[0] = 1, len[0] = 0;

	int tmp = 0;
	for(int i = 0; i < n; ++ i) {
		int ch = s[i] - 'a';
		for(tmp = curNode; ; tmp = link[tmp]) {
			int pos = i - len[tmp] - 1;
			if(pos >= 0 && s[pos] == s[i])
				break;
		}

		if(~adj[tmp][ch]) {
			curNode = adj[tmp][ch], ++ val[curNode]; continue;
		}

		adj[tmp][ch] = curNode = ++ treeSize;
		len[curNode] = len[tmp] + 2;

		if(len[curNode] == 1) {
			link[curNode] = 0;
		} else {
			while(1) {
				tmp = link[tmp];
				int pos = i - len[tmp] - 1;
				if(pos >= 0 && s[pos] == s[i])
					break;
			}
			link[curNode] = adj[tmp][ch];
		}
		++ val[curNode];
	}
}

int deg[N];

void bfs() {
	for(int i = 2; i <= treeSize; ++ i) ++ deg[link[i]];

	queue<int> q;
	for(int i = 2; i <= treeSize; ++ i) if(deg[i] == 0) q.push(i);

	while(!q.empty()) {
		int u = q.front(); q.pop();
		-- deg[link[u]], val[link[u]] += val[u];
		if(deg[link[u]] == 0) q.push(link[u]);
	}
}

int main(){
	iostream::sync_with_stdio(false); cin.tie(0);
	
	cin >> s;
	n = (int)s.size();
	build(), bfs();

	long long Ans = 1;
	for(int i = 2; i <= treeSize; ++ i) Ans = max(Ans, 1ll * len[i] * val[i]);
	cout << Ans << endl;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 31996 KB Output is correct
2 Correct 32 ms 31992 KB Output is correct
3 Correct 31 ms 31992 KB Output is correct
4 Correct 31 ms 32248 KB Output is correct
5 Correct 30 ms 32128 KB Output is correct
6 Correct 28 ms 31992 KB Output is correct
7 Correct 29 ms 32128 KB Output is correct
8 Correct 29 ms 32128 KB Output is correct
9 Correct 30 ms 32120 KB Output is correct
10 Correct 29 ms 32100 KB Output is correct
11 Correct 29 ms 32100 KB Output is correct
12 Correct 31 ms 31996 KB Output is correct
13 Correct 30 ms 32128 KB Output is correct
14 Correct 31 ms 32028 KB Output is correct
15 Correct 26 ms 31992 KB Output is correct
16 Correct 25 ms 31992 KB Output is correct
17 Correct 25 ms 32100 KB Output is correct
18 Correct 30 ms 32056 KB Output is correct
19 Correct 29 ms 31992 KB Output is correct
20 Correct 29 ms 32120 KB Output is correct
21 Correct 25 ms 31992 KB Output is correct
22 Correct 25 ms 31992 KB Output is correct
23 Correct 27 ms 31992 KB Output is correct
24 Correct 29 ms 32128 KB Output is correct
25 Correct 29 ms 31992 KB Output is correct
26 Correct 28 ms 32000 KB Output is correct
27 Correct 29 ms 31992 KB Output is correct
28 Correct 31 ms 31992 KB Output is correct
29 Correct 27 ms 32128 KB Output is correct
30 Correct 26 ms 32128 KB Output is correct
31 Correct 32 ms 32128 KB Output is correct
32 Correct 26 ms 31992 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32128 KB Output is correct
2 Correct 32 ms 31992 KB Output is correct
3 Correct 29 ms 32120 KB Output is correct
4 Correct 27 ms 32120 KB Output is correct
5 Correct 29 ms 32128 KB Output is correct
6 Correct 29 ms 32120 KB Output is correct
7 Correct 25 ms 32120 KB Output is correct
8 Correct 26 ms 32128 KB Output is correct
9 Correct 27 ms 32100 KB Output is correct
10 Correct 25 ms 32120 KB Output is correct
11 Correct 29 ms 32120 KB Output is correct
12 Correct 30 ms 32120 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 32248 KB Output is correct
2 Correct 29 ms 32248 KB Output is correct
3 Correct 29 ms 32220 KB Output is correct
4 Correct 29 ms 32220 KB Output is correct
5 Correct 31 ms 32256 KB Output is correct
6 Correct 31 ms 32120 KB Output is correct
7 Correct 30 ms 32256 KB Output is correct
8 Correct 29 ms 32068 KB Output is correct
9 Correct 29 ms 32048 KB Output is correct
10 Correct 33 ms 32116 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 33400 KB Output is correct
2 Correct 33 ms 33552 KB Output is correct
3 Correct 37 ms 33656 KB Output is correct
4 Correct 34 ms 33536 KB Output is correct
5 Correct 39 ms 33504 KB Output is correct
6 Correct 30 ms 33116 KB Output is correct
7 Correct 31 ms 33280 KB Output is correct
8 Correct 32 ms 32380 KB Output is correct
9 Correct 33 ms 32768 KB Output is correct
10 Correct 34 ms 33224 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 36196 KB Output is correct
2 Correct 40 ms 36348 KB Output is correct
3 Correct 45 ms 36352 KB Output is correct
4 Correct 44 ms 36480 KB Output is correct
5 Correct 49 ms 36224 KB Output is correct
6 Correct 51 ms 35836 KB Output is correct
7 Correct 40 ms 35644 KB Output is correct
8 Correct 34 ms 32776 KB Output is correct
9 Correct 31 ms 32772 KB Output is correct
10 Correct 39 ms 35596 KB Output is correct
11 Correct 39 ms 36352 KB Output is correct
12 Correct 34 ms 33152 KB Output is correct