結果
| 問題 | No.263 Common Palindromes Extra |
| ユーザー |
 suisen
|
| 提出日時 | 2022-01-31 16:48:15 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 9,661 bytes |
| コンパイル時間 | 1,426 ms |
| コンパイル使用メモリ | 105,300 KB |
| 実行使用メモリ | 360,596 KB |
| 最終ジャッジ日時 | 2024-06-11 08:59:08 |
| 合計ジャッジ時間 | 4,068 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 12 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | AC | 24 ms
7,884 KB |
| testcase_04 | AC | 107 ms
21,348 KB |
| testcase_05 | AC | 121 ms
20,884 KB |
| testcase_06 | AC | 13 ms
6,016 KB |
| testcase_07 | AC | 243 ms
111,388 KB |
| testcase_08 | AC | 273 ms
119,836 KB |
| testcase_09 | MLE | - |
| testcase_10 | MLE | - |
| testcase_11 | AC | 92 ms
20,128 KB |
ソースコード
#define PROBLEM "https://yukicoder.me/problems/no/263"
#include <iostream>
#include <string>
#include <array>
#include <cassert>
#include <vector>
#include <map>
namespace suisen {
namespace internal::palindromic_tree {
template <typename T>
constexpr bool false_v = false;
template <typename T, typename Sequence, typename ChildrenContainerType>
struct PalindromicTreeBase {
using container_type = Sequence;
using value_type = T;
using children_container_type = ChildrenContainerType;
struct PalindromicTreeNode {
friend struct PalindromicTreeBase;
PalindromicTreeNode() = default;
private:
children_container_type _children;
int _suffix_link;
int _length;
int _multiplicity;
int _first_occurence;
};
using node_type = PalindromicTreeNode;
using node_pointer_type = node_type*;
static constexpr int NODE_NULL = -1;
static constexpr int NODE_M1 = 0;
static constexpr int NODE_0 = 1;
PalindromicTreeBase() {
_nodes.reserve(2);
node_pointer_type node_m1 = _new_node();
node_m1->_suffix_link = NODE_M1;
node_m1->_length = -1;
node_m1->_first_occurence = 1;
node_pointer_type node_0 = _new_node();
node_0->_suffix_link = NODE_M1;
node_0->_length = 0;
node_m1->_first_occurence = 0;
_active_index = 0;
}
template <typename Iterable>
PalindromicTreeBase(const Iterable& seq) : PalindromicTreeBase() {
add_all(seq);
}
void add(const value_type& val) {
_seq.push_back(val);
node_pointer_type par_node = _find_next_longest_suffix_palindrome(_get_node(_active_index));
auto& ch = par_node->_children;
bool inserted = false;
if constexpr (is_map) {
const auto [it, inserted_tmp] = ch.emplace(val, _nodes.size());
inserted = inserted_tmp;
_active_index = it->second;
} else if constexpr (is_vector) {
if (value_type(ch.size()) <= val) ch.resize(val + 1, NODE_NULL);
if (ch[val] == NODE_NULL) {
inserted = true;
ch[val] = _nodes.size();
_active_index = _nodes.size();
} else {
_active_index = ch[val];
}
} else if constexpr (is_array) {
if (ch[val] == NODE_NULL) {
inserted = true;
ch[val] = _nodes.size();
_active_index = _nodes.size();
} else {
_active_index = ch[val];
}
} else static_assert(false_v<void>);
if (not inserted) {
++_get_node(_active_index)->_multiplicity;
return;
}
int par_length = par_node->_length;
int par_suffix_link = par_node->_suffix_link;
node_pointer_type new_node = _new_node();
new_node->_multiplicity = 1;
new_node->_length = par_length + 2;
new_node->_first_occurence = _seq.size() - new_node->_length;
if (new_node->_length == 1) {
new_node->_suffix_link = NODE_0;
} else {
new_node->_suffix_link = _find_next_longest_suffix_palindrome(_get_node(par_suffix_link))->_children[val];
}
}
template <typename Iterable>
void add_all(const Iterable &seq) {
for (const auto &val : seq) add(val);
}
int node_num() const {
return _nodes.size();
}
const node_type& get_node(int index) const {
return _nodes[index];
}
int first_occurence(int index) const {
return get_node(index)._first_occurence;
}
int length(int index) const {
return get_node(index)._length;
}
int suffix_link(int index) const {
return get_node(index)._suffix_link;
}
int node_multiplicity(int index) const {
return get_node(index)._multiplicity;
}
const children_container_type& children(int index) const {
return get_node(index)._children;
}
std::vector<int> parents() const {
int sz = node_num();
std::vector<int> res(sz, -1);
for (int i = 0; i < sz; ++i) {
for (const auto& p : children(i)) {
if constexpr (is_map) {
res[p.second] = i;
} else if (p != NODE_NULL) {
res[p] = i;
}
}
}
return res;
}
const container_type get_palindrome(int index) {
if (index == NODE_M1) return container_type{};
int l = first_occurence(index), r = l + length(index);
return container_type{ _seq.begin() + l, _seq.begin() + r };
}
std::vector<int> frequency_table() const {
int sz = node_num();
std::vector<int> res(sz);
for (int i = sz; i-- > 1;) {
res[i] += node_multiplicity(i);
res[suffix_link(i)] += res[i];
}
return res;
}
private:
static constexpr bool is_map = std::is_same_v<std::map<value_type, int>, children_container_type>;
static constexpr bool is_vector = std::is_same_v<std::vector<value_type>, children_container_type>;
static constexpr bool is_array = std::is_same_v<std::array<value_type, std::tuple_size_v<children_container_type>>, children_container_type>;
int _active_index;
container_type _seq;
std::vector<node_type> _nodes;
node_pointer_type _new_node() {
node_pointer_type new_node = &_nodes.emplace_back();
if constexpr (not (is_map or is_vector)) {
std::fill(new_node->_children.begin(), new_node->_children.end(), NODE_NULL);
}
return new_node;
}
node_pointer_type _find_next_longest_suffix_palindrome(node_pointer_type node) {
const int sz = _seq.size();
for (;; node = _get_node(node->_suffix_link)) {
int opposite_index = sz - node->_length - 2;
if (opposite_index >= 0 and _seq[opposite_index] == _seq.back()) return node;
}
}
node_pointer_type _get_node(int index) {
return &_nodes[index];
}
};
} // namespace internal::palindromic_tree
template <typename T, typename Sequence = std::vector<T>>
struct PalindromicTree : public internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::map<T, int>> {
using base_type = internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::map<T, int>>;
using base_type::base_type;
};
template <typename T, typename Sequence = std::vector<T>>
struct PalindromicTreeVec : public internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::vector<T>> {
using base_type = internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::vector<T>>;
using base_type::base_type;
};
template <typename T, std::size_t N, typename Sequence = std::vector<T>>
struct PalindromicTreeArr : public internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::array<T, N>> {
using base_type = internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::array<T, N>>;
using base_type::base_type;
};
} // namespace suisen
using suisen::PalindromicTree;
int main() {
std::string s, t;
std::cin >> s >> t;
PalindromicTree<char, std::string> tree(s);
std::vector<int> f = tree.frequency_table();
tree.add('['), tree.add(']');
tree.add_all(t);
std::vector<int> g = tree.frequency_table();
long long ans = 0;
for (int i = 2, n = f.size(); i < n; ++i) {
ans += (long long) f[i] * (g[i] - f[i]);
}
std::cout << ans << std::endl;
// verification of other versions of palindromic tree
{
using suisen::PalindromicTreeVec;
using suisen::PalindromicTreeArr;
auto fix = [](const std::string& s) {
std::vector<int> res;
for (char c : s) res.push_back(c - 'A');
return res;
};
PalindromicTreeVec<int> tv(fix(s));
assert(tv.frequency_table() == f);
tv.add(26), tv.add(27);
tv.add_all(fix(t));
assert(tv.frequency_table() == g);
PalindromicTreeArr<int, 28> ta(fix(s));
assert(ta.frequency_table() == f);
ta.add(26), ta.add(27);
ta.add_all(fix(t));
assert(ta.frequency_table() == g);
}
return 0;
}