Submission #1034685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034685		xnqs	Palindromes (APIO14_palindrome)	C++17	73 / 100	620 ms	92440 KiB

palindrome

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <unordered_map>
 
struct TrieNode {
	int lazy = 0;
	TrieNode* next[26] = {nullptr};
	~TrieNode() {
		for (int i = 0; i < 26; i++) {
			if (next[i]!=nullptr) {
				delete next[i];
			}
		}
	}
};
 
template<const int PRIME = 53, const int MOD = 1000000007, const bool REV = 0>
class StringHasher {
private:
	int len;
	std::vector<int> pPRIME;
	std::vector<int> pfx_hash;
public:
	StringHasher(std::string str) {
		len = str.size();
		pPRIME.assign(str.size(),0);
		pPRIME[0] = 1;
		pfx_hash.assign(str.size(),0);
		pfx_hash[0] = str[((REV) ? str.size()-1 : 0)] - 'a' + 1;
		for (int i = 1; i < str.size(); i++) {
			pPRIME[i] = 1LL*pPRIME[i-1]*PRIME%MOD;
			pfx_hash[i] = 1LL*pfx_hash[i-1]*PRIME%MOD + (str[((REV) ? str.size()-i-1 : i)] - 'a' + 1);
			if (pfx_hash[i]>=MOD) {
				pfx_hash[i] -= MOD;
			}
		}
	}
 
	inline int hash_query(int l, int r) {
		if (REV) {
			l = len-l-1;
			r = len-r-1;
			std::swap(l,r);
		}
		int ret = pfx_hash[r] - ((l-1>=0) ? 1LL*pPRIME[r-l+1]*pfx_hash[l-1]%MOD : 0);
		if (ret<0) {
			ret += MOD;
		}
		return ret;
	}
 
	int operator() (int l, int r) {
		return hash_query(l,r);
	}
};
 
std::string str;
TrieNode* root;
std::unordered_map<int, TrieNode*> map;
 
void insert(TrieNode* node, const std::string& str, int l, int r, int h) {
	if (l>r+1) {
		return;
	}
 
	for (int i = l; i <= r; i++) {
		if (!node->next[str[i]-'a']) {
			node->next[str[i]-'a'] = new TrieNode;
		}
		node = node->next[str[i]-'a'];
		
		h = 1LL*h*53%1000000007 + (str[i]-'a'+1);
		if (h>=1000000007) {
			h -= 1000000007;
		}
		map[h] = node;
	}
	node->lazy += 1;
}
 
std::pair<int,int64_t> dfs(TrieNode* node, bool odd = 1, int depth = 0) {
	int freq = node->lazy;
	int64_t max = 0;
	for (int i = 0; i < 26; i++) {
		if (node->next[i]!=nullptr) {
			auto [a, b] = dfs(node->next[i], odd, depth+1);
			freq += a;
			max = std::max(max, b);
		}
	}
 
	max = std::max(max, static_cast<int64_t>(2LL*depth-odd)*freq);
	return std::pair<int,int64_t>(freq,max);
}
 
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
 
	std::cin >> str;
	StringHasher<53, 1000000007, 0> hash1(str);
	StringHasher<53, 1000000007, 1> hash1_r(str);
 
	int64_t ans = 0;
 
	// odd length
#if 1
	root = new TrieNode;
	for (int i = 0; i < str.size(); i++) {
		// bs length of palindrome centered in i
		int len = 1;
		int l = 1, r = str.size();
		while (l<=r) {
			int m = (l+r)>>1;
			if (i-m+1>=0&&i+m-1<str.size()&&
			    hash1(i-m+1,i)==hash1_r(i,i+m-1)) {
				len = m;
				l = m+1;
			}
			else {
				r = m-1;
			}
		}
 
		// bs length of longest prefix in trie so we get amortized build time
		TrieNode* longest_pfx = root;
		int longest_pfx_len = 0;
		int longest_pfx_h1 = 0;
		l = 1, r = len;
		while (l<=r) {
			int m = (l+r)>>1;
			if (!map.count(hash1(i,i+m-1))) {
				r = m-1;
			}
			else {
				longest_pfx = map[hash1(i,i+m-1)];
				longest_pfx_len = m;
				longest_pfx_h1 = hash1(i,i+m-1);
				l = m+1;
			}
		}
 
		insert(longest_pfx,str,i+longest_pfx_len,i+len-1,longest_pfx_h1);
	}
 
	ans = std::max(ans, dfs(root).second);
	delete root;
	map.clear();
#endif
 
	// even length
#if 1
	root = new TrieNode;
	for (int i = 1; i < str.size(); i++) {
		if (str[i-1]!=str[i]) {
			continue;
		}
 
		// bs length of palindrome centered in i
		int len = 1;
		int l = 1, r = str.size();
		while (l<=r) {
			int m = (l+r)>>1;
			if (i-m>=0&&i+m-1<str.size()&&
			    hash1(i-m,i-1)==hash1_r(i,i+m-1)) {
				len = m;
				l = m+1;
			}
			else {
				r = m-1;
			}
		}
 
		// bs length of longest prefix in trie so we get amortized build time
		TrieNode* longest_pfx = root;
		int longest_pfx_len = 0;
		int longest_pfx_h1 = 0;
		l = 1, r = len;
		while (l<=r) {
			int m = (l+r)>>1;
			if (!map.count(hash1(i,i+m-1))) {
				r = m-1;
			}
			else {
				longest_pfx = map[hash1(i,i+m-1)];
				longest_pfx_len = m;
				longest_pfx_h1 = hash1(i,i+m-1);
				l = m+1;
			}
		}
 
		insert(longest_pfx,str,i+longest_pfx_len,i+len-1,longest_pfx_h1);
	}
 
	ans = std::max(ans, dfs(root, /*odd=*/0).second);
	delete root;
#endif
	
	std::cout << ans << "\n";
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:114:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |  for (int i = 0; i < str.size(); i++) {
      |                  ~~^~~~~~~~~~~~
palindrome.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |    if (i-m+1>=0&&i+m-1<str.size()&&
      |                  ~~~~~^~~~~~~~~~~
palindrome.cpp:159:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |  for (int i = 1; i < str.size(); i++) {
      |                  ~~^~~~~~~~~~~~
palindrome.cpp:169:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |    if (i-m>=0&&i+m-1<str.size()&&
      |                ~~~~~^~~~~~~~~~~
palindrome.cpp: In instantiation of 'StringHasher<PRIME, MOD, REV>::StringHasher(std::string) [with int PRIME = 53; int MOD = 1000000007; bool REV = false; std::string = std::__cxx11::basic_string<char>]':
palindrome.cpp:106:43:   required from here
palindrome.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for (int i = 1; i < str.size(); i++) {
      |                   ~~^~~~~~~~~~~~
palindrome.cpp: In instantiation of 'StringHasher<PRIME, MOD, REV>::StringHasher(std::string) [with int PRIME = 53; int MOD = 1000000007; bool REV = true; std::string = std::__cxx11::basic_string<char>]':
palindrome.cpp:107:45:   required from here
palindrome.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]

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