oj.uz

Submission #223919

# Submission time Handle Problem Language Result Execution time Memory
223919 2020-04-16T20:47:51 Z lucas110550 Palindromes (APIO14_palindrome) C++14
0 / 100
 75 ms 65528 KB 
#include <bits/stdc++.h>

using namespace std;

char str[300005];
int n;
int len[300005], ch[300005][26];
int r[300005], f[300005];
char s[101];
int h, t, cnt;
long long sum = 0;
int st, ed;
vector<int> E[300005];

void init() {
	for (int i = 0; i < 2; i ++) memset(ch[i], 0, sizeof(ch[i]));
	len[0] = 0; len[1] = -1;
	f[0] = 1; f[1] = 1;
	st = ed = 0;
	cnt = 1;
	sum = 0;
}

bool valid(int x) {
	return 1 <= x && x <= t;
}

void front_ins(int x) {
	while (!valid(x + len[st] + 1) || str[x + len[st] + 1] != str[x]) st = f[st];
	if (!ch[st][str[x] - 'a']) {
		int j = f[st];
		while (!valid(x + len[j] + 1) || str[x + len[j] + 1] != str[x]) j = f[j];
		len[++ cnt] = len[st] + 2;
		int ff = ch[j][str[x] - 'a'];
		f[cnt] = ff;
		E[ff].push_back(cnt);
		ch[st][str[x] - 'a'] = cnt;
		memset(ch[cnt], 0, sizeof(ch[cnt]));
		r[cnt] ++;
	}
	st = ch[st][str[x] - 'a'];
//	sum += r[st];
	if (len[st] == t - h) ed = st;
}

void back_ins(int x) {
	while (!valid(x - len[ed] - 1) || str[x - len[ed] - 1] != str[x]) ed = f[ed];
	if (!ch[ed][str[x] - 'a']) {
		int j = f[ed];
		while (!valid(x - len[j] - 1) || str[x - len[j] - 1] != str[x]) j = f[j];
		len[++ cnt] = len[ed] + 2;
		int ff = ch[j][str[x] - 'a'];
		f[cnt] = ff;
		E[ff].push_back(cnt);
		ch[ed][str[x] - 'a'] = cnt;
		memset(ch[cnt], 0, sizeof(ch[cnt]));
		r[cnt] ++;
	}
	ed = ch[ed][str[x] - 'a'];
//	sum += r[ed];
	if (len[ed] == t - h) st = ed;
}

void dfs(int x) {
	for (int i = 0; i < (int )E[x].size(); i ++) { 
		dfs(E[x][i]);
		r[x] += r[E[x][i]];
	}
}

int main( ) {
	init();
	scanf("%s", str + 1);
	n = (int )strlen(str + 1);
	for (int i = 1; i <= n; i ++) {
		++ t;
		back_ins(i);
	}
	dfs(0);
	for (int i = 2; i <= cnt; i ++) {
		sum = max(sum, 1LL * r[i] * len[i]);
	}
	printf("%lld\n", sum);
	return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", str + 1);
  ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 8 ms 7424 KB Output is correct
6 Correct 8 ms 7424 KB Output is correct
7 Correct 9 ms 7424 KB Output is correct
8 Correct 10 ms 7424 KB Output is correct
9 Correct 10 ms 7424 KB Output is correct
10 Correct 10 ms 7424 KB Output is correct
11 Correct 9 ms 7424 KB Output is correct
12 Correct 9 ms 7424 KB Output is correct
13 Correct 9 ms 7424 KB Output is correct
14 Incorrect 8 ms 7424 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7552 KB Output is correct
2 Correct 9 ms 7552 KB Output is correct
3 Correct 9 ms 7552 KB Output is correct
4 Correct 9 ms 7680 KB Output is correct
5 Correct 9 ms 7552 KB Output is correct
6 Correct 10 ms 7552 KB Output is correct
7 Correct 9 ms 7552 KB Output is correct
8 Correct 9 ms 7552 KB Output is correct
9 Correct 8 ms 7552 KB Output is correct
10 Incorrect 10 ms 7424 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9088 KB Output is correct
2 Correct 10 ms 8960 KB Output is correct
3 Correct 12 ms 9344 KB Output is correct
4 Correct 12 ms 9216 KB Output is correct
5 Correct 12 ms 8704 KB Output is correct
6 Correct 10 ms 8832 KB Output is correct
7 Correct 10 ms 8960 KB Output is correct
8 Incorrect 9 ms 7552 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24448 KB Output is correct
2 Correct 25 ms 23424 KB Output is correct
3 Correct 26 ms 26752 KB Output is correct
4 Correct 27 ms 25088 KB Output is correct
5 Correct 33 ms 20096 KB Output is correct
6 Correct 23 ms 17792 KB Output is correct
7 Correct 21 ms 20224 KB Output is correct
8 Incorrect 11 ms 7680 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 58488 KB Output is correct
2 Correct 53 ms 53368 KB Output is correct
3 Correct 64 ms 65528 KB Output is correct
4 Correct 55 ms 56560 KB Output is correct
5 Correct 75 ms 46456 KB Output is correct
6 Correct 57 ms 48376 KB Output is correct
7 Correct 47 ms 44800 KB Output is correct
8 Incorrect 15 ms 8192 KB Output isn't correct
9 Halted 0 ms 0 KB -