Submission #33798

#	Time	Username	Problem	Language	Result	Execution time	Memory
33798		sinhriv	Palindromes (APIO14_palindrome)	C++14	0 / 100	1000 ms	41984 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

struct eerTree{
	static const int Alpabet = 30;
	static const int N = 3e5;

	struct Node{
		int nxt[Alpabet];
		int suffix;
		int len;
		int value;
	};


	int cnt;
	int current;
	Node tree[N];
	string source;

	void addLetter(int pos){
		int u = current;
		int c = source[pos] - 'a';



		while(true){
			int len = tree[u].len;
			if(pos - len - 1 >= 0 && source[pos - len - 1] == source[pos]){
				break;
			}
			u = tree[u].suffix;
		}
		
		if(tree[u].nxt[c] != 0){
			++tree[tree[u].nxt[c]].value;
			return;
		}

		tree[u].nxt[c] = ++cnt;
		tree[cnt].value = 1;
		tree[cnt].len = tree[u].len + 2;


		if(tree[cnt].len == 1){
			tree[cnt].suffix = 2;
			current = cnt;
			return;
		}

		while(true){
			u = tree[u].suffix;
			int len = tree[u].len;
			if(pos - len - 1 >= 0 && source[pos - len - 1] == source[pos]){
				tree[cnt].suffix = tree[u].nxt[c];
				break;
			}
		}
		current = cnt;
	}

	void Init(string x){
		cnt = current = 2; 
		source = x;

		tree[1].len = -1;
		tree[1].suffix = 1;
		tree[2].len = 0;
		tree[2].suffix = 1;
	
		for(int i = 0; i < source.size(); ++i){
			addLetter(i);
		}
	}

	long long calc(){
		long long ans = 0;
		for(int i = cnt; i >= 1; --i){
			ans = max(ans, 1LL * tree[i].value * tree[i].len);
			tree[tree[i].suffix].value += tree[i].value;
		}
		return ans;
	}
}f;


int main(){
	if(fopen("1.inp", "r")){
		freopen("1.inp", "r", stdin);
	}

	ios_base::sync_with_stdio(false);
	cin.tie(NULL); 

	string s;
	cin >> s;

	f.Init(s);

	cout << f.calc();

	return 0;
}

Compilation message (stderr)

palindrome.cpp: In member function 'void eerTree::Init(std::__cxx11::string)':
palindrome.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < source.size(); ++i){
                    ^
palindrome.cpp: In function 'int main()':
palindrome.cpp:90:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("1.inp", "r", stdin);
                               ^

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