Submission #45666

#	Time	Username	Problem	Language	Result	Execution time	Memory
45666		sorry_Benq	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	10045 ms	121720 KiB

palindromic

#include <bits/stdc++.h>
 
using namespace std;

#define MAXN 1000005

const int sigma = 26;
 
 
struct Node
{
    int start, end;
    int length;
    int insertEdg[26];
    int suffixEdg;
    int cnt = 0;
};
 
Node root1, root2;
Node tree[MAXN];
int currNode;
string s;
int ptr;

void init(){
	root1.length = -1;
    root1.suffixEdg = 1;
    root2.length = 0;
    root2.suffixEdg = 1;
 
    tree[1] = root1;
    tree[2] = root2;
    ptr = 2;
    currNode = 1;
}
 
void insert(int idx)
{
//STEP 1//

	/* search for Node X such that s[idx] X S[idx]
	is maximum palindrome ending at position idx
	iterate down the suffix link of currNode to
	find X */
	int tmp = currNode;
	while (true)
	{
		int curLength = tree[tmp].length;
		if (idx - curLength >= 1 and s[idx] == s[idx-curLength-1])
			break;
		tmp = tree[tmp].suffixEdg;
	}

	/* Now we have found X ....
	* X = string at Node tmp
	* Check : if s[idx] X s[idx] already exists or not*/
	if(tree[tmp].insertEdg[s[idx]-'a'] != 0)
	{
		// s[idx] X s[idx] already exists in the tree
		currNode = tree[tmp].insertEdg[s[idx]-'a'];
		return;
	}

	// creating new Node
	ptr++;

	// making new Node as child of X with
	// weight as s[idx]
	tree[tmp].insertEdg[s[idx]-'a'] = ptr;

	// calculating length of new Node
	tree[ptr].length = tree[tmp].length + 2;

	// updating end point for new Node
	tree[ptr].end = idx;

	// updating the start for new Node
	tree[ptr].start = idx - tree[ptr].length + 1;


//STEP 2//

	/* Setting the suffix edge for the newly created
	Node tree[ptr]. Finding some String Y such that
	s[idx] + Y + s[idx] is longest possible
	palindromic suffix for newly created Node.*/

	tmp = tree[tmp].suffixEdg;

	// making new Node as current Node
	currNode = ptr;
	if (tree[currNode].length == 1)
	{
		// if new palindrome's length is 1
		// making its suffix link to be null string
		tree[currNode].suffixEdg = 2;
		return;
	}
	while (true)
	{
		int curLength = tree[tmp].length;
		if (idx-curLength >= 1 and s[idx] == s[idx-curLength-1])
			break;
		tmp = tree[tmp].suffixEdg;
	}

	// Now we have found string Y
	// linking current Nodes suffix link with s[idx]+Y+s[idx]
	tree[currNode].suffixEdg = tree[tmp].insertEdg[s[idx]-'a'];
}
 
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    for (int testcase = 0; testcase < T; testcase++){
		init();
		string t;
		cin >> t;
		s = "";
		for (int i = 0; i < t.size() / 2; i++){
			s += t[i];
			s += t[t.size() - i - 1];
		}
		if (t.size() % 2 == 1){
			s += t[t.size() / 2];
		}
		int N = s.size();
		int ans[N + 1];
		memset(ans, 0, sizeof(ans));
		ans[0] = 0;
		int res = 0;
		for(int i = 1; i <= N; i++)
		{
			insert(i - 1);
			//cout << "FOR LOOP " << n << endl;
			for(int v = currNode; tree[v].length > 0; v = tree[v].suffixEdg){
				if (tree[v].length % 2 == 0)
					ans[i] = max(ans[i], ans[i - tree[v].length] + 2);
			}
			if (i != N){
				res = max(res, ans[i] + 1);
			}
			else{
				res = max(res, ans[i]);
			}
		}
		cout << res << endl;
	}
    return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:121:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < t.size() / 2; i++){
                   ~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40