Submission #288921

#	Time	Username	Problem	Language	Result	Execution time	Memory
288921		Namnamseo	Palindromes (APIO14_palindrome)	C++17	73 / 100	1085 ms	78712 KiB

palindrome

#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 (stderr)

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 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 0 / 27