Submission #440219

#	Time	Username	Problem	Language	Result	Execution time	Memory
440219		keta_tsimakuridze	Palindromes (APIO14_palindrome)	C++14	73 / 100	119 ms	121888 KiB

palindrome

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,in[N],idx,suff;
vector<int>V[N];
string s;
queue<int> q;
struct st{
	int vis[27];
	int sufflink;
	int cnt;
	int len;
} tree[N];
void add(int i){
	int cur = suff;
	while(true) {
		if(s[i - tree[cur].len - 1] == s[i]) {
			if(tree[cur].vis[s[i]-'a']) {
				suff = tree[cur].vis[s[i]-'a']; 
				tree[suff].cnt++; 
				return;
			}
			suff = ++idx; 
			tree[idx].cnt = 1;
			tree[cur].vis[s[i]-'a'] = idx;
			tree[idx].len = tree[cur].len + 2;
			break;
		}
	
		cur = tree[cur].sufflink;
	}
	if(tree[idx].len == 1){
		tree[idx].sufflink = 2;
		return;
	} 

	while(true) { 
		cur = tree[cur].sufflink;
		if(s[i - tree[cur].len - 1] == s[i]) {
			tree[idx].sufflink = tree[cur].vis[s[i]-'a'];
			V[idx].push_back(tree[cur].vis[s[i]-'a']);
			in[tree[cur].vis[s[i]-'a']]++;
			break;
		}
	}
	
}
 main(){
	cin>>s;
	int n = s.size();
	s = '#' + s;
	idx = 2;
	tree[1].len = -1; 
	tree[2].len = 0;
	in[1] +=2;
	tree[1].sufflink = tree[2].sufflink = 1;
	suff = 2;
	for(int i=1;i<=n;i++){
		add(i);
	}
	for(int i=1;i<=idx;i++) {
		if(!in[i]) q.push(i);
	}
	int ans = 0;
	while(q.size()){ 
		int u = q.front();
		q.pop();
		ans = max(ans, tree[u].len * tree[u].cnt);
		for(int i=0;i<V[u].size();i++) {
			in[V[u][i]]--;
			tree[V[u][i]].cnt += tree[u].cnt;
			if(!in[V[u][i]]) q.push(V[u][i]);
		}
	}
	cout<<ans;
}

Compilation message (stderr)

palindrome.cpp:51:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 |  main(){
      |  ^~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:72:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i=0;i<V[u].size();i++) {
      |               ~^~~~~~~~~~~~

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