#978826 (C++23) No.2606 Mirror Relay

提出ソース

結果

問題	No.2606 Mirror Relay
ユーザー	👑 hitonanode
提出日時	2024-05-03 17:32:42
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	58 ms / 2,000 ms
コード長	4,134 bytes
コンパイル時間	1,752 ms
コンパイル使用メモリ	127,744 KB
実行使用メモリ	37,924 KB
最終ジャッジ日時	2024-05-03 17:32:47
合計ジャッジ時間	3,945 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	1 ms 5,376 KB
testcase_32	AC	1 ms 5,376 KB
testcase_33	AC	2 ms 5,376 KB
testcase_34	AC	2 ms 5,376 KB
testcase_35	AC	2 ms 5,376 KB
testcase_36	AC	2 ms 5,376 KB
testcase_37	AC	2 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	12 ms 5,504 KB
testcase_40	AC	12 ms 5,376 KB
testcase_41	AC	12 ms 5,376 KB
testcase_42	AC	12 ms 5,376 KB
testcase_43	AC	12 ms 5,376 KB
testcase_44	AC	14 ms 5,376 KB
testcase_45	AC	13 ms 5,376 KB
testcase_46	AC	13 ms 5,376 KB
testcase_47	AC	13 ms 5,376 KB
testcase_48	AC	13 ms 5,376 KB
testcase_49	AC	24 ms 13,068 KB
testcase_50	AC	25 ms 14,096 KB
testcase_51	AC	26 ms 14,396 KB
testcase_52	AC	21 ms 11,916 KB
testcase_53	AC	25 ms 14,856 KB
testcase_54	AC	24 ms 13,708 KB
testcase_55	AC	34 ms 19,276 KB
testcase_56	AC	23 ms 13,448 KB
testcase_57	AC	23 ms 12,388 KB
testcase_58	AC	27 ms 15,624 KB
testcase_59	AC	9 ms 5,376 KB
testcase_60	AC	9 ms 5,376 KB
testcase_61	AC	10 ms 5,376 KB
testcase_62	AC	9 ms 5,376 KB
testcase_63	AC	10 ms 5,632 KB
testcase_64	AC	10 ms 5,376 KB
testcase_65	AC	9 ms 5,376 KB
testcase_66	AC	9 ms 5,376 KB
testcase_67	AC	10 ms 5,376 KB
testcase_68	AC	9 ms 5,376 KB
testcase_69	AC	58 ms 37,924 KB
testcase_70	AC	1 ms 5,376 KB
testcase_71	AC	1 ms 5,376 KB
testcase_72	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#line 1 "string/test/palindromic_tree.yuki2606.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/2606"
#line 2 "string/palindromic_tree.hpp"

#include <map>
#include <string>
#include <vector>

// Palindromic tree / Eertree （回文木）
namespace palindromic_tree {

template <class Key> class Node {
    int suffix_link_ = -1; // このノードからのsuffix link （suffix の最長回文）
    int length_ = -1;      // このノードが表す回文の長さ
    std::map<Key, int> children;

public:
    Node() = default;

    Node(int suffix_link, int length) : suffix_link_(suffix_link), length_(length) {}

    int suffix_link() const { return suffix_link_; }

    int length() const { return length_; }

    int get_child(Key c) const {
        auto it = children.find(c);
        return (it == children.end()) ? -1 : it->second;
    }

    void set_child(int c, int nxt_idx) { children[c] = nxt_idx; }

    template <class OStream> friend OStream &operator<<(OStream &os, const Node &node) {
        os << "Node(suffix_link=" << node.suffix_link() << ", length=" << node.length()
           << ", children={";
        for (const auto &[c, nxt] : node.children) os << c << "->" << nxt << ", ";
        return os << "})";
    }
};

template <class Key> struct Tree {
    std::vector<Node<Key>> nodes;

    Tree() { nodes = {Node<Key>(0, -1), Node<Key>(0, 0)}; }

    // nodes[cursor] は s[0:i] の suffix
    // s[0:(i + 1)] の suffix で、 nodes[cursor] 自身とその先祖の最長回文を探す
    int find_next_suffix(const std::vector<Key> &s, int i, int cursor) {
        while (true) {
            const int cur_len = nodes.at(cursor).length();
            const int opposite_pos = i - cur_len - 1;
            if (opposite_pos >= 0 and s.at(opposite_pos) == s.at(i)) return cursor;
            cursor = nodes.at(cursor).suffix_link();
        }
    }

    template <class Callback> void add_string(const std::vector<Key> &s, Callback callback) {
        int cursor = 1;

        for (int i = 0; i < (int)s.size(); ++i) {

            cursor = find_next_suffix(s, i, cursor);

            int ch = nodes.at(cursor).get_child(s.at(i));

            if (ch < 0) {
                const int nxt_cursor = nodes.size();
                const int new_length = nodes.at(cursor).length() + 2;
                int new_suffix_link_par = find_next_suffix(s, i, nodes.at(cursor).suffix_link());
                int new_suffix_link = nodes.at(new_suffix_link_par).get_child(s.at(i));
                if (new_suffix_link < 1) new_suffix_link = 1;

                nodes.at(cursor).set_child(s.at(i), nxt_cursor);
                nodes.push_back(Node<Key>(new_suffix_link, new_length));
                cursor = nxt_cursor;

            } else {
                cursor = ch;
            }

            callback(i, cursor);
        }
    }

    template <class Callback> void add_string(const std::string &s, Callback callback) {
        add_string(std::vector<Key>{s.cbegin(), s.cend()}, callback);
    }

    template <class Vec> void add_string(const Vec &s) {
        add_string(s, [](int, int) {});
    }
};

} // namespace palindromic_tree
#line 3 "string/test/palindromic_tree.yuki2606.test.cpp"

#include <algorithm>
#include <iostream>
#line 8 "string/test/palindromic_tree.yuki2606.test.cpp"

using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    string S;
    cin >> S;

    palindromic_tree::Tree<char> tree;

    vector<long long> visitcnt(S.size() + 2);
    tree.add_string(S, [&](int, int node_idx) { visitcnt.at(node_idx)++; });

    const int V = tree.nodes.size();
    for (int i = V - 1; i > 0; --i) visitcnt.at(tree.nodes.at(i).suffix_link()) += visitcnt.at(i);

    vector<vector<int>> children(V);
    for (int i = 1; i < V; ++i) children.at(tree.nodes.at(i).suffix_link()).push_back(i);

    vector<long long> dp(V, 0);
    for (int i = 0; i < V; ++i) {
        dp.at(i) += visitcnt.at(i) * max(tree.nodes.at(i).length(), 0);
        for (int ch : children.at(i)) dp.at(ch) += dp.at(i);
    }

    cout << *max_element(dp.begin(), dp.end()) << '\n';
}