oj.uz

Submission #288921

# Submission time Handle Problem Language Result Execution time Memory
288921 2020-09-02T07:21:03 Z Namnamseo Palindromes (APIO14_palindrome) C++17
73 / 100
 1000 ms 78712 KB 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
using ll=long long;
#define pb push_back
#define rep(i,n) for(int i=0;i<n;++i)

const int maxn = int(6e5) + 10;

char s[maxn];
int n;

int nxt[maxn][27];
int fn[maxn][27];
int cnt[maxn], dep[maxn], par[maxn];
int myv[maxn];

int rad[maxn];
int here[maxn];
int nn, root;

int G(int v, int i) {
	if (!nxt[v][i]) {
		nxt[v][i] = ++nn;
		dep[nn] = dep[v] + 1;
		par[nn] = v;
	}
	return nxt[v][i];
}

int main() {
	scanf("%s", s);
	n = strlen(s);

	{ // inflate
		for (int i=n-1; 0<=i; --i) s[2*i+1] = s[i];
		for (int i=0; i<=n; ++i) s[2*i] = '{';
		n = 2*n+1;
	}

	// manacher
	for (int i=0, b=0; i<n; ++i) {
		int r=0;
		if (i<=b+rad[b]) r=min(b+rad[b]-i, rad[2*b-i]);
		while (i+r+1<n && i-r-1>=0 &&
			s[i+r+1] == s[i-r-1]) ++r;
		rad[i]=r;
		if (b+rad[b] < i+rad[i]) {
			for(int j=b+rad[b]+1; j<=i+rad[i]; ++j) here[j]=i;
			b=i;
		}
	}

	// ptree
	root = ++nn;
	for (int i=0; i<n; ++i) {
		int t = here[i];
		int len = i-t;
		int p;
		if (len == 0) p = root;
		else {
			int b = i-1, l = len-1;
			while (here[b] != b-l) b = 2*here[b] - (b-l) +l;
			p = myv[b];
		}
		myv[i] = G(p, s[i]-'a');
		par[myv[i]] = p;
	}

	rep(i, n) {
		int len = rad[i], b = i+len, p;
		if (len == 0) p = G(root, s[i]-'a');
		else { while (here[b] != b-len) b = 2*here[b]-(b-len)+len; p = myv[b]; }
		++cnt[p];
	}

	for (int i=nn; 1<=i; --i) cnt[par[i]] += cnt[i];
	ll ans = 0;
	for(int i=1; i<=nn; ++i) ans = max(ans, (dep[i]-1)*1ll*cnt[i]);

	printf("%lld\n", ans);

	return 0;
}

Compilation message

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

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2944 KB Output is correct
2 Correct 3 ms 2944 KB Output is correct
3 Correct 3 ms 2944 KB Output is correct
4 Correct 3 ms 2944 KB Output is correct
5 Correct 3 ms 2944 KB Output is correct
6 Correct 3 ms 2944 KB Output is correct
7 Correct 3 ms 2944 KB Output is correct
8 Correct 6 ms 640 KB Output is correct
9 Correct 7 ms 768 KB Output is correct
10 Correct 3 ms 2176 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 26496 KB Output is correct
2 Correct 23 ms 26496 KB Output is correct
3 Correct 24 ms 26496 KB Output is correct
4 Correct 23 ms 26496 KB Output is correct
5 Correct 26 ms 26488 KB Output is correct
6 Correct 21 ms 20088 KB Output is correct
7 Correct 23 ms 22784 KB Output is correct
8 Correct 577 ms 3192 KB Output is correct
9 Correct 355 ms 8440 KB Output is correct
10 Correct 27 ms 22912 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 78712 KB Output is correct
2 Correct 68 ms 78712 KB Output is correct
3 Correct 68 ms 78628 KB Output is correct
4 Correct 71 ms 78712 KB Output is correct
5 Correct 78 ms 78712 KB Output is correct
6 Correct 67 ms 70776 KB Output is correct
7 Correct 66 ms 66808 KB Output is correct
8 Execution timed out 1085 ms 7428 KB Time limit exceeded
9 Halted 0 ms 0 KB -