oj.uz

Submission #106248

# Submission time Handle Problem Language Result Execution time Memory
106248 2019-04-17T16:21:40 Z ToMo01 Palindromes (APIO14_palindrome) C++17
0 / 100
 49 ms 35968 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] = 1;
		} 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 32124 KB Output is correct
2 Incorrect 32 ms 31992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31992 KB Output is correct
2 Correct 25 ms 32128 KB Output is correct
3 Correct 25 ms 32128 KB Output is correct
4 Correct 28 ms 32120 KB Output is correct
5 Correct 25 ms 32000 KB Output is correct
6 Incorrect 31 ms 31992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 32220 KB Output is correct
2 Correct 29 ms 32248 KB Output is correct
3 Incorrect 27 ms 32120 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 33436 KB Output is correct
2 Correct 33 ms 33400 KB Output is correct
3 Correct 33 ms 32888 KB Output is correct
4 Correct 33 ms 32916 KB Output is correct
5 Correct 34 ms 33280 KB Output is correct
6 Correct 36 ms 33024 KB Output is correct
7 Incorrect 33 ms 32888 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 35964 KB Output is correct
2 Correct 49 ms 35968 KB Output is correct
3 Incorrect 36 ms 34176 KB Output isn't correct
4 Halted 0 ms 0 KB -