oj.uz

Submission #288875

# Submission time Handle Problem Language Result Execution time Memory
288875 2020-09-02T05:40:14 Z Namnamseo Palindromes (APIO14_palindrome) C++17
0 / 100
 576 ms 49272 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[300010];
int n;

int nxt[maxn][27];
int fn[maxn][27];
int fail[maxn];
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 Q[maxn], head, tail;

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, 27) {
		int v = nxt[root][i];
		if (v) { fn[root][i]=v; fail[v] = root; Q[head++] = v; }
		else fn[root][i] = root;
	}

	while (tail < head) {
		int v = Q[tail++];
		rep(i, 27) { int u = nxt[v][i];
			if (u) {
				fn[v][i]=u; fail[u]=fn[fail[v]][i]; Q[head++]=u;
			} else fn[v][i]=fn[fail[v]][i];
		}
	}

	rep(i, n) ++cnt[myv[i]];
	for(int i=tail-1; 0<=i; --i) cnt[fail[Q[i]]] += cnt[Q[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:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  scanf("%s", s);
      |  ~~~~~^~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 1 ms 896 KB Output is correct
7 Correct 1 ms 896 KB Output is correct
8 Correct 1 ms 896 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 0 ms 512 KB Output is correct
12 Incorrect 1 ms 768 KB Output isn't correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5248 KB Output is correct
2 Correct 4 ms 5248 KB Output is correct
3 Correct 5 ms 5248 KB Output is correct
4 Correct 5 ms 5248 KB Output is correct
5 Correct 5 ms 5248 KB Output is correct
6 Correct 5 ms 5248 KB Output is correct
7 Correct 5 ms 5248 KB Output is correct
8 Correct 6 ms 768 KB Output is correct
9 Correct 7 ms 768 KB Output is correct
10 Incorrect 4 ms 3840 KB Output isn't correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 49144 KB Output is correct
2 Correct 40 ms 49208 KB Output is correct
3 Correct 40 ms 49144 KB Output is correct
4 Correct 40 ms 49272 KB Output is correct
5 Correct 41 ms 49144 KB Output is correct
6 Correct 32 ms 36600 KB Output is correct
7 Correct 37 ms 42104 KB Output is correct
8 Correct 576 ms 3568 KB Output is correct
9 Correct 357 ms 13944 KB Output is correct
10 Incorrect 36 ms 42104 KB Output isn't correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 1280 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -