oj.uz

Submission #1034703

# Submission time Handle Problem Language Result Execution time Memory
1034703 2024-07-25T16:54:03 Z xnqs Palindromes (APIO14_palindrome) C++17
100 / 100
 859 ms 104672 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <unordered_map>
#include <map>
 
struct TrieNode {
	int lazy = 0;
	TrieNode* next[26] = {nullptr};
	~TrieNode() {
		for (int i = 0; i < 26; i++) {
			if (next[i]) {
				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);
	}
};

class PairHasher {
public:
	std::size_t operator() (const std::pair<int,int>& p) const {
		return 1000000069LL*p.first + p.second;
	}
};

std::string str;
TrieNode* root;
std::unordered_map<std::pair<int,int>, TrieNode*, PairHasher> map;
//std::map<std::pair<int,int>, TrieNode*> map;
 
void insert(TrieNode* node, const std::string& str, int l, int r, int h1, int h2) {
	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'];
		
		h1 = 1LL*h1*53%1000000007 + (str[i]-'a'+1);
		if (h1>=1000000007) {
			h1 -= 1000000007;
		}
		h2 = 1LL*h2*53%1000000009 + (str[i]-'a'+1);
		if (h2>=1000000009) {
			h2 -= 1000000009;
		}
		map[std::pair<int,int>(h1,h2)] = node;
	}
	node->lazy += 1;
}
 
void insert_naive(TrieNode* node, const std::string& str, int l, int r) {
	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'];
	}
	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, 1000000009, 0> hash2(str);
	StringHasher<53, 1000000007, 1> hash1_r(str);
	StringHasher<53, 1000000009, 1> hash2_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)&&
			    hash2(i-m+1,i)==hash2_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;
		int longest_pfx_h2 = 0;
		l = 1, r = len;
		while (l<=r) {
			int m = (l+r)>>1;
			int h1 = hash1(i,i+m-1);
			int h2 = hash2(i,i+m-1);
			if (!map.count(std::pair<int,int>(h1,h2))) {
				r = m-1;
			}
			else {
				longest_pfx = map[std::pair<int,int>(h1,h2)];
				longest_pfx_len = m;
				longest_pfx_h1 = h1;
				longest_pfx_h2 = h2;
				l = m+1;
			}
		}
 
		insert(longest_pfx,str,i+longest_pfx_len,i+len-1,longest_pfx_h1,longest_pfx_h2);
	}
 
	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)&&
			    hash2(i-m,i-1)==hash2_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;
		int longest_pfx_h2 = 0;
		l = 1, r = len;
		while (l<=r) {
			int m = (l+r)>>1;
			int h1 = hash1(i,i+m-1);
			int h2 = hash2(i,i+m-1);
			if (!map.count(std::pair<int,int>(h1,h2))) {
				r = m-1;
			}
			else {
				longest_pfx = map[std::pair<int,int>(h1,h2)];
				longest_pfx_len = m;
				longest_pfx_h1 = h1;
				longest_pfx_h2 = h2;
				l = m+1;
			}
		}
 
		insert(longest_pfx,str,i+longest_pfx_len,i+len-1,longest_pfx_h1,longest_pfx_h2);
	}
 
	ans = std::max(ans, dfs(root, /*odd=*/0).second);
	delete root;
#endif
	
	std::cout << ans << "\n";
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:139:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |  for (int i = 0; i < str.size(); i++) {
      |                  ~~^~~~~~~~~~~~
palindrome.cpp:145:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |    if (i-m+1>=0&&i+m-1<str.size()&&
      |                  ~~~~~^~~~~~~~~~~
palindrome.cpp:189:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |  for (int i = 1; i < str.size(); i++) {
      |                  ~~^~~~~~~~~~~~
palindrome.cpp:199:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |    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:129:43:   required from here
palindrome.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   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 = 1000000009; bool REV = false; std::string = std::__cxx11::basic_string<char>]':
palindrome.cpp:130:43:   required from here
palindrome.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
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:131:45:   required from here
palindrome.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
palindrome.cpp: In instantiation of 'StringHasher<PRIME, MOD, REV>::StringHasher(std::string) [with int PRIME = 53; int MOD = 1000000009; bool REV = true; std::string = std::__cxx11::basic_string<char>]':
palindrome.cpp:132:45:   required from here
palindrome.cpp:35: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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 452 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 452 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 624 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 764 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 604 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3676 KB Output is correct
2 Correct 10 ms 3564 KB Output is correct
3 Correct 15 ms 2552 KB Output is correct
4 Correct 13 ms 2392 KB Output is correct
5 Correct 5 ms 3676 KB Output is correct
6 Correct 6 ms 3376 KB Output is correct
7 Correct 8 ms 3496 KB Output is correct
8 Correct 3 ms 856 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 5 ms 2652 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 35528 KB Output is correct
2 Correct 158 ms 33884 KB Output is correct
3 Correct 194 ms 21484 KB Output is correct
4 Correct 182 ms 20068 KB Output is correct
5 Correct 62 ms 34244 KB Output is correct
6 Correct 65 ms 25120 KB Output is correct
7 Correct 107 ms 21740 KB Output is correct
8 Correct 18 ms 3928 KB Output is correct
9 Correct 53 ms 7860 KB Output is correct
10 Correct 63 ms 29488 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 104672 KB Output is correct
2 Correct 537 ms 96128 KB Output is correct
3 Correct 859 ms 63448 KB Output is correct
4 Correct 651 ms 55784 KB Output is correct
5 Correct 217 ms 103040 KB Output is correct
6 Correct 389 ms 75668 KB Output is correct
7 Correct 401 ms 65156 KB Output is correct
8 Correct 56 ms 10660 KB Output is correct
9 Correct 66 ms 10740 KB Output is correct
10 Correct 221 ms 88704 KB Output is correct
11 Correct 457 ms 104576 KB Output is correct
12 Correct 101 ms 15536 KB Output is correct