Submission #83288

#	Time	Username	Problem	Language	Result	Execution time	Memory
83288		farukkastamonuda	회문 (APIO14_palindrome)	C++14	100 / 100	62 ms	41312 KiB

palindrome

#include <bits/stdc++.h>
#define li 300005
#define inf 1000000009
#define md 1000000007
#define lo long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
int n,link[li],len[li],now,lazy[li];
char s[li];
int tot=2,nxt[li][26];
stack<int> st;
lo int ans;
void add(int ind){
	while(s[ind-len[now]-1]!=s[ind]) now=link[now];
	if(nxt[now][s[ind]-'a']){
		now=nxt[now][s[ind]-'a'];
		lazy[now]++;
		return ;
	}
	int nw=++tot;
	nxt[now][s[ind]-'a']=nw;
	len[nw]=len[now]+2;
	st.push(nw);
	lazy[nw]++;
	if(len[nw]==1){
		link[nw]=2;
		now=nw;
		return ;
	}
	now=link[now];
	while(s[ind-len[now]-1]!=s[ind]) now=link[now];
	link[nw]=nxt[now][s[ind]-'a'];
	now=nw;
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	link[1]=1;link[2]=1;
	len[1]=-1;len[2]=0;
	now=1;
	for(int i=1;i<=n;i++) add(i);
	while(!st.empty()){
		int x=st.top();
		st.pop();
		ans=max(ans,1ll*len[x]*lazy[x]);
		lazy[link[x]]+=lazy[x];
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27