Submission #77647

#	Time	Username	Problem	Language	Result	Execution time	Memory
77647		samuelfgs96	Palindromes (APIO14_palindrome)	C++11	73 / 100	73 ms	55944 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']; 
			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 sz[N];
void dfs (int u) {
	for (int i = t1.ptr; i >= 3; i--) {
		sz[i] += t1.tree[i].qtd;
		sz[t1.tree[i].suffixEdg] += sz[i];
	}
}
void dfs2 (int u) {
	for (int i = 0; i < 26; i++)
		if (t1.tree[u].insertEdg[i])
			dfs2(t1.tree[u].insertEdg[i]);
	if (u >= 3) {
		ans = max(ans, ll(sz[u]) * (t1.tree[u].end - t1.tree[u].start + 1));
	}

}
int main (void) {
	cin >> s;
	t1 = treez(s);
	dfs(1);
	dfs2(1);
	dfs2(2);
	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: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 0 / 27