Submission #77645

#	Time	Username	Problem	Language	Result	Execution time	Memory
77645		samuelfgs96	Palindromes (APIO14_palindrome)	C++11	0 / 100	72 ms	56096 KiB

palindrome

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

using namespace std;

const int N = 212345;
typedef pair<int, int> pii;
typedef long long ll;
 
int bit[N];
struct treez {
	struct Node { 
		int start, end; 
		int length; 
		int insertEdg[26]; 
		int suffixEdg; 
		int qtd;
	}; 
	Node root1, root2; 
	Node tree[N]; 
	int currNode; 
	string s; 
	int ptr; 
	treez () { }
	treez (string s) : s(s) { 
		root1.length = -1; 
		root1.suffixEdg = 1; 
		root2.length = 0; 
		root2.suffixEdg = 1; 
		memset (tree, 0, sizeof tree);
		tree[1] = root1; 
		tree[2] = root2; 
		ptr = 2; 
		currNode = 1; 
		for (int i = 0; i < s.size(); i++) insert(i);
	}
	  
	void insert(int idx) { 
		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; 
		} 
	  
		if(tree[tmp].insertEdg[s[idx]-'a'] != 0) { 
			currNode = tree[tmp].insertEdg[s[idx]-'a']; 
			cout << idx << " ";
			for (int j = tree[currNode].start; j <= tree[currNode].end; j++)
				cout << s[j];
			cout << endl;
			tree[currNode].qtd++;
			return; 
		} 
		ptr++; 
		tree[tmp].insertEdg[s[idx]-'a'] = ptr; 
		tree[ptr].length = tree[tmp].length + 2; 
		tree[ptr].end = idx; 
		tree[ptr].start = idx - tree[ptr].length + 1; 
		tree[ptr].qtd = 1;
	  
		tmp = tree[tmp].suffixEdg; 
		currNode = ptr; 
		if (tree[currNode].length == 1) { 
			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; 
		} 
	  
		tree[currNode].suffixEdg = tree[tmp].insertEdg[s[idx]-'a']; 
	} 
};
treez t1;
string s;
ll ans;
int dfs (int u, int sz) {
	for (int i = 0; i < 26; i++)
		if (t1.tree[u].insertEdg[i])
			dfs(t1.tree[u].insertEdg[i], t1.tree[u].qtd);
	if (u >= 3) 
		ans = max(ans, ll(sz) * (t1.tree[u].end - t1.tree[u].start + 1));
	return sz;
}
int main (void) {
	cin >> s;
	t1 = treez(s);
	dfs(1, 0);
	dfs(2, 0);
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

palindrome.cpp: In constructor 'treez::treez(std::__cxx11::string)':
palindrome.cpp:40:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.size(); i++) insert(i);
                   ~~^~~~~~~~~~

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